Симплексный метод


главная страница Рефераты Курсовые работы текст файлы добавьте реферат (спасибо :)Продать работу

поиск рефератов

Контрольная работа на тему Симплексный метод

скачать
похожие рефераты
подобные качественные рефераты

Размер: 73.1 кб.
Язык: русский
Разместил (а): Елизавета
16.11.2010
1 2    
Задача 1.
Решить задачу линейного программирования симплексным методом.
Вариант 3.
Найти наибольшее значение функции f(X) = - x1 - x2 + 2x3 при ограничениях
2x1 + x2 + x3 £ 2
x1 - x2 + x3 £ 1,
xj ³ 0, j = 1, 2, 3.
Решение.
Приведем задачу к каноническому виду, вводя дополнительные неотрицательные переменные x4,5 ³ 0.
f(X) = - x1 - x2 + 2x3 ® max
2x1 + x2 + x3 + x4 = 2
x1 - x2 + x3 + x5 = 1,
xj ³ 0, j = 1, 2, 3, 4, 5.
Каноническая задача имеет необходимое число единичных столбцов, т. е. обладает очевидным начальным опорным решением.
Очевидное начальное опорное решение (0; 0; 0; 2; 1).
Решение осуществляется симплекс-методом с естественным базисом. Расчеты оформим в симплекс-таблицах
Номер симплекс-таблицы
Базис
Cj
Ci
B
-1
-1
2
0
0
Q
A1
A2
A3
A4
A5
0
A4
0
2
2
1
1
1
0
2:1 = 1
A5
0
1
1
-1
1
0
1
1:1 = 1
j
-
0
1
1
-2
0
0
1
A4
0
1
1
2
0
1
-1
1:2 = 1/2
A3
2
1
1
-1
1
0
1
j
-
2
3
-1
0
0
2
2
A2
-1
1/2
1/2
1
0
1/2
-1/2
A3
2
3/2
3/2
0
1
1/2
1/2
j
-
5/2
7/2
0
0
1/2
3/2
Начальное опорное решение (0; 0; 0; 1; 1), соответствующее симплекс-таблице 0, неоптимальное, так как в D - строке есть отрицательные значения, наименьшее в столбце А3. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А5, эта строка направляющая. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А5 выводим из базиса, а А3 - вводим в базис. После пересчета получаем симплекс-таблицу 1. Соответствующее опорное решение (0; 0; 1; 1; 0) не оптимально, так как в D - строке есть отрицательные значения, в столбце А2.Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А4. В качестве направляющей строки возьмем А4. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А4 выводим из базиса, а А2 - вводим в базис. Опорное решение, соответствующее симплекс-таблице 2 (0; 1/2; 3/2; 0; 0) - оптимально, так как в D - строке нет отрицательных значений.
Отбрасывая значения дополнительных переменных х4 и х5, получаем оптимальное решение исходной задачи:
х1 = 0, х2 = 1/2 = 0,5; х3 = 3/2 = 1,5; fmax = -1×0 - 1×0,5 + 2×1,5 = 2,5.
Задача 2.
Задание 1. Сформулировать экономико-математическую модель исходной экономической задачи.
Задание 2. Решить полученную задачу линейного программирования графическим методом.
Задание 3. Сформулировать двойственную задачу и найти ее оптимальное решение, используя теоремы двойственности.
Вариант 3.
Из 505 м2 ткани нужно сшить не более 150 женских и не более 100 детских платьев. На пошив одного женского и детского платья требуется соответственно 3 м2 и 1 м2 ткани. При реализации каждого женского платья получают 10 ден. единиц прибыли, а детского – 5 ден. единиц. Сколько нужно сшить женских и детских платьев, чтобы получить наибольшую прибыль?
Решение.
Задание 1.
Обозначим x1 и x2 количество женских и детских платьев, соответственно (план пошива). Очевидно, x1,2 ³ 0 и целые. Так как женских платьев должно быть не более 150, то x1 £ 150, аналогично, для детских платьев получаем x2 £ 100. Расход ткани на план пошива (x1, x2) составит 3x1 + x2 м2, эта величина не должна превышать запаса ткани 505 м2. Следовательно, должно выполняться неравенство 3x1 + x2 £ 505.
Прибыль от продажи платьев составит f(X) = 10x1 + 5x2 ден. единиц, и она должна быть наибольшей
Получаем экономико-математическую модель задачи:
Найти максимум функции f(X) при заданных ограничениях
f(X) = 10x1 + 5x2 ® max
3x1 + x2 £ 505
x1 £ 150
x2 £ 100
x1,2 ³ 0, целые.
Задание 2.
Решаем задачу без условия целочисленности решения. Построим множество допустимых решений задачи.
Прямые ограничения x1,2 ³ 0 выделяют первую четверть плоскости.
Проведем прямую 3x1 + x2 = 505 через точки (110; 175) и (175; -5). Подставим в первое неравенство координаты точки (0; 0): 3×0 +1×0 = 0 < 505, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.
Проведем прямую x1 = 150 и выберем левую полуплоскость.
Проведем прямую x2 = 100 и выберем нижнюю полуплоскость.
Множество допустимых решений – это многоугольник ABCDO.
Построим линию уровня целевой функции f(X) = 10x1 + 5x2 10x1 + 5x2 = 0 через точки (0; 0 ) и (-10; 20). Вектор-градиент {10; 5} задает направление, перемещаясь вдоль которого, можно увеличить значение целевой функции; перемещаясь в противоположном направлении, можно уменьшить ее значение.
Из чертежа видно, что наибольшее значение целевой функции будет на линии уровня, проходящей через точку В.
Координаты этой точки найдем из системы
3x1 + x2 = 505,
x2 = 100.
x1 = 135,
x2 = 100.
fmах = 10 ×135 + 5 ×100 = 1850 ден. единиц.
Полученное оптимальное решение оказалось целым, следовательно, это решение поставленной задачи. Получили: в оптимальном плане пошива следует сшить женских платьев 135 шт., детских – 100 шт. При этом прибыль составит 1850 ден. единиц и будет наибольшей.

