й случай. ЗЛП представлена в симметрической форме записи

Тогда система ограничений имеет вид

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

системы ограничений дополнительные переменные (). Тогда

система ограничений примет предпочтительный вид:

Отсюда получаем начальный опорный план:

.

В целевую функцию дополнительные переменные вводятся с ко­эффициентами, равными нулю: ().

Пример 4. Найти начальный опорный план

Решение. Приведем задачу к каноническому виду:

Система ограничений имеет предпочтительный вид. Начальный опорный план .

3-й случай. Пусть система ограничений имеет вид

Сведем задачу к каноническому виду, добавив к левым частям

системы ограничений дополнительные переменные ():

Теперь система ограничений, вообще говоря, не имеет предпочти­тельного вида. В этом случае вводят искусственный базис путем перехо­да к М-задаче:

где в целевой функции знак ««относится к задаче максимизации. Если некоторые из уравнений исходной системы ограничений имеют предпочтительный вид, то в них не вводят искусственные переменные. Начальный опорный план M-задачи имеет вид

Z() = 0.

Между оптимальными планами исходной задачи и M-задачи име­ется следующая связь: если в оптимальном плане M-задачи все искус­ственные переменные равны нулю, то значения оставшихся коорди­нат плана дадут оптимальный план исходной задачи.

Нахождение оптимального опорного плана. Начальный опорный план ₀ исследуется на оптимальность:

1) если в Z -строке нет отрицательных элементов (не считая свободного члена) — план оптимален. Если в Z -строке нет также и нулевых элементов, то оптимальный план единственный; если же среди элементов есть хотя бы один нулевой, то оптимальных планов бесконечное множество.

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

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

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

Пример5. Решить симплекс-методом задачу

Решение: Задача записана в канонической форме, но два свободных члена отрицательны, поэтому перед тем как записать задачу в форме таблицы, умножим первое и второе уравнения на (-1).

А теперь будем перебрасывать нули из левого столбца на верх таблицы. Для первого шага жорданова исключения возьмем разрешающим, например, четвертый столбец (в нем есть положительные элементы!). Разрешающая строка определится по минимальному из отношений: 4/1 и 7/1. В данном случае min(4/1;7/1)=4/1 и соответствует первой строке, она и будет разрешающей.

Таб.1

0= 0= 0=	4 7	1 1 1 1 0 1 2 1 0 1 2 1 0 1 1
Z =		3 1 0 0 0

Таб.2

= 0= 0=		1 1 1 0 1 2 1 1 3 0 1 1
Z =		3 1 0 0

Таб.3

= 0= =		1 1 1 4 2 2 3 0 1
Z =		3 1 0

Таб.4

= = =		1 2 2 1 1 1
Z =		3 1

Сделав еще два шага жордановых исключений (таб.2 таб.3) приходим к таб.4, в левом столбце которой уже нет нулей: базис выделен. Ему соответствует начальный опорный план: =(0; 0; 2; 2; 5). Найденный нами опорный план неоптимален, т.к. в Z -строке присутствует отрицательный элемент ( 3). В соответствующем ему столбце имеются положительные элементы, поэтому есть возможность улучшить план (таб.5).

Таб.5

= = =		1 2 2 3 1 3
Z =		3 5

Однако и этот план неоптимален, т.к. в Z -строке присутствует отрицательный элемент ( 5). Сделав еще один шаг, получаем таб.6., в Z -строке которой нет отрицательных элементов.

Таб.6

= = =
f=		4/3 5/3

Значит, содержащийся в таб.6 опорный план является оптимальным. Итак, =(4; 1; 9; 0; 0), f _max=16. Задача решена.

Замечание: если ЗЛП задана в симметрической форме записи, то введя дополнительные переменные, ее можно привести к канонической форме, и решать по предложенному алгоритму.

Список литературы

1 Кузнецов, А. В. Руководство к решению задач по математическому программированию: учеб. пособие /А. В. Кузнецов, Н. И. Холод, Л.С. Костевич. – 2-е изд., перераб и доп. – Минск: Выш. шк., 2001. – 448 с.

2 Унсович, А. Н. Краткий курс высшей математики для экономистов / А. Н. Унсович – Барановичи: БНИП, 2000. – 531 с.