183737 (Линейное программирование)

Задача 1.

Решить задачу линейного программирования симплексным методом.

Вариант 2.

Найти наибольшее значение функции f(X) = x₁ – 4x₄ при ограничениях

x ₁ – x₂ + x₃ + x₄ = 3

x₁ + x₂ + 2x₃ = 5,

x_j 0, j = 1, 2, 3, 4.

Решение.

Задача записана в каноническом виде, но не имеет необходимого числа единичных столбцов, т. е. не обладает очевидным начальным опорным решением.

Для нахождения опорного плана переходим к М-задаче:

f(X) = x₁ – 4x₄ – Мy₁ max

x ₁ – x₂ + x₃ + x₄ = 3

x₁ + x₂ + 2x₃ + y₁ = 5,

x_j 0, j = 1, 2, 3, 4; y₁ 0.

Очевидное начальное опорное решение (0; 0; 0; 3; 5).

Решение осуществляется симплекс-методом с искусственным базисом.

Расчеты оформим в симплекс-таблицах

Начальное опорное решение (0; 0; 0; 3; 5), соответствующее симплекс-таблице 0, неоптимальное, так как в - строке есть отрицательные значения, наименьшее в столбце А₃. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке P₁, эта строка направляющая. Направляющий элемент на пересечении направляющих строки и столбца. Столбец P₁ выводим из базиса, а А₃ - вводим в базис.

При пересчете таблицы столбец Р₁ далее можно не рассчитывать.

После пересчета получаем симплекс-таблицу 1. Соответствующее опорное решение (0; 0; 5/2; 1/2; 0) не оптимально, так как в - строке есть отрицательные значения, в столбце А₁.Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А₄. В качестве направляющей строки возьмем А₄. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А₄ выводим из базиса, а А₁ - вводим в базис.

После пересчета получаем симплекс-таблицу 2. Опорное решение, соответствующее симплекс-таблице 2 (1; 0; 2; 0; 0) – не оптимально, так как в - строке есть отрицательные значения, в столбце А₂. Этот столбец будет направляющим. Минимальное положительное оценочное отношение Q в строке А₃. В качестве направляющей строки возьмем А₃. Направляющий элемент на пересечении направляющих строки и столбца. Столбец А₃ выводим из базиса, а А₂ - вводим в базис.

После пересчета получаем симплекс-таблицу 3. Опорное решение, соответствующее симплекс-таблице 3 (4; 1; 0; 0; 0) – оптимально, так как в - строке нет отрицательных значений.

Отбрасывая значения переменной y₁, получаем оптимальное решение исходной задачи:

х₁ = 4, х₂ = 1; х₃ = 0; х₄ = 0; f_max = 14 + 01 + 00 – 40 = 4.

Задача 2.

Задание 1. Сформулировать экономико-математическую модель исходной экономической задачи.

Задание 2. Решить полученную задачу линейного программирования графическим методом.

Задание 3. Сформулировать двойственную задачу и найти ее оптимальное решение, используя теоремы двойственности.

Вариант 2.

Предприятие производит полки для ванных комнат двух размеров А и Б. Служба маркетинга определили, что на рынке может быть реализовано до 550 полок в неделю, а объем поставляемого на предприятие материала, из которого делаются полки, равен 1200 м² в неделю. Для каждой полки типов А и Б требуется 2 м² и 3 м² материала соответственно, а затраты станочного времени на обработку одной полки типа А и Б составляют соответственно 12 и 30 минут. Общий недельный объем станочного времени равен 160 часов, а прибыль от продажи каждой полки типа А и Б составляет 3 и 4 ден. единиц соответственно. Определить, сколько полок каждого типа следует выпускать в неделю для получения наибольшей прибыли.

Решение.

Задание 1.

Обозначим x₁ и x₂ количество полок типа А и Б, соответственно (план выпуска). Очевидно, x₁, x₂ 0 и целые.

Так как объем реализации в неделю составляет до 550 полок, то x₁ + x₂ 550.

Расход материала составит 2x₁ + 3x₂ м², эта величина не должна превышать запаса материала 1200 м². Следовательно, должно выполняться неравенство 2x₁ + 3x₂ 1200.

Затраты станочного времени составят 0,2x₁ + 0,5x₂ час. и не могут быть больше недельного объема 160 час. Следовательно, должно выполняться неравенство 0,2x₁ + 0,5x₂ 160. Чтобы не было дробей, умножим его на 10 и получим 2x₁ + 5x₂ 1600.

Прибыль от реализации полок составит f(X) = 3x₁ + 4x₂ ден. единиц, и она должна быть наибольшей

Получаем экономико-математическую модель задачи:

Найти максимум функции f(X) при заданных ограничениях

f(X) = 3x₁ + 4x₂ max

x₁ + x₂ 550

2x₁ + 3x₂ 1200

2x₁ + 5x₂ 1600

x₁, x₂ 0, целые.

Задание 2.

Решаем задачу без условия целочисленности решения. Построим множество допустимых решений задачи.

Прямые ограничения x_1,2 0 выделяют первую четверть плоскости.

Проведем прямую x₁ + x₂ = 550 через точки (0; 550) и (550; 0). Подставим в первое неравенство координаты точки (0; 0): 10 +10 = 0 < 550, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.

Проведем прямую 2x₁ + 3x₂ = 1200 через точки (0; 400) и (600; 0). Подставим в первое неравенство координаты точки (0; 0): 20 + 30 = 0 < 1200, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.

Проведем прямую 2x₁ + 5x₂ = 1600 через точки (0; 320) и (800; 0). Подставим в первое неравенство координаты точки (0; 0): 20 + 50 = 0 < 1600, так как неравенство выполняется, то выбираем полуплоскость, содержащую эту точку.

Множество допустимых решений – это многоугольник ABCDO.

Построим линию уровня целевой функции f(X) = 3x₁ + 4x₂

3x₁ + 4x₂ = 0 через точки (200; -150 ) и (-200; 150).

Вектор-градиент {3; 4} задает направление, перемещаясь вдоль которого, можно увеличить значение целевой функции; перемещаясь в противоположном направлении, можно уменьшить ее значение. На чертеже построен вектор, пропорциональный градиенту (60; 80), так как сам градиент имеет малый масштаб на чертеже.

Из чертежа видно, что наибольшее значение целевой функции будет на линии уровня, проходящей через точку С, являющейся пересечением прямых (1) и (2).

Координаты этой точки найдем из системы

x₁ + x₂ = 550,

2x₁ + 3x₂ = 1200.

Первое уравнение умножим на 2 и вычтем из второго, получаем x₂ = 100 и x₁ = 450

f_mах = 3 450 + 4 100 = 1750 ден. единиц.

Полученное оптимальное решение оказалось целым, следовательно, это решение поставленной задачи. Получили: в оптимальном плане выпуска следует произвести полок типа А 450 шт., а полок типа Б – 100 шт.При этом прибыль от реализации составит 1750 ден. единиц и будет наибольшей.

Задание 3.

Двойственная задача.

Найти минимум функции g(Y) при ограничениях:

g(Y) = 550y₁ + 1200y₂ + 1600y₃ min

y₁ + 2y₂ + 2y₃ 3

y₁ + 3y₂ + 5y₃ 4

y_1,2,3 0.

Оптимальное решение прямой задачи Х = (450; 100). Подставим его в ограничения этой задачи

1450 + 1100 = 550

2450 + 3100 = 1200

2450 + 5100 = 1400 < 1600

Условия дополняющей нежесткости (вторая теорема двойственности): для оптимальных планов двойственных задач имеют место соотношения: