Этап 1. Приведем исходную задачу линейного программирования к каноническому виду. Однако из основных требований к канонической форме задачи линейного программирования является запись функциональных ограничений задачи в виде системы линейных уравнений неотрицательными правыми частями. Это требование вытекает из метода Жордана-Гаусса определения базисного решения системы линейных уравнений. Условие неотрицательности правых частей необходимо для того, чтобы базисное решение было допустимым (опорным).
Каноническая форма данной задачи получается путем введения дополнительных неотрицательных переменных (базисных или балансных):
1→ 0,8x1+0,5x2+x3 =400
2→ 0,4x1+0,8x2 +x4 =365
3→ x1 - x2 +x5 =100 (3.1)
4→ x2 +x6 =350
5→ 16x1+ 14x2 =F
x1, x6 ≥0
В системе (3.1) – x3, x4, x5 и x6- базисные или балансные переменные, которые превращают неравенства в равенства. Можно дать следующую экономическую интерпретацию базисным переменным. Например, переменная x3≥0 т.е. если ресурс “молоко” используются полностью, то x3=0; если не полностью, то x3>0. Таким образом, x3-это избыток ресурса “молоко”. Подобным образом можно интерпретировать остальные базисные переменные.
Этап 2. Составление первого опорного плана
Заполняем первый шаг (первую) симплексной таблицы (табл.3.1)
В столбцы 1-7 и строки 1-5 записываем коэффициенты при неизвестных и свободные члены системы (3.1). В столбце базисных переменных записываем их обозначения. Так как к началу решения оценки базисных переменных неизвестных даем им значения равные нулю. Оценки свободных переменных (количество выпускаемой продукции) принимаются равными их значениям в целевой функции. Решение задачи линейного программирования в симплексной таблице находится в столбце свободных членов, то есть решения на первом шаге выглядит как:
x =x2=0; x3=400; x4=365; x5=100; x6=350
Контрольный столбец служит для проверки правильности решения и представляет собой произведения коэффициентов столбца свободных членов на оценки соответствующих переменных. Сумма этих произведений дает значение целевой функции, в данном случае F (x)=0
Этап 3.Проверка плана на оптимальность
Признаком оптимальности решения задачи является отсутствие положительное значений в строке целевой функции. В нашем случае это условие не выполняется (есть два положительных числа-16 и 14). Следовательно, план не оптимальный и решение надо продолжить.
Этап 4. Определение ведущих столбца и строки
От первого варианта плана, в котором мы ничего не выпускаем, переходим ко второму варианту. Переход осуществляется следующим образом: определяются ведущий столбец и строка (иногда употребляется термин «разрешающий ») и ведущий элемент.
Если посмотреть на строку целевой функции первой итерации (строка 5), то там есть два положительных числа -16 и 14, которые являются коэффициентами целевой функции и представляют собой цены выпускаемой продукции (c1 = 16 –цена сливочного мороженого; c2=14 – цена шоколадного мороженого) то есть на втором шаге мы можем ввести в план, либо выпуск сливочного, либо шоколадного мороженого. Можно ввести в план выпуск сливочного мороженного, т.к это приводит к большому росту дохода (16>14). столбец соответствующий этой цифре (16) называется ведущим.
С математической точки зрения выбор ведущего столбца производится по правилу: ведущий столбец- maх {Cj}
После выбора ведущего столбца приступаем к выбору ведущей строки. Для этого коэффициенты в столбце свободных членов делим на соответствующие коэффициенты ведущего столбца:
=100,и среди них выбираем минимальное значение (100). Строка, соответствующая этому минимуму и будет ведущей.
Почему выбирается минимальное значение? Дело в том, что коэффициенты в столбцах 1-6 и строках 1-4 симплекс- таблицы(3.1) представляют собой расход ресурса на единицу изделия, а столбец- 7 – это наличие этих ресурсов. То есть отношения, например 400/ 0,8 =500, означает, что по ресурсу «молоко» мы можем выпустить 500 кг. сливочного мороженого, но при этом не будет выполняться равенство 3 системе (3.1), т.к. x5≥0 Таким образом, мы можем выпускать только 100кг. сливочного мороженого и это строка (3) становится ведущей.
С математической точки зрения выбор ведущей строки производится по правилу: ведущая строка → min {}, где abij – коэффициенты ведущего столбца.
Иногда при выборе ведущей строки получается несколько равных. Это может затруднить вектор ведущей строки и привести к зацикливанию.
В таких случаях для выбора ведущей строки используют метод Креко, который заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения , делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретиться наименьшее частное при чтении таблицы слева направо по столбцам.
Элемент симплексной таблицы, находящейся на пересечении ведущей строки и ведущего столбца, называется ведущим или разрешающим.
Этап 5.Построение нового опорного плана.
Переход к новому осуществляется в результате пересчета симплексной таблицы методом Жордана - Гаусса.
Разделим все элементы ведущей строки предыдущей симплексной таблицы на ведущий элемент и результаты деления занесем в строку следующей симплексной таблицы. В результате этого на месте разрешающего элемента в следующей симплексной таблице запишем 1, а в остальных клетках j столбца, включая клетку столбца целевой функции, записываем нули (табл. 3.2).
Таблица 3.2
Если в ведущем столбце есть нулевой коэффициент, то соответствующая ему строка переносится в следующую итерацию без изменений (строка 4 первой итерации) (табл. 3.2).
Кроме этого на втором шаге свободная переменная, соответствующая ведущему столбцу (x1), заменяет базисную переменную, соответствующую ведущей строки (x5) (табл. 3.2) вместе со своей оценкой.
Остальные коэффициенты пересчитываются по правилу прямоугольника следующим образом. Для каждого преобразуемого коэффициента строится прямоугольник, две противоположных вершины которого образуют преобразуемый и ведущий коэффициент. Вычисления производятся так: новое значение преобразуемого коэффициента равно его старому значению минус произведение коэффициентов, стоящих на противоположной диагонали и деленные на ведущий коэффициент.
Например, нам необходимо найти новое значение коэффициента a152 =14 на втором шаге (табл.3.3).
Таблица 3.3
Прямоугольник для него будет:
Тогда:
a252 = a152 – =14- =30
Также находим значения всех коэффициентов на втором шаге (табл. 3.4).
Таблица 3.4
Таким образом, на втором шаге (второй итерации) мы получили следующий план (табл. 3.4):
- выпускается 100 кг сливочного мороженого (x1=100); шоколадное не выпускается (x2=0);
- избыток наполнителя составляет 325 кг (x4=325);
- спрос на сливочное мороженое удовлетворяется полностью (уравнение 3 системы 3.1 (x1-x2=100; 100-0=100, т.е. x5=0);
- избыток спроса на шоколадное мороженое составляет 350 кг (x6=350);
- доход составляет 1600 руб.
Далее возвращаемся к этапу 3 и проверяем полученный план на оптимальность. Из строки целевой функции видно, что она содержит положительный коэффициент c 52 = 30 (табл. 3.4), т.е. план не оптимальный и его можно улучшить путем введения в план выпуск шоколадного мороженого (x2), так как любое значение x2>0 увеличивает значение целевой функции.
Выполняя последовательно этапа 3-5, получаем окончательную симплексную таблицу (3.5)
Таблица 3.5
В этой таблице все коэффициенты в строке целевой функции отрицательные или равные нулю, т.е. полученный план оптимален, т.е. нет ни одной переменной, введение которой в план увеличилось бы значение целевой функции в 9200 руб.