Графическое решение

Составляем ЗЛП по условиям задачи. Обозначим за x₁ – объем производства продукции А, за x₂ – объем производства продукции В. Тогда целевая функция F, отображающая стоимость всей произведенной продукции, может быть записана как

F=7,5x₁+3x₂®max.

Ограничения по ресурсам запишутся в виде неравенств

2x₁+x₂£150

x₁+5x₂£200

3x₁ £200

при x₁,x₂³0

Рассчитаем точки для построения прямых ограничений (рис. 2.2).

Рис. 2.2. Расчет точек для построения линий ограничений

Граничные условия (неотрицательность переменных x₁ и x₂) определяются первым координатным углом. Поскольку знаки всех неравенств меньше или равно (при положительном коэффициенте при x₂), то область под графиками всех прямых ограничений и ограниченная осями координат есть ОДР данной задачи.

Строим прямую нулевого уровня целевой функции 7,5x₁+3x₂ =0 (рис. 2.3).

Рис. 2.3. Расчет точек линии нулевого уровня целевой функции

Переносим линию целевой функции во все вершины ОДР и определяем точку, в которой она проходит выше, чем в других (рис. 2.4).

Рис. 2.4. Графическое решение ЗЛП

Это точка пересечения прямых, заданных уравнениями 2x₁+x₂=150 и 3x₁=200. Решив систему из этих уравнений, получаем координаты этой точки x₁= и x₂=. Это значит что для оптимального решения нужно выпустить 66,66 кг продукции А и 16,66 кг продукции В. Стоимость произведенной продукции равна

F=7,5×66,66+3×16,66= 594,98 руб.

и показывает максимально возможную прибыль при данных условиях.

Решение ЗЛП симплекс-методом с использованием симплекс таблиц

Приводим общую ЗЛП

F=7,5x₁+3x₂®max

2x₁+x₂£150

x₁+5x₂£200

3x₁ £200

при x₁,x₂³0

к каноническому виду, добавляя в левые части неравенств дополнительные переменные

F=7,5x₁+3x₂®max

2x₁+x₂+x₃=150

x₁+5x₂ + x₄=200

3x₁ + x₅ =200

при x_i³0, i=1…5

и записываем ее в виде 0-уравнений

F=0 – (–7,5x₁ – 3x₂)

x₃=150 – (2x₁+x₂)

x₄=200 – (x₁+5x₂)

x₅ =200 – (3x₁)

Заполняем первую симплекс-таблицу (рис. 2.5).

Рис. 2.5. Первая симплекс-таблица ЗЛП

В индексной строке таблицы есть отрицательные значения, значит, данный план не оптимален. Переходим к построению новой таблицы.

Ищем разрешающий столбец. Максимальное по модулю из отрицательных значений это –7,5. Оно определяет разрешающий столбец таблицы x₁ (в новой таблице эта переменная перейдет в базис).

Для нахождения разрешающей строки таблицы составляем отношения элементов столбца свободных членов к элементам разрешающего столбца и находим из них наименьшее

min (150/2, 200/1,200/3)=200/3=66,6.

Это значение определяет разрешающую строку таблицы x₅.

Разрешающий элемент таблицы находится на пересечении разрешающего столбца и разрешающей строки (x₅./ x₁) и равен 3.

Переходим к новой симплексной таблице.

В ней вместо переменной x₅ в базисе появилась переменная x₁. Строка, соответствующая новой базисной переменной в новой таблице, получается из разрешающей строки предыдущей таблицы делением ее элементов на разрешающий элемент, равный 3.

Другие строки вычисляются согласно пункту 11 приведенного выше алгоритма симплекс-метода. Например, элемент на пересечении строки x₃ и столбца свободных членов равен

150 – (200×2)/3,

элемент на пересечении строки x₃и столбца x₁ равен соответственно

1 – (2×0)/3 и т.д.

Вторая симлекс-таблица имеет вид (рис. 2.6):

Рис. 2.6. Вторая симплекс таблица ЗЛП

Этот план тоже не оптимальный – в индексной строке есть отрицательное значение. Повторяем алгоритм снова и в результате получаем третью таблицу (рис. 2.7).

Рис. 2.7. Оптимальный план решения ЗЛП

Этот план оптимален. Значения базисных переменных x₁ и x₂ равны соответственно 66,66 и 16,66, значения добавленных переменных x₃ и x₄ равно 0. Значение целевой функции равно 594,98. Полученное симплекс-методом решение ЗЛП полностью совпадает с решением задачи, полученным графически.

Поиск по сайту: