где множество индексов базисных переменных k-\-1 итерации. В столбце Вх заменяют Хд на Хр, а в столбце С - Сд на Ср.

5. Если все А'+*) == а№-и)0, / = \,п, то новое базисное решение Хг = 4 е/(+*> - оптимальное. В противном случае осуществляют переход ко второму этапу, т. е. выполняют следующую итерацию.

При решении задач минимизации в базис вводят вектор с наибольшей положительной оценкой.

Если в качестве начального базиса выбирают базис из свободных переменных, для которых Ср=0, то оценки для всех небазисных переменных Ah=aoh--Си, а соответствующее значение целевой функции aoo=CiXi=0.

Количество симплекс-итераций N при решении задач линейного программирования зависит в основном от числа ограничений. Обычно \,5inN2m, где т - количество ограничений в исходной сим-плг- таблице.

Пример 1. Найти решение следующей задачи:

тах(2л:,-bXs-bVXj); --Sxg--Зхз < 4;

-Xi - 4X2 + Юхз 7; Xl > О, хг >0. Хз > 0.

Преобразуем модель задачи к каноническому виду, введя остаточные переменные Х4 и xs соответственно в первое и второе ограничения. Каноническая модель задачи примет вид

max (2xi -f Xj -f 7хз); x, + 2x2 + Зхз -- x* = 4; -Xl -4x2-1- 10хз + Х5 = 7; Xi>0, X2>0. Хз>0, X4>0, Xs>0.

Так как вектор Ло > О, a векторы Л7 и л7образуют единичный базис, то задачу можно решить методом симплекс-таблиц. Табл. 7.2 - начальная симплекс-таблица.

/ итерация

Определяем направляющий столбец. Им будет столбец Аз, так как Дз < < Ai < Д2 и Дз < 0: (-7 < -2 < -1). Направляющую строку выбираем из

- 7 1 7 3 10 J ~~10

т. е. направляющей является вторая строка таблицы. Поэтому направляющий элемент Х23 = 10, т. е. из числа базисных переменных выводится Xs, а вводится переменная Хз.

Таблица 7.2

7 260

19 10

13 10

32 10

3 10

4 10

49 10

27 10

38 10

Выполнив первый шаг симплексных преобразований, получим табл. 7.3.

итерация 38

Поскольку минимальная оценка Дг =

-, направляющим столбцом яв-

ляется Лг. Направляющая строка - первая, так как в столбце имеется только один положительный элемент, расположенный в первой строке.

Следовательно, направляющий элемент Хц =-, и из числа базисных

переменных выводится переменная х^, а вводится переменная Xz. Проделав симплексные преобразования, получим табл. 7.4.

/ итерация

Поскольку в индексной строке Д последней таблицы только одни отрицательный элемент Д], столбец Л, является направляющим, и переменная Xi должна быть введена в число базисных переменных. Направляющей строкой будет первая, так как

19 15 1 19

19 15 1 19 13 1 J ~ 13

Поэтому элемент Хц =

13 1 J 13

направляющий, и нз числа базисных переменных

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