х1 = 150
А
В
С
D
O
·
 

Задание 3.
Двойственная задача.
Найти минимум функции g(Y) при ограничениях:
g(Y) = 505y1 + 150y2 + 100y3 ® min
3y1 + y2 ³ 10
y1 + y3 ³ 5
y1,2,3 ³ 0.
Оптимальное решение прямой задачи Х = (135; 100). Подставим его в ограничения этой задачи
3×135 + 1×100 = 505
135 < 150
100 = 100.
Условия дополняющей нежесткости (вторая теорема двойственности): для оптимальных планов двойственных задач имеют место соотношения:

Так как для оптимального решения прямой задачи второе ограничение выполняется как неравенство, то в оптимальном решении двойственной задачи y2 = 0.
Так как для оптимального решения прямой задачи х1 > 0и х2 > 0, то оба ограничения двойственной задачи выполняются как равенство. Для нахождения решения двойственной задачи получаем систему
y2 = 0
3y1 + y2 = 10
y1 + y3 = 5.
Получаем решение: y1 = 10/3, y2 = 0, y3 = 5/3.
Найдем значение целевой функции двойственной задачи:
g(Y) = 505×10/3 + 150×0 + 100×5/3 = 5550/3 = 1850.
Получили gmin = fmax = 1850 ден. единиц.
Так как значения прямой и двойственной функций равны, то Y = (10/3; 0; 5/3) является оптимальным решением двойственной задачи (по первой теореме двойственности).
Задача 3.
Задание 1. Записать исходные данные задачи в виде транспортной таблицы, определить, открытой или закрытой является транспортная задача.
Задание 2. Сформулировать экономико-математическую модель исходной транспортной задачи.
Задание 3. Найти оптимальный план перевозок, отметив при этом единственность или неединственность оптимального плана.
Вариант 3.
Картофель из четырех районов должен быть перевезен в три хранилища. Запасы картофеля в районах соответственно равны 400 т, 500 т, 800 т и 500 т. Возможности хранилищ соответственно равны 700 т, 800 т и 700 т. Затраты на перевозку одной тонны картофеля из первого района в каждое из хранилищ равны соответственно 1, 4 и 3 ден. единиц; аналогичные затраты на перевозку из второго района составляют 7, 1 и 5 ден. единиц, из третьего - 4, 8 и 3 ден. единиц, из четвертого - 6, 2 и 8 ден. единиц. Найти план перевозок картофеля из районов в хранилища, при котором транспортные расходы были бы минимальными.
Решение.
Задание 1.
Мощности
поставщиков
Мощности потребителей
700
800
700
400
1
4
3
500
7
1
5
800
4
8
3
500
6
2
8
Сумма мощностей поставщиков (запасы картофеля в всех районах) 400+500+800+500 = 2200, сумма мощностей потребителей (возможности всех хранилищ) 700+800+700 = 2200. Суммы равны, данная задача является транспортной задачей закрытого типа.
Задание 2.
Обозначим xij объем поставок картофеля от i – го поставщика (района) j – му потребителю (хранилищу), i = 1, 2, 3, 4; j = 1, 2, 3. Очевидно, xij ³ 0. В закрытой транспортной задаче все ограничения являются равенствами.
Так как потребности должны быть удовлетворены, то выполняются условия:
х11 + х21 + х31 + х41 = 700
х12 + х22 + х32 + х42 = 800                (1)
х13 + х23 + х33 + х43 = 700
Так как поставки от поставщика всем потребителям не могут быть больше его возможностей, то выполняются условия:
х11 + х12 + х13 = 400
х21 + х22 + х23 = 500       (2)
х31 + х32 + х33 = 800
х41 + х42 + х43 = 500
Затраты на транспортировку составят
F(X) = х11 + 4х12 + 3х13 +
+ 7х21 + х22 + 5x23 +
+ 4х31 + 8х32 + 3х33 +
+ 6х41 + 2х42 + 8х43 .
Требуется найти неотрицательное решение системы уравнений (1) – (2), на котором целевая функция затрат F(X) принимает минимальное значение.
Задание 3.
Начальный план перевозок находим методом минимальной стоимости:
Заполняем клетку (1; 1) х11 = min {700, 400} = 400, от поставщика 1 вывезено все, в строке 1 больше поставок нет. Заполняем клетку (2; 2) х22 = min {800, 500} = 500, от поставщика 2 вывезено все, в строке 2 больше поставок нет. Клетка (4; 2) х42 = min {800 - 500, 500} = 300, потребителю 2 все завезено, в столбец 2 больше поставок нет. Клетка (3; 3) х33 = min {700, 800} = 700, потребителю 3 все завезено, в столбец 3 больше поставок нет. Далее клетка (3; 1) х31 = 100. Клетка (4; 1) х41 = 200. Все клетки, в которые даны поставки, считаем занятыми, остальные – свободными. Первоначальный план перевозок задается таблицей 1.
Таблица 1.
Мощности
поставщиков
Мощности потребителей
ui
700
800
700
400
1
400
4
3
0
500
7
1
500
5
-4
800
4
100
8
3
700
-3
500
6
200
2
300
8
-5
vj
1
-3
0
Исследуем этот план перевозок на оптимальность методом потенциалов. Потенциалы для занятых клеток удовлетворяют уравнениям: vj = cij + ui.
Пусть u1 = 0; по клетке (1; 1) находим v1 = 1; по клетке (3; 1) находим u3 = -3; по клетке (4; 1) находим u4 = -5; по клетке (4; 2) находим v2 = -3; по клетке (3; 3) находим v3 = -0; по клетке (2; 2) находим u2 = -4.
Для всех клеток матрицы перевозок найдем оценки клеток dij = (ui + cij) - vj :

