Бережная_Матметоды моделирования эк cистем

В последней строке нет положительных элементов, следова­ тельно, оптимальное решение найдено:

^min = — 9; ^ = (0; 0; 2; 1; 1); Z^^x "^ ~ -^min ~ 9.

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

Метод искусственного базиса

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

^1 = Pi -(Щ r+l^r+l +^1 r+2^r+2 + - + OCi^X^);

2min = YO - (Yr+l^rf 1 + Yr+2^rf2 + - + Уп^п)-

При этом Pi > о, ..., P^> о, тогда, положив свободные неизвест­ ные х^+1, Xf^2y ^п равными нулю, получаем опорное решение

^1 ^ Рь ^2 "^ Рг» -у ^г ^ Рг

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

220

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

yi^bi -(aiixi •\-ai2X2 +... + fli^^;,);

(7.43)

Уг =*r "(^rl^l +^г2^2 +... + Л,71^л)-

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

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

^1 = P l - ( « I r + l ^ r + l + a i r + 2 ^ r + 2 + - + «1/7^/;+^11Л+- + ^гД^г);

Хг =Р^ -{0.rr+\Xr^\ +СХ;.^+2^г+2 +... + СХ^^„ ^СгхУх +... + С^^>'^).

От системы (7.43) к системе (7.44) всегда можно перейти шага­ ми симплекс-метода. При таком переходе в качестве линейной формы рассматривают ф)шкцию

равную сумме искусственных переменных. Переход заканчивают, когда F^^^ = О и все искусственные переменные у/ переведены в свободные неизвестные.

Анализ вариантов решений

1. Если jFjnin ^ О, а все у^ переведены в свободные переменные, то задача не имеет положительного решения.

2. Если F^^^ = О, а часть yi осталась в базисе, то для перевода их в свободные переменные необходимо применять специальные приемы.

221

в симплекс-таблице, соответствующей системе (7.44), после то­ го как /'min == 0> а все у/ ~ свободные, вычеркивают строку для Z'^jn и столбцы для У1 и решают задачу для исходной линейной формы

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

симплекс-методом. Для нахождения опорного плана использовать ме­ тод искусственных переменных.

Ограничения:

|3xi - 5x2 "^^3 "^2x4 =1» \2х\ - 2 Х 2 + Х 4 - Х 5 = - 4 ; I Х\ — 3X2 "Ь 2X4 "" ^5 ~ "~^*

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

2min = ^1 + 2x2, ^/ ^ о, / = 171.

В базис можно вьщелить переменную Ху Введем две искусст­ венные переменные — >'i и У2*

^min = о - (-^1 - 2x2);

^min = Д'! + У2 = 9 - (-3X1 + 5X2 ^ ЗХ4 + 2X5).

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

222

Наименьший положительный элемент в строке линейной фор­ мы F^ij^ = 2. Разрешающий элемент находится на пересечении столбца переменной х^ и строки переменной yi.

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

Таблица 7.10

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

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

Так как F^^in = О, а 3/1 и У2 переведены в число свободных, пере­ ход к первому опорному решению завершен. Строку, соответству­ ющую F^^in» и столбцы переменных у^ и У2 вычеркиваем в послед­ ней таблице и переписываем ее в новом виде (табл. 7.12):

223

т

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

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

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

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

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

«11^1+«12^2+- + «i/i^«=*i;

(7.46)

224

(7.47)

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

ощ Ьх

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

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

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

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

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

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

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

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

225

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

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

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

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

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

Пример 7.14. Определение опорного плана. Дана следующая система:

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

-Х1~Х2+хз+Х4=4;

-Xi + 2X2 + -^3 + ^5 = '7» 2xj — Х2 + Х4 "Ь Х5 — f\

^max = 3Xi - Х2 + 5.

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

Выберем произвольно столбец с положительным элементом. Затем по минимальному положительному отношению находим раз­ решающий элемент. В нашем примере он равен 1 и находится на пересечении столбца переменной Х4 и первой строки (элемент от­ мечен квадратом). Выполняя преобразования Жордана-Гаусса, по­ лучим табл. 7.15.

226

т

Выполняя в дальнейшем все действия алгоритма, получим ряд следующих аналогичных таблиц (табл. 7,16, 7.17):

227

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

Запишем нашу задачу из табл. 7.17 так:

Получено первое допустимое решение, выделим его. Для этого положим Xj = 0; Х2= О, тогда X = (0; 0; 2; 2; 5); Z^^^ "^ 5.

Задача решена.

7.7. Экономическая интерпретация решения задачи линейного программирования

Любая экономико-математическая модель лишь упрощенно, грубо отображает реальный экономический процесс, и это упроще­ ние существенно сказывается на получаемых результатах. Исследо­ вателя вряд ли устроила бы заключительная симплекс-таблица, из которой можно было бы получить только список переменных и их значения. На самом же деле результирующая симплекс-таблица «насыщена» весьма важными данными, лишь небольшую часть ко­ торых составляют оптимальные значения переменных. Из симп­ лекс-таблицы можно получить информацию относительно:

•оптимального решения;

•статуса ресурсов;

•ценности каждого ресурса;

•чувствительности оптимального решения к изменению запа­ сов ресурсов, вариациям коэффициентов целевой функции и ин­ тенсивности потребления ресурсов.

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

Для иллюстрации возможностей получения указанной выше информации из заключительной симплекс-таблицы воспользуемся опять задачей об ассортименте продукции (пример 7.2). Эта задача формулируется следующим образом:

228

Оптимальная симплекс-таблица имеет вид (табл. 7.18):

В таблице y^.j = 1,4 — выравнивающие переменные.

Оптимальное решение. С точки зрения практического использо­ вания результатов решения задач линейного программирования классификация переменных на базисные и небазисные не имеет значения и при анализе оптимального решения может не учиты­ ваться. Переменные, отсутствующие в симплекс-таблице в столбце «базисные переменные», обязательно имеют нулевое значение. Зна­ чения остальных переменных приводятся в столбце «свободные члены».

При интерпретации результатов оптимизации в задаче об ас­ сортименте продукции нас прежде всего интересуют объемы про­ изводства продукции П^ и Я2, т. е. значения управляемых перемен­ ных Xj и Х2. Используя данные, содержащиеся в симплекс-таблице для оптимального решения, основные результаты можно предста­ вить в следующем виде (табл. 7.19):

229