7.6. Методы нахождения опорного решения задачи линейного программирования

Сформированный выше алгоритм симплекс-метода можно при-менять лишь в том случае, если выделено первое допустимое решение, т. е. исходная задача линейного программирования приведена к виду

х\ = Pl -(air+l*r+l +а1 r+2xr+2 +•..

Хг =рг -(агг+1*г+1 + агг+2*г+2 + - +

2min = Yo - (Yr+l*r+l + Yr+2*r+2 + - + У^п)-

При этом pj > 0, ..., pr> 0, тогда, положив свободные неизвестные хг+1, хг+2» хп равными нулю, получаем опорное решение

*1 = Рь х2 = *г = Рг

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

1 1 + 0і2*2+-+*ІІІ*іі=

ariXl+ar2X2+... + aniX„=br.

Перепишем систему (7.42) в другом виде. Для этого введем искусственные переменные Ух, у2, ••> У г так> чтобы был выделен базис. Тогда система примет вид

У\=Ь[ ~(а\ххх +012*2 +

yr = br -(дгі*і +аг2х2 + ... + в/ихя).

Системы (7.42) и (7.43) будут эквивалентны в том случае, если все yh для і = 1,г будут равны 0. Кроме того, мы считаем, что все bj > 0 для і = 1,г. В противном случае соответствующие ограничения из системы (7.42) умножим на — 1. Для того чтобы yt были равны 0, мы должны преобразовать задачу таким образом, чтобы все искусственные переменные у і перешли в свободные неизвест-ные.

В этом случае система (7.43) после преобразования примет вид:

В симплекс-таблице, соответствующей системе (7.44), после того как = 0, а все yt - свободные, вычеркивают строку для и столбцы для у і и решают задачу для исходной линейной формы

7 . ^mirr

Рекомендуется вводить минимум искусственных переменных. Пример 7.13. Решение задачи линейного программирования симплекс-методом. Для нахождения опорного плана использовать метод искусственных переменных.

3*1 -5*2 +*з +2*4 =1;

- 2Х\ -ІХ2 +*4 ~х5 х\ +2*4 =-5.

Целевая функция:

Дпіп = х\ + 2Х2, X/ > 0, / = 171.

В базис можно выделить переменную хъ. Введем две искусст-венные переменные — Уі и ,2-

хъ = 1 - (3*! - 5х2 + 2х4);

У\ = 4 - (-2*! + 2х2 - х4 + *5>;

у2 = 5 - (-xj + 3*2 - 2х4 + х5);

^min = 0 - (-Х! - 2Х2);

^min = Л + У2 = 9 - (—ЗХ| + 5*2 - 3*4 + 2х5).

Составим симплекс-таблицу (табл. 7.9):

Таблица 7.9 Свободные ^^неизвестные

Базисные

неизвестные ^ч^ Свобод-ный член х2 х4 х5 *3 1 3 —5 2 0 У\ 4 -2 2 -1 и Уі 5 -1 3 -2 1 V . ^min 0 -1 -2 0 0 ^min 9 -3 5 -3 2

т

Наименьший положительный элемент в строке линейной фор- мы /'mjn = 2. Разрешающий элемент находится на пересечении столбца переменной х5 и строки переменной

Заполним следующую симплекс-таблицу (табл. 7.10):

Таблица 7.10 Свободные ^ч^еизвестные Свобод-ный член *2 х4 У\ Базисные неизвестные *3 1 3 -5 2 0 *5 4 -2 2 -1 1 У2 1 1 и -1 -1 z .

^min 0 -1 -2 0 0 F

1 min 1 1 1 -1 —2 t

Наименьший положительный элемент в строке линейной формы Fmin = 1. Минимальное симплекс-отношение соответствует строке переменной у2.

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

Таблица 7.11 Свободные ^чнеизвестные

Базисные неизвестные Свобод-ный член У2 х4 Ух *3 6 8 5 -3 5 2 -4 -2 1 3 *2 1 1 1 -1 -1 z

^min 2 1 2 -2 -1 F

1 min 0 0 -1 0 -1

Так как Fmin = 0, а у{ и у2 переведены в число свободных, переход к первому опорному решению завершен. Строку, соответствующую Fmin, и столбцы переменных Уі и у2 вычеркиваем в последней таблице и переписываем ее в новом виде (табл. 7.12): ^^^^ Свободные неизвестные Свободный Х\ х4 Базисные член неизвестные *3 6 8 —3 2 —4 1 х2 1 1 -1 z . 2 1 —2

t

Решим задачу для исходной линейной формы Zmin. В табл. 7.12 находим разрешающий элемент. Он равен 8. Выполняя действия согласно алгоритму симплекс-метода, получим табл.

Таблица 7.13 Свободные неизвестные Базисные ^^^^^ неизвестные Свободный член *з х4 6/8 1/8 —3/8 5 4/8 —12/8 х2 2/8 -1/8 -5/8 z 10/8 -1/8 -13/8

В последней строке (Zmin) положительных элементов нет, следовательно, оптимальное решение найдено.

_ Значение целевой функции Zmin равно 10/8. Оптимальный план X = (6/8; 2/8; 0; 0; 5).

Второй алгоритм отыскания опорного плана

Пусть задача линейного программирования записана в каноническом виде:

.: (7.46)

>1*1 + ат2х2 +- + атпхп=Ьт>

^min = cxxx + c^x2 + ... + (7.47)

6,-> 0, i=l,/w, xy >0,y=l,/i.

Построим первую таблицу Жордана—Гаусса для задач (7.46) и (7.47). Для единообразия вычислительной процедуры к исходной таблице приписываем строку целевой функции:

Ьт 0

ахх аХ2 .... аХп

ат\ ат2 •••• атп СХ С2 .... СП

і

(7.48)

2 т

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

Алгоритм метода

Запишем задачу в форме (7.48), при этом все элементы столбца свободных членов bj должны быть неотрицательны 6/ > 0, / = 1,/и. Уравнения системы (7.46), в которых свободные члены отрицательны, предварительно нужно умножить на — 1.

Таблицу (7.48) преобразуем шагами Жордана—Гаусса исключений. При этом на каждом шаге разрешающим может быть вы-бран любой столбец, содержащий хотя бы один положительный элемент. Строка целевой функции на выбор разрешающих столбцов влияние не оказывает.

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

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

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

Пояснение.

Теорема. Если разрешающий элемент выбирать по наименьшему положительному симплекс-отношению, то после шага Жор-

дана—Гаусса свободный член в разрешающей строке становится

положительным, а остальные члены сохраняют свой знак.

Выбор разрешающего элемента производят иначе, а именно.

Просматривают строку, соответствующую какому-либо отрицательному свободному члену. Выбирают в ней какой-либо отрица-тельный элемент — соответствующий этому элементу столбец будет разрешающим.

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

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

Пример 7.14. Определение опорного плана.

Дана следующая система:

Xj + Х2 ~ Хз - Х4 = -4;

х1-2х2-хз-х5=-7; (7.49)

2xj — х2 + х4 + Х5 =7;

Zmaх = 3X1 - + 5; (7.50)

X/ > 0, / = Г7~5.

Два свободных члена в системе ограничений отрицательны, поэтому перед тем, как записать задачу в виде (7.48), умножим соответствующие уравнения (7.49) на —1:

-Х1-Х2+Х3+Х4=4; « -xj + 2х2 + Х3 + х5 = 7;

2xj - х2 + х4 + х5 = 7;

Zmax = 3xj - х2 + 5.

Запишем данную задачу в виде выражения 7.48 и получим табл. 7.14.

Выберем произвольно столбец с положительным элементом. Затем по минимальному положительному отношению находим разрешающий элемент. В нашем примере он равен 1 и находится на пересечении столбца переменной х4 и первой строки (элемент отмечен квадратом). Выполняя преобразования Жордана-Гаусса, получим табл. 7.15. *1 *з *4 *5 Свободный *2 член L -1 -1 1 ш 0 4 4 -1 2 1 0 1 7 10 2 -1 0 1 1 7 10 3 -1 0 0 0 5 7 t

Таблица 7.15

*2 *3 *4 *5 Свободный V член L -1 -1 1 1 0 4 4 -1 2 1 0 1 7 10 3 0 -1 0 ш 3 6 3 -1 0 0 0 5 7 т Выполняя в дальнейшем все действия алгоритма, получим ряд следующих аналогичных таблиц (табл.

На данном этапе расчетов в табл. 7.17 мы получили три нулевых столбца, что соответствует количеству ограничений в примере. Здесь необходимо закончить преобразования Жордана-Гаусса. Запишем нашу задачу из табл. 7.17 так:

Х\ - 2X2 + х4 = 2

-2jq + + = 2 или х\ + х2 + х5 = 5

Х4=2-(Х{ -2х2);

х3=2-(-2Х1+Х2);

х5=5~(Х!+Х2);

Zmax - - х2 + 5;

'шах

2тш * 5 - + х2)-

Получено первое допустимое решение, выделим его. Для этого положим хх = 0; х2= 0, тогда X = (0; 0; 2; 2; 5); Zmax = 5. Задача решена.