Таким образом, оптимальное решение задачи И = (~-, 0. \ Зна-

\ 13 13 /

чеиие целевой функции, соответствующее оптимальному решению Ооо = -

Таблица 7.4

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

Пример 2. Найти решение задачи

max {3xi - -Ь 2xs + х^); - Xj + 4хз + Xt= 10;

-3xi + 2X2 + Хз - 2x4 = 8; 4xi-X2 -2хз = 4; Xi>Q, X2>0, Хз>0, X4>0.

Строим М-задачу:

шах (3xi - Xs -f 2x3 -b X4 - My, - AIf/2 - AfJ/s); 2xi - X2 -b 4хз + X4 + yi= 10; -3x, + 2x2-b Хз - 2x4-f = 8; 4xi - X2 -2x3 + 3 = 4;

Xi>0, X2>0, Хз>0, X4>0, г/,>0, г/2>0, г/з>0. ,

Исходная симплекс-таблица - табл. 7.6. .

* I итерация

Наименьшей является оценка Д1 = -ЗМ - 3. Поэтому переменная Xi должт на быть введена в число базисных. Так как min

f 10 4

in <-,-

I 2 4

=-, то из числа

базисных переменных выводится г/з. Проделав симплексные преобразования о направляющим элементом X31, получим табл. 7.7.

итерация

Наименьшей является оценка Дз = -- Ж--Поэтому переменная Хз

должна быть введена в число базисных. Так как в столбце a3 только один элемент Xi3 > О, то из числа базисных переменных выводится у а Xi3 = 5 - направляющий элемент.

Таблица 7.6

Таблица 7.8

Таблица 7.9

Проделав симплексные преобразования, получим табл. 7.8.

/ итерация

В строке Д только один отрицательный элемент Да =--Ж - ---,

5 10

а в столбце А2 только один положительный элемент Х22 = --. Проделав сим-

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

IV итерация

Поскольку в таблице имеется оценка д4 = 59 31

/ 19 59 31 \

< О, то рещение

6 12 / оптимальное. В число базисных переменных вводится Xt, а выводится переменная Xs. Проделав симплексные преобразования, получим табл. 7.10.

Все элементы строки Д положительны. Поэтому получено оптимальное рещение X = (28, 108, О, 62), которому соответствует оптимальное значение целевой функции Ооо = 38.

Двойственность в линейном программировании

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

Если £ -оптимальный базис.одной из задач и Св - вектор коэффициентов ее целево1функции, то оптимальное решение двойственной задачи равно СвВ~. Поэтому, если в двойственной задаче число ограничений меньше, чем в исходной, то эффективность вычислительного процесса при ее решении будет выше.

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

Пусть задана исходная задача в канонической форме

max Хо - 2 jXj 3=1

(7.45) 197

при ограничениях

п

2] ацХ] = Що, i = 1, m; (7.46)

Xj>0.j=l,n. (7.47)

Ей соответствует двойственная задача

т

min Уо = 11 агоУг (7.48)

при ограничениях

i:aijyi>Cj, j = 1,п; (7.49)

Уг - произвольные для i = 1,т. (7.50)

Если исходная задача является задачей минимизации, то двойственная задача будет иметь вид

т

max = Z г-оУг (7.51)

при ограничениях

2 aijyi < Cj, j = l,n; (7.52)

У г - произвольные для i = I, т. (7.53)

Частным случаем рассмотренных задач являются симметричные двойственные задачи:

Исходная задача Двойственная задача

. . - - п т

шах Хо = 2 зХу, min Уо = Л атУи

5=1 г=1

2] aijXj < ttio, i= l,m; а^уг > с ] = l,n;

3=1 г=1

Xj > О, / = 1, П. о, I == 1, т.

Правила построения двойственной задачи:

1. Каждому i-y ограничению исходной задачи соответствует переменная у^ двойственной задачи и наоборот, каждому /-у ограничению двойственной задачи соответствует переменная лс,- исходной задачи.

] 2. Матрица А ограничений исходной задачи и матрица А ограничений двойственной задачи взаимно транспонированы: строка коэффициентов г, в /-ОМ ограничении двойственной задачи является столбцом коэффициентов при Xj в ограничениях исходной задачи и наоборот.

3. Свободные члены ограничений одной из задач являются коэффициентами при соответствующих переменных в целевой функции другой задачи; максимизация меняется на минимизацию и наоборот.

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

5. Каждому t-y ограничению-неравенству исходной задачи в двойственной задаче соответствует условие неотрицательности yiO, а равенству - переменная без ограничений на знак ( произвольная ) .

Пример 1. Построить двойственную задачу к исходной, заданной в каиони-ческой форме:

max Xq = -3xi -f- 5x2 + xs - xi

при ограничениях

ЗлТ]-f-8X2-f-Хз-f-4 = 50; 5xi - 4X2 -Хз-f-X4 = 14;

Xl>0, X2>0, Хз>0, X4>0.

Г- 1веиная задача . ,

min I/O = 50i/i -b 14i/2 .

при ограничениях v

- Зу1 + 5у2>-3; 8(/i -4j/2>5; J/i -i/2>l; у1 + у2>-1, где у, к у2- произвольные.

Пример 2. Построить двойственную задачу к исходной, заданной в форме общей модели:

min Хо = Xl - 2x2 +хзх4 + xi

при ограничениях

х, -2x2-bX3-f-3x4 -2X5 = 6; 2xi-Ь 3x2 - 2x3 - Х4-f-Х5 < 4;

- ,1

Xl -t- Зхз - 4X5 > 8; xj > О, /=1,5. Двойственная задача .,.; !

max уо = 6г/, - 4у2 + 8уз .

при ограничениях

У1-2у2 + Узи -2(/, - Зг/2-t-Ог/з < -2; У, ~ 2у2 + Зуз 1; Зу1+У2 + 0уз<~1; ~2у1~У2 - 4уз1, где i/2 > 0; /3 > О; ji - произвольный.

Рассмотрим двойственную задачу к исходной о составлении бетона, приведенной выше. Модель исходной задачи:

при ограничениях

4 . , .

min 2] CjX]

