Алгоритм симплексного метода включает следующие этапы.

Этап 1. Приведем исходную задачу линейного программирования к каноническому виду. Однако из основных требований к канонической форме задачи линейного программирования является запись функциональных ограничений задачи в виде системы линейных уравнений неотрицательными правыми частями. Это требование вытекает из метода Жордана-Гаусса определения базисного решения системы линейных уравнений. Условие не отрицательности правых частей необходимо для того, чтобы базисное решение было допустимым (опорным).

Каноническая форма данной задачи получается путем введения дополнительных неотрицательных переменных (базисных или балансных):

1→ 0, 8x₁+0, 5x₂+x₃ =400

2→ 0, 4x₁+0, 8x₂+x₄=365

3→ x₁ - x₂ +x₅ =100 (3.6)

4→ x₂+x₆ =350

5→ 16x₁+ 14x₂ =F

x₁, x₆ ≥ 0

В системе (3.6) – x₃, x₄, x₅ и x₆- базисные или балансные переменные, которые превращают неравенства в равенства. Можно дать следующую экономическую интерпретацию базисным переменным. Например, переменная x₃≥ 0 т.е. если ресурс “молоко” используются полностью, то x₃=0; если не полностью, то x₃> 0. Таким образом, x₃-это избыток ресурса “молоко”. Подобным образом можно интерпретировать остальные базисные переменные.

Этап 2. Составление первого опорного плана

Заполняем первый шаг симплексной таблицы

 

В столбцы 1-7 и строки 1-5 записываем коэффициенты при неизвестных и свободные члены системы (3.6). В столбце базисных переменных записываем их обозначения. Так как к началу решения оценки базисных переменных неизвестных даем им значения равные нулю. Оценки свободных переменных (количество выпускаемой продукции) принимаются равными их значениям в целевой функции. Решение задачи линейного программирования в симплексной таблице находится в столбце свободных членов, то есть решения на первом шаге выглядит как:

x =x₂=0; x₃=400; x₄=365; x₅=100; x₆=350

Контрольный столбец служит для проверки правильности решения и представляет собой произведения коэффициентов столбца свободных членов на оценки соответствующих переменных. Сумма этих произведений дает значение целевой функции, в данном случае F (x)=0

Этап 3. Проверка плана на оптимальность

Признаком оптимальности решения задачи является отсутствие положительных значений в строке целевой функции. В нашем случае это условие не выполняется (есть два положительных числа-16 и 14). Следовательно, план не оптимальный и решение надо продолжить.

Этап 4. Определение ведущих столбца и строки

От первого варианта плана, в котором мы ничего не выпускаем, переходим ко второму варианту. Переход осуществляется следующим образом: определяются ведущий столбец и строка (иногда употребляется термин «разрешающий ») и ведущий элемент.

Если посмотреть на строку целевой функции первой итерации (строка 5), то там есть два положительных числа -16 и 14, которые являются коэффициентами целевой функции и представляют собой цены выпускаемой продукции ( c₁ = 16 –цена сливочного мороженого; c₂=14 – цена шоколадного мороженого) то есть на втором шаге мы можем ввести в план, либо выпуск сливочного, либо шоколадного мороженого. Можно ввести в план выпуск сливочного мороженного, т.к это приводит к большому росту дохода ( 16> 14 ). столбец соответствующий этой цифре ( 16 ) называется ведущим.

С математической точки зрения выбор ведущего столбца производится по правилу: ведущий столбец- maх {C_j}

После выбора ведущего столбца приступаем к выбору ведущей строки. Для этого коэффициенты в столбце свободных членов делим на соответствующие коэффициенты ведущего столбца:

=100, и среди них выбираем минимальное значение (100). Строка, соответствующая этому минимуму и будет ведущей.

Почему выбирается минимальное значение? Дело в том, что коэффициенты в столбцах 1-6 и строках 1-4 симплекс- таблицы представляют собой расход ресурса на единицу изделия, а столбец- 7 – это наличие этих ресурсов. То есть отношения, например 400/ 0, 8 =500, означает, что по ресурсу «молоко» мы можем выпустить 500 кг. сливочного мороженого, но при этом не будет выполняться равенство 3 системе (3.6), т.к. x₅≥ 0 Таким образом, мы можем выпускать только 100 кг. сливочного мороженого и эта строка (3) становится ведущей.

С математической точки зрения выбор ведущей строки производится по правилу: ведущая строка → min { }, где a^b_ij – коэффициенты ведущего столбца.

Иногда при выборе ведущей строки получается несколько равных . Это может затруднить вектор ведущей строки и привести к зацикливанию.

В таких случаях для выбора ведущей строки используют метод Креко, который заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения , делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретиться наименьшее частное при чтении таблицы слева на право по столбцам.

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: