<<
>>

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:

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

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

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

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

Пояснение.

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

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

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

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

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

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

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

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

Пример 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.16, 7.17): Таблица 7.16 х4 *5 Свободный V* *2 *з член L -1 -1 1 1 0 4 4 -4 2 в 0 0 4 4 3 0 -1 0 1 3 6 3 -1 0 0 0 5 7 Таблица 7.17 *2 *з х4 *5 Свободный член L 1 -2 0 1 0 2 2 -2 1 1 0 0 2 2 1 1 0 0 1 5 8 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. Задача решена.

<< | >>
Источник: Бережная Е.В., Бережной В.И.. Математические методы моделирования экономических систем: Учеб. пособие. — 2-е изд., перераб. и доп. — М.: Финансы и статистика,2006. - 432 е.. 2006

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

  1. 2.3 АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
  2. 2.1 РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  3. МЕТОД ПРОЕКТОВ ПО РЕШЕНИЮ ЗАДАЧ ЭКОЛОГИЧЕСКОГО ОБРАЗОВАНИЯ И ВОСПИТАНИЯ ПОДРОСТКОВ
  4. 7.1. Задачи линейного программирования
  5. 7.2. Построение экономико- математических моделей задач линейного программирования
  6. 7.3. Графическое решение задачи линейного программирования
  7. 7.6. Методы нахождения опорного решения задачи линейного программирования
  8. 7.7. Экономическая интерпретация решения задачи линейного программирования
  9. 7.8. Двойственные задачи линейного программирования
  10. Транспортные задачи линейного программирования
  11. 10.4. Многоцелевые задачи линейного программирования
  12. 12.2. Аналитический метод решения задач параметрического программирования
  13. § 65. Симплекс-метод решения задач линейного программирования, М-метод