7=1

Z,aijXibi, 1 = 1,3; 3=1

Xj>0, }== 1,4,

где Xj - искомые количества сырья /-го вида (j=T~4); Cj - стоимость единицы сырья /-го вида; bi - количество компонента i-ro вида сырья, не меньше которого должно содержаться в бетоне (/-

- 1,3); Uij - количество единиц компонента t-ro вида в сырье /-го вида.

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

Модель двойственной задачи:

max Д] ЬгУ{

прн ограничениях

JaijyiCj, j =1,4;

Уг>0,1=1.3.

Экономическая интерпретация полученной двойственной задачи: yi - стоимость (ценность) единицы t-ro вида компонента бетона (t=l,3);

2j С1гзУг - стоимость (ценность) вссх трсх компонснтов в сырье

/-ГО вида. Эта стоимость не должна превышать стоимости единицы сырья /-Г0 вида:

Е aim < Cj.

Стоимость всех компонентов сырья всех видов, вошедших в бетон,

т. е. ценность бетона, равна 2 b i/t-

Таким образом, необходимо определить стоимость (ценность) единицы каждого t-ro вида компонента бетона уг, i=l, 3, так, чтобы стоимость всех компонентов сырья /-го вида (/=1,4), содержащегося в единице сырья, не превышала стоимости единицы сырья этого вида и ценность бетона была максимальной. Часто У{ называют теневыми стоимостями.

Теоремы двойственности. Теоремы двойственности утверждают . следующие положения:

1. Если исходная и двойственная к ней задачи имеют допустимые решения, то существуют оптимальные решения и исходной, и двойственной задач, а значения целевых функций при оптимальных решениях совпадают:

3=1 i=l

где х°. и у° - компоненты векторов оптимальных решений: Х° = = (л^ лО.Д.л ) и уо= (i/ i/ ..,i/° ) соответственно.

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

3 Если исходная (двойственная) задача линейного программи-оования имеет неограниченное оптимальное решение, то соответствующая двойственная (исходная) задача не имеет ни одного допустимого решения.

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

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

гфаведливость приведенных утверждений вытекает из следующего.

Умножим каждое i-e ограничение исходной задачи на соответствующую компоненту yiO допустимого решения двойственной задачи, а каждое /-е ограничение двойственной задачи на соответствующую компоненту XjO допустимого решения исходной задачи. Сложив отдельно правые и соответственно левые части полученных соотношений, получим:

т п т

ZI yi (ZI aXj) < ZI (iioyi-,

i=l 3=1 i=l

n m n

Z Xj (Z o-ayi) > Z C3X3. 3=1 i=i 3=1

Выражения в левых частях полученных соотношений равны, поэтому

п т

Z (]Хз < Z J0№. 3=1 j=l

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

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

y°(Z i°-M - О, f= l,m; 3=1

где х9. и у° - компоненты векторов оптимальных решений соответ-ственно исходной и двойственной к ней задачи;

Таким образом, если при подстановке компонентов оптимального решения в систему ограничений исходной задачи t-e ограничение обращается в неравенство, то i-я компонента оптимального решения двойственной задачи равна нулю. Если 1-й компонент оптимального решения двойственной задачи положителен, то t-e ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство.

Аналогично, если при подстановке компонентов оптимального решения в систему ограничений двойственной задачи j-e ограничение обращается в неравенство, то /-й компонент оптимального решения исходной задачи равен нулю. Если /-й компонент оптимального решения исходной задачи положителен, то j-e ограничение двойственной задачи удовлетворяется ее оптимальным решением как строгое равенство.

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

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

Каждому вектору X соответствует допустимое решение двойственной задачи, причем каждому следующему вектору - лучшее, чем предыдущее.

Оптимальному решению исходной задачи соответствует оптимальное решение двойственной задачи. Таким образом, двойственный симплекс-метод-Это применение обычного симплекс-метода к двойственной задаче, дополненное построением на каждой итерации п-мерного вектора X, являющегося почти допустимым опорным решгением исходной задачи.

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

1) начальное опорное допустимое базисное решение не очевидно, для его определения необходимо использовать специальные методы, например метод искусственных переменных, метод Данцига;

2) после получения решения задачи линейного программирова-