Линейное программирование (стр. 1 из 4)
Задача 1.
Решить задачу линейного программирования симплексным методом.
Вариант 2.
Найти наибольшее значение функции f(X) = x1 – 4x4 при ограничениях
x1 – x2 + x3 + x4 = 3x1 + x2 + 2x3 = 5,
xj ³ 0, j = 1, 2, 3, 4.
Решение.
Задача записана в каноническом виде, но не имеет необходимого числа единичных столбцов, т. е. не обладает очевидным начальным опорным решением.
Для нахождения опорного плана переходим к М-задаче:
f(X) = x1 – 4x4 – Мy1 ® max
x1 – x2 + x3 + x4 = 3x1 + x2 + 2x3 + y1 = 5,
xj ³ 0, j = 1, 2, 3, 4; y1³ 0.
Очевидное начальное опорное решение (0; 0; 0; 3; 5).
Решение осуществляется симплекс-методом с искусственным базисом.
Расчеты оформим в симплекс-таблицах
| Номер симплекс-таблицы | Базис | Cj Ci | B | 1 | 0 | 0 | -4 | -M | Q |
| A1 | A2 | A3 | A4 | P1 | |||||
| 0 | A4 | -4 | 3 | 1 | -1 | 1 | 1 | 0 | 3:1 = 3 |
| P1 | -M | 5 | 1 | 1 | 2 | 0 | 1 | 5:2 = 2,5 | |
| j | - | -5M-12 | -M-5 | -M+4 | -2M-4 | 0 | 0 | ||
| 1 | A4 | -4 | 1/2 | 1/2 | -3/2 | 0 | 1 | 1/2:1/2=1 | |
| A3 | 0 | 5/2 | 1/2 | 1/2 | 1 | 0 | 5/2:1/2=1 | ||
| j | - | -2 | -3 | 6 | 0 | 0 | |||
| 2 | A1 | 1 | 1 | 1 | -3 | 0 | 2 | ||
| A3 | 0 | 2 | 0 | 2 | 1 | -1 | 2:2=1 | ||
| j | - | 1 | 0 | -3 | 0 | 6 | |||
| 3 | A1 | 1 | 4 | 1 | 0 | 3/2 | 1/2 | ||
| A2 | 0 | 1 | 0 | 1 | 1/2 | -1/2 | |||
| j | - | 4 | 0 | 0 | 3/2 | 9/2 |
Начальное опорное решение (0; 0; 0; 3; 5), соответствующее симплекс-таблице 0, неоптимальное, так как в D - строке есть отрицательные значения, наименьшее в столбце А3. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке P1, эта строка направляющая. Направляющий элемент на пересечении направляющих строки и столбца. Столбец P1 выводим из базиса, а А3 - вводим в базис.
При пересчете таблицы столбец Р1 далее можно не рассчитывать.
После пересчета получаем симплекс-таблицу 1. Соответствующее опорное решение (0; 0; 5/2; 1/2; 0) не оптимально, так как в D - строке есть отрицательные значения, в столбце А1.Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А4. В качестве направляющей строки возьмем А4. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А4 выводим из базиса, а А1 - вводим в базис.
После пересчета получаем симплекс-таблицу 2. Опорное решение, соответствующее симплекс-таблице 2 (1; 0; 2; 0; 0) – не оптимально, так как в D - строке есть отрицательные значения, в столбце А2. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А3. В качестве направляющей строки возьмем А3. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А3 выводим из базиса, а А2 - вводим в базис.
После пересчета получаем симплекс-таблицу 3. Опорное решение, соответствующее симплекс-таблице 3 (4; 1; 0; 0; 0) – оптимально, так как в D - строке нет отрицательных значений.
Отбрасывая значения переменной y1, получаем оптимальное решение исходной задачи:
х1 = 4, х2 = 1; х3 = 0; х4 = 0; fmax = 1×4 + 0×1 + 0×0 – 4×0 = 4.
Задача 2.
Задание 1. Сформулировать экономико-математическую модель исходной экономической задачи.
Задание 2. Решить полученную задачу линейного программирования графическим методом.
Задание 3. Сформулировать двойственную задачу и найти ее оптимальное решение, используя теоремы двойственности.
Вариант 2.
Предприятие производит полки для ванных комнат двух размеров А и Б. Служба маркетинга определили, что на рынке может быть реализовано до 550 полок в неделю, а объем поставляемого на предприятие материала, из которого делаются полки, равен 1200 м2 в неделю. Для каждой полки типов А и Б требуется 2 м2 и 3 м2 материала соответственно, а затраты станочного времени на обработку одной полки типа А и Б составляют соответственно 12 и 30 минут. Общий недельный объем станочного времени равен 160 часов, а прибыль от продажи каждой полки типа А и Б составляет 3 и 4 ден. единиц соответственно. Определить, сколько полок каждого типа следует выпускать в неделю для получения наибольшей прибыли.
Решение.
Задание 1.
Обозначим x1 и x2 количество полок типа А и Б, соответственно (план выпуска). Очевидно, x1, x2 ³ 0 и целые.
Так как объем реализации в неделю составляет до 550 полок, то x1 + x2 £ 550.
Расход материала составит 2x1 + 3x2 м2, эта величина не должна превышать запаса материала 1200 м2. Следовательно, должно выполняться неравенство 2x1 + 3x2 £ 1200.
Затраты станочного времени составят 0,2x1 + 0,5x2 час. и не могут быть больше недельного объема 160 час. Следовательно, должно выполняться неравенство 0,2x1 + 0,5x2 £ 160. Чтобы не было дробей, умножим его на 10 и получим 2x1 + 5x2 £ 1600.
Прибыль от реализации полок составит f(X) = 3x1 + 4x2 ден. единиц, и она должна быть наибольшей
Получаем экономико-математическую модель задачи:
Найти максимум функции f(X) при заданных ограничениях
f(X) = 3x1 + 4x2 ® max
x1 + x2 £ 550
2x1 + 3x2 £ 1200
2x1 + 5x2 £ 1600
x1, x2 ³ 0, целые.
Задание 2.
Решаем задачу без условия целочисленности решения. Построим множество допустимых решений задачи.
Прямые ограничения x1,2 ³ 0 выделяют первую четверть плоскости.
Проведем прямую x1 + x2 = 550 через точки (0; 550) и (550; 0). Подставим в первое неравенство координаты точки (0; 0): 1×0 +1×0 = 0 < 550, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.
Проведем прямую 2x1 + 3x2 = 1200 через точки (0; 400) и (600; 0). Подставим в первое неравенство координаты точки (0; 0): 2×0 + 3×0 = 0 < 1200, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.
Проведем прямую 2x1 + 5x2 = 1600 через точки (0; 320) и (800; 0). Подставим в первое неравенство координаты точки (0; 0): 2×0 + 5×0 = 0 < 1600, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.
Множество допустимых решений – это многоугольник ABCDO.
Построим линию уровня целевой функции f(X) = 3x1 + 4x2
3x1 + 4x2 = 0 через точки (200; -150 ) и (-200; 150).
Вектор-градиент {3; 4} задает направление, перемещаясь вдоль которого, можно увеличить значение целевой функции; перемещаясь в противоположном направлении, можно уменьшить ее значение. На чертеже построен вектор, пропорциональный градиенту (60; 80), так как сам градиент имеет малый масштаб на чертеже.
Из чертежа видно, что наибольшее значение целевой функции будет на линии уровня, проходящей через точку С, являющейся пересечением прямых (1) и (2).
Координаты этой точки найдем из системы
x1 + x2 = 550,2x1 + 3x2 = 1200.
Первое уравнение умножим на 2 и вычтем из второго, получаем x2 = 100 и x1 = 450
fmах = 3 ×450 + 4 ×100 = 1750 ден. единиц.
Полученное оптимальное решение оказалось целым, следовательно, это решение поставленной задачи. Получили: в оптимальном плане выпуска следует произвести полок типа А 450 шт., а полок типа Б – 100 шт.При этом прибыль от реализации составит 1750 ден. единиц и будет наибольшей.
 |
