Метод искусственного базиса, страница 2

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

При решении задач целесообразно соблюдать следующие рекомендации:

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

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

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

4.2 Пример решения задачи методом искусственного базиса

Решим двухэтапным методом искусственного базиса задачу из раздела 1.3.1. Для этого ее надо вначале привести к канонической форме:

min 4х₁ + 15х₂ + 40х₃

380х₁ + х₂ + 2х₃ – х₄ = 4

380х₁ + х₂ + 2х₃ + х₅ = 6

90х₂ + 50х₃ – х₆ = 110

20х₂ + 80х₃ + х₇ = 25

х₁ + х₂ + х₃ = 0,5

х_1-7 ³ 0

Здесь дополнительная переменная х₄ представляет собой превышение содержания кальция в рационе над минимально допустимым, а х₅ показывает, на сколько оно ниже максимально допустимого. Переменная х₆ показывает, на сколько содержание белка в рационе больше минимально допустимого, а  х₇ – на сколько меньше содержание клетчатки по сравнению с максимально допустимым. Все эти величины измеряются в граммах.

В этой задаче свободные члены неотрицательны. Имеется часть базиса, а именно единичные столбцы стоят при двух переменных – х₅ и х₇ (во втором и четвертом ограничениях). В остальных трех уравнениях базисных переменных нет, поэтому введем три искусственные переменные и построим расширенную задачу для реализации двухэтапного симплекс-метода следующим образом:

min у₁ + у₂ + у₃

380х₁ + х₂ + 2х₃ – х₄ + у₁ = 4

380х₁ + х₂ + 2х₃ + х₅ = 6

90х₂ + 50х₃ – х₆ + у₂ = 110

20х₂ + 80х₃ + х₇ = 25

х₁ + х₂ + х₃ + у₃= 0,5

х_1-7 ³ 0

у_1-3 ³ 0

Решим расширенную задачу обычным симплекс-методом. Тогда исходная таблица примет вид таблицы 14.

Таблица 14 – Исходная симплексная таблица для расширенной задачи

Так как задача на минимум, здесь критерий оптимальности нарушен в столбцах при трех первых переменных (в критериальной строке в них стоят положительные коэффициенты). В качестве разрешающего можно выбрать любой из них. Выберем, например, столбец x₂. Тогда из базиса выйдет переменная у₃. Следующая таблица будет иметь вид таблицы 15.

Таблица 15 – Вторая симплексная таблица для расширенной задачи