Среди оценок нет отрицательных, следовательно план перевозок Х0 (таблица 1) оптимальный.
Так как среди оценок свободных клеток есть нулевые (клетка (1; 3)), то оптимальный план перевозок не единственный.
Общие затраты на перевозки
F(X1) = 1*400 + 1*500 + 4*100 + 3*700 + 6*200 + 2*300 = 5200 ден. единиц будут минимальными при:
x11 = 400, x22 = 500, x31 = 100, х33 = 700, x41 = 200, x42 = 300, остальные xij = 0.
По оптимальному плану перевозок следует перевезти картофеля:
из первого района в первое хранилище                   - 400 т;
из второго района во второе хранилище                 - 500 т;
из третьего района в первое хранилище                   - 100 т,
в третье хранилище              - 700 т;
из четвертого района в первое хранилище     - 200 т,
во второе хранилище - 300 т.
Задача 4
В таблице приведены годовые данные о трудоемкости производства I т цемента (нормо-смен) (N —последняя цифра зачетной книжки студента):
Текущий номер года (t)
1
2
3
4
5
6
7
8
9
10
Трудоемкость 1 т цемента (yi)
7,9+0,N
8,3+0,N
7,5+0,N
6,9+0,N
7,2+0,N
6,5+0,N
5,8+0,N
4,9+0,N
5,1+0,N
4,4+0,N
Задание 1. Сгладить временной ряд методом простой скользящей средней, выбрав длину интервала сглаживания m = 3; результаты отра­зить на графике.
Задание 2. Определить наличие тренда во временном ряду методом Фостера - Стьюарта. Табличные значения статистики Стьюдента ta принять равными при уровне значимости a = 0.05 ta = 2,23 , а при a = 0,30 - ta = 1,09; другие необходимые табличные данные приведены в таблице 4.5 учебника на с.153 (описание метода Фостера - Стьюар­та см. учебник с. 151- 153).
Задание 3. Для исходного временного ряда построить линейную трендовую модель , определив ее параметры на основе метода наименьших квадратов (соответствующую систему нормальных уравнений см. в учебнике на с. 196 формула (5.5)).
Задание 4. Оценить адекватность построенной модели на основе исследования
а) близости математического ожидания остаточной компоненты (ряда остатков) нулю; критические значения r-критерия принять равным тому числу, как указанно в задании 2;
б) случайности отклонений остаточной компоненты по критерию пиков (поворотных точек); Расчеты выполнить на основе соотношения 5.9. учебника на с. 200;
в) независимости уровней ряда остатков (отсутствие автокорреляции) на основе критерия Дарбина — Уотсона (см. учебник с. 203— 204), используя в качестве критических значений dl = 1.08 и d2 = 1,36; если критерий Дарбина — Уотсона ответа не дает, исследование независимости провести по первому коэффициенту автокорреляции:
,
где ei -- уровни остаточной компоненты;
Модуль первого коэффициента автокорреляции сравнить с критическим уровнем этого коэффициента, значение которого принять равным 0,36;
г) нормальности закона распределения уровней остаточной компоненты на основе RS-критерия;
В качестве критических значений принять интервал от 2,7 до 3,7 (см. учебник, стр. 201—-202).
Задание 5. Оценить точность построенной трендовой линейной модели, используя показатели среднего квадратического отклонения от линии тренда (формула (5,17) учебника на с. 210, k = 1) и средней относительной ошибки аппроксимации (формула (5.14) учебника на с. 204).
Задание 6. Построить точечный и интервальный прогноз трудоемкости производства 1 т цемента на два шага вперед (формула (5.18) учебника на с. 210). Результаты моделирования и прогнозирования отразить на графике.
Все промежуточные результаты вычислений представить в табли­цах, вычисления провести с двумя десятичными знаками в дробной части.
Вариант 3. Условия при N = 3
Текущий номер года (t)
1
2
3
4
5
6
7
8
9
10
Трудоемкость 1 т цемента (yi)
8,2
8,6
7,8
7,2
7,5
6,8
6,1
5,2
5,4
4,7
Решение.
Задание 1. Сглаживание ряда Y(t) произведем по простой скользящей средней

Результаты в таблице 1.
Таблица 1.
Сглаживание ряда динамики
t
Факт Y(t)
Скользящая сумма
Скользящее среднее
1
8,2
-
-
2
8,6
24,6
8,20
3
7,8
23,6
7,87
4
7,2
22,5
7,50
5
7,5
21,5
7,17
6
6,8
20,4
6,80
7
6,1
18,1
6,03
8
5,2
16,7
5,57
9
5,4
15,3
5,10
10
4,7
-
-
    продолжение
1 2    

Добавить контрольную работу в свой блог или сайт
загрузка...
Удобная ссылка:

Скачать контрольную работу бесплатно
подобрать список литературы


Симплексный метод


Постоянный url этой страницы:
Контрольная работа Симплексный метод


Разместите кнопку на своём сайте:
Рефераты
вверх страницы


© coolreferat.com | написать письмо | правообладателям | читателям
При копировании материалов укажите ссылку.