Задание 3.
Двойственная задача.
Найти минимум функции g(Y) при ограничениях:
g(Y) = 550y1 + 1200y2 + 1600y3 ® min
y1 + 2y2 + 2y3 ³ 3
y1 + 3y2 + 5y3 ³ 4
y1,2,3 ³ 0.
Оптимальное решение прямой задачи Х = (450; 100). Подставим его в ограничения этой задачи
1×450 + 1×100 = 550
2×450 + 3×100 = 1200
2×450 + 5×100 = 1400 < 1600
Условия дополняющей нежесткости (вторая теорема двойственности): для оптимальных планов двойственных задач имеют место соотношения:
Так как для оптимального решения прямой задачи треть ограничение выполняется как неравенство, то в оптимальном решении двойственной задачи y3 = 0.
Так как для оптимального решения прямой задачи х1 > 0и х2 > 0, то оба ограничения двойственной задачи выполняются как равенство. Для нахождения решения двойственной задачи получаем систему
y3 = 0y1 + 2y2 + 2y3 = 3
y1 + 3y2 + 5y3 = 4
Получаем решение: y1 =, y2 = 1, y3 = 0.
Найдем значение целевой функции двойственной задачи:
g(Y) = 550×1 + 1200×1 + 1600×0 = 1750.
Получили gmin = fmax = 1750 ден. единиц.
Так как значения прямой и двойственной функций равны, то Y = (1; 1; 0) является оптимальным решением двойственной задачи (по первой теореме двойственности).