Контрольная работа: Линейное программирование

-

4

0

0

3/2

9/2

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

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

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

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

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

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

х₁ = 4, х₂ = 1; х₃ = 0; х₄ = 0; f_max = 1×4 + 0×1 + 0×0 – 4×0 = 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