Имя материала: Справочник по математике для экономистов

Автор: В.И. Ермаков

9.6. признак оптимальности опорного решения задачи линейного программирования в канонической форме. условие неограниченности целевой функции

По задаче линейного программирования в канонической форме (9.7) — (9.9) всегда можно составить таблицу (табл. 9.1).

Табл. 9.1 называется симплекс-таблицей для задачи (9.7) - (9.9).

Предположим, что a=(d1; йг dn)— некоторое опорное решение задачи (9.7) — (9.9), а векторы Afl, А^, Air образуют его базис. Тогда таблицу (9.1) можно преобразовать методом Гаусса в табл. 9.2.

Прибавим к последней строке табл. 9.2 первую строку, умноженную на у,,, вторую строку, умноженную на у,,, r-ю строку, умноженную на у,,. В результате получим новую табл. 9.3, где dh, d^, dif — координаты опорного решения, соответствующие векторам базиса AiJt Ап, Air.

Здесь 6j, = 5(j=... = 5,=0, а 50=/(^) (значение целевой функции на опорном решении а).

Табл. 9.3, полученная указанным выше способом, называется симплекс-таблицей, приведенной к базису А1{, Ап, Air опорного решения а, а числа 81г <5,,, 8>г, 51г, .... 5t, .... 5„ — оценками этого базиса.

Имеют место следующие утверждения (случай задачи минимизации):

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

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

Предположим, что симплекс-таблица для задачи линейного программирования в канонической форме приведена к базису некоторого опорного решения. Если среди оценок этого базиса имеется положительная оценка <5„ а все остальные элементы 5-го столбца таблицы не положительны, то целевая функция не ограничена снизу на допустимом множестве. (Условие неограниченности целевой функции.)

О Пример. Рассмотрим опорное решение а = (1; 0; 0; 0) задачи

/= — 1 Oxj + х2 — 9хэ + 6х4 (min),

 

*,><U=1,2,3,4.

Приведем симплекс-таблицу для этой задачи к базису А±, А2 опорного решения а:

Среди оценок базиса Alt А2 есть положительная оценка S3 = 1. Значит, утверждать на этом этапе, что я — оптимальное решение, мы не можем.

С другой стороны, возьмем базис Ак, Аъ того же опорного решения ос. Приведя симплекс-таблицу к этому базису, получим 1-1/2 0 3/2 1 О       1/2    1      -1/2 0

0     -1/2   0     -33/2 -10

 

Все оценки базиса Ах, Аг не положительны. Следовательно, ос — оптимальное решение данной задачи. Щ

 

9.7. Решение заданного программирования симплекс-методом

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

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

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

Предположим, что перед выполнением очередного шага симплекс-таблица для задачи (9.7) — (9.9) приведена к базису

А,х,     А^_[у Ajk, Ajk+t,     Ajr. (9.14)

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

Выберем любую из положительных оценок, например <5,>0. В симплекс-таблице, приведенной к б(&Му, рассмотрим элементы

аи, .... а'ь,     a'ks,     а„ (9.15) s-то столбца и соответствующие свободные члены

«*!       dh        dk,        dr. (9.16)

Можно считать, что среди элементов (9.15) есть положительные элементы (в противном случае целевая функция не ограничена снизу на допустимом множестве).

В этом случае необходимо рассмотреть все отношения вида

d,

т, гдеяь>0, (9.17) ai.

т. е. отношения свободного члена к соответствующему элементу s-ro столбца при условии, что последний положителен. Среди отношений (9.17) выбираем наименьшее. Если

d* (d,

6=   =min<- a)s>0

d* К

то симплекс-таблицу приводим к новому базису

А^,     Aiki, As, Ajk+[,     Аіґ (9.18)

т. е. из базиса (9.14) исключаем вектор А>к, а вместо него вводим вектор А,.

Если 0>О (так заведомо случится, если исходное опорное решение не вырождено), то базис (9.18) является базисом нового опорного решения f3 такого, что /(/0 </(<*)•

Если же в=0, то (9.18) является новым базисом исходного опорного решения а.

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

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

Для предотвращения зацикливания необходимо уточнить правило перехода к новому базису. Это сделать можно, например, следующим образом.

Среди оценок базиса (9.14) выбираем положительную оценку с наименьшим номером. Если 5, — такая оценка, а наименьшее из отношений (9.17) определено неоднозначно, берем наименьшее

dK

отношение — с наименьшим номером к.

"it,

О Пример. Для изготовления продукции используют три вида сырья. При этом можно применять любой из четырех способов производства. Запасы сырья, расход и количества производимой продукции за 1 ч работы по каждому способу приведены в табл. 9.4.

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

Обозначаем через Xj время использования у-го способа производства (j=*l, 2, 3, 4); получаем задачу линейного программирования

/= 12хх + 7хг + 18*э + 10*4 (шах),

 

*i + х2+2х3+ *4<30, + 3*2 + 3*3 + 2*4 ^40,

*,>0,у=1, 2, 3,4.

Эту задачу сведем к канонической задаче минимизации: /'= -12*! - 1хг -18л:3 -10*4 (min),

*1 + 2*2 + *э  +xs =1\%,

ху+ *2 + 2*3 + *4 +х6 = 30, *!+ 3*2 + 3л3+2л:4 +*7=40,

Xj&OJ-l, 2, 3, 4, 5, 6, 7,

 

и составим симплекс-таблицу. Симплекс-таблица оказывается приведенной к базису А5, А6, А7 опорного решения осх = (0; 0; 0; 0; 18, 30, 40),при этом/ (а,) = 0.

*1

*i

*3

**

**

*7

 

1

2

1

0

1

0

0

18

1

I

2

1

0

1

0

зо

1

3

3

2

0

0

]

40

12

7

18

10

0

0

0

0

 

Выбираем положительную оценку <5t = 12 и составляем следующие отношения: 18/1, 30/1, 40/1. Так как наименьшее среди них 18/1, то необходимо перейти к базису Av, А6, Ап. Для этого достаточно выполнить жорданово преобразование всей таблицы с ведущим элементом au = 1.

Имеем

 

 

хг

X,

*4

 

 

 

1

2

0

0

0

18

0

-1

1

1

-1

1

0

12

0

1

2

2

-1

0

1

22

0

-17

6

10

-12

0

0

-216

Базис Ах, Аь, А1 является базисом опорного решения а2 = (18; 0; 0; 0; 0; 12; 22). При этом/'(се2) = -216.

Выбираем оценку 54=10>0 и составляем отношения: 12/1, 22/2. Наименьшим среди них является 22/2. Следовательно, переходим к базису Ах, АА, А6. Получим

 

*1

х1

хз

*4

xi

xt

х1

 

1

2

0

1

0

0

18

0

-3/2

0

0

-1/2

1

-1/2

1

0

1/2

1

1

-1/2

0

1/2

11

0

-22

-4

0

-7

0

-5

-326

 

Все оценки базиса Аи А±, А6 не положительны. Следовательно, <х3 = (18; 0,0, 11, 0; 1; 0) — оптимальное решение канонической задачи минимизации. Поэтому /ї = (18; 0; 11) — оптимальное решение исходной задачи. При этом/(/?) = 326.

Таким образом, для того чтобы выпустить наибольшее количество продукции при имеющихся запасах сырья, необходимо в течение 18 ч использовать первый способ производства и в течение 11ч — четвертый. В результате будет произведено 326 единиц продукции. #

ЯЛетод искусственного базиса для отыскания начального опорного решения

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

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

/=Їу>^(шіп), (9.19)

я

£flyxy=*fci = j,2, ...,т, (9.20)

х,>0,7=1,2,...,и. (9.21)

Без ограничения общности можно считать, что 6,^0, i=l, 2, ... ... , т. Для отыскания опорного решения задачи (9.19) — (9.21) строим вспомогательную задачу:

^^(min), (9.22)

1-І

Л

£ OijXj+y,=bi, i= 1, 2,    m, (9.23)

 

x,7>QJ= 1, 2,     n; y&0, i= 1, 2,     m. (9.24)

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

1°. Вспомогательная задача (9.22) — (9.24) всегда имеет оптимальное решение.

2°. Вектор 0=(О; 0; 0; Ь{, Ь2; Ьт) является опорным решением задачи (9.22) — (9.24).

Таким образом, принимая вектор Д за начальное опорное решение, вспомогательную задачу можно решить симплекс-методом. Пусть 0° = (jc?; х\; х°й; уЧ; yf, у°) — оптимальное опорное решение задачи (9.22) — (9.24).

Если уйх—у= ...=yl,=0, то а=(х?; xf,     х°) — опорное ре

шение исходной задачи (9.19) — (9,21), Если же среди чисел у°и

у,       у°т   есть   положительные,   то   исходная задача

(9.19) — (9.231) имеет пустое допустимое множество.

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

9.9. Взаимно двойственные задачи линейного программирования

Взаимно двойственные задачи линейного программирования имеют следующий вид:

£ у,*, (max),    (9.25)   <р = £ Ь,у,(шп), (9.29)

j- 1-І

л          т

£ aiixJ=bil і є I, /£ M =           £ fly^ = yj,jeliJt         (9.30)

='{I,2,...,m},      (9.26) "

£ау*у^„ієМ/,            (9.27)   £auyi>Yj,JeJ,  (2-31)

y-i        .-і

X;^0rjeJ,J^N= y,^0,ieMI.      (9.32)

= {1,2, ...,*},     (9.28)

При этом задача максимизации (9.25) -(9-.28) называется прямой   (или   исходной)   задачей,   а   задача минимизации (9.29) —.(9.32) — двойственной к ней.

Во взаимно двойственных задачах всегда:

оівназадач является задачей максимизации, а другая — задачей минимизации, в системе ограничений задачи максимизации неравенства записаны со знаком ^,в системе ограничений задачи минимизации — со знаком ^;

каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения, при этом ограничению, записанному в виде неравенства, соответствует переменная, связанная условием неотрицательности;

матрица условий одной задачи получается из матрицы условий другой задачи с помощью транспонирования;

коэффициенты целевой функции одной задачи соответственно равны свободным членам системы ограничений другой задали.

О Взаимно двойственными являются следующие задачи:

f=5x1—x2 + 8х3 — х4 (max),         q> — 2yl + Ъуг + 5уъ (min),

j'2x1 + 5x2-x3 + 7x4=2,       f 2y1+y2+y3^5,

x1-x2 + 5x3-x4^3,     J 5yl-y2~y3=-l,

 

xx>0, x3>0;

-Уі + 5у2 + Зу3>Ь,

 

y2>o.

 

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

Если 1=М—{, 2, т), a J=N={1, 2, .., л}, то имеем нессиметричную пару взаимно двойственных задач:

л т

f= I 7;*/(max)>          <? = £ Ь,у,(min),

}-і І-Х я т

£ ацХ}=К i'=l, 2,         т,         £ ацу^, j= 1, 2, и.

Xj^0,j=lt 2, п;

Если /=0, а /=#={1, 2, л}, то получим симметричную пару взаимно двойственных задач:

п т

f= £ уіхі fmin>'           v=£ **л fmin)>

>-1      і- і

£ayx,^6„ /=1, 2, ...; /и,           £ <*ijyi>Vj,J=l> 2> ••••

Xj^0,j=l,2,...,n; y^O, f=l, 2, т.

 

Простейшие свойства взаимно двойственных задач

1 °. Если а — допустимое решение прямой задачи (9.25) — (9.28), а /} — допустимое решение двойственной задачи (9.29)-(9.32), то ДаК<р(/ї).

2°. Если а и /? — допустимые решения соответственно прямой и двойственной задач и Да)=<р ($), то а и /Ї — оптимальные решения этих задач.

 

9.10. Теоремы двойственности в линейном программировании

Основные утверждения о взаимно двойственных задачах содержатся в двух следующих теоремах.

Первая теорема двойственности. Для взаимно двойственных задач (9.25) — (9.28) и (9.29) — (9.32) имеет место один из вза имоисключающнх случаев.

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

В прямой задаче допустимое множество не пусто, а целевая на этом множестве не ограничена сверху. При этом у двойственной задачи будет пустое допустимое множество.

В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым.

Обе из рассматриваемых задач имеют пустые допустимые множества.

Вторая  теорема   двойственности.   Пусть   а° = (х?;   xjj; ... х°;    ...;   х°)— допустимое   решение   прямой задачи

(9.25) - (9.28), а = у?;y0J — допустимое решение двойственной задачи (9.29) — (9.32). Для того чтобы or и /?° были оптимальными решениями соответственно задач (9.25) — (9.28) и (9.29) — (9.32), необходимо и достаточно, чтобы выполнялись следующие соотношения:

*'(£«^?-Т;) = <и=1, 2,     л, (9.33)

y4^taijX]-b^ = Q, i=l, 2,     т. (9.34)

Условия (9.33) — (934) позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное 1 решение другой задачи. Поэтому для решения некоторой задачи линейного программирования можно вначале решить двойственную ей задачу, а затем определить оптимальное решение исходной задачи. Существуют и другие методы решения задач линейного программирования, опирающиеся на теорию двойственности.

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

Критерий оптимальности. Пусть a° = (x°i; xf; х°„) —до-пустимое решение задачи (9.25) — (9.28). Вектор а является оптимальным решением этой задачи тогда и только тогда, когда среди решений системы уравнений

т

Іа(лК,-7,=0приі,°*0, (9.35)

i-1

Я=0при І^хІкЬ, (9.36) у-1

содержится хотя бы одно допустимое решение задачи (9.29) — (9.32), двойственной к задаче (9.25) — (9.28).

О Вектор ос = (3; 0; 1; 3) является допустимым решением задачи /= -2х1~х2+хг+хА (max),.

{

хх-хг+2хъ~ хА=2, Зх2-7хэ +Зх4=2,

 

*у^0,;=1, 2, 3, 4.

В данном случае соотношения вида (9.36) отсутствуют; а из условий (9.35) имеем

(>i = -2,

иУі~1уг + 2у3 = ], + 3^ = 1.

Отсюда yt=—2, у2 = —1/3, у3=4/3. Нетрудно проверить, что /f=(—2; — 1/3; 4/3) — решение системы ограничений двойственной задачи:

( Уі

-Уу+Ъу2+ Уз>~^ ] 2у1 + 7у2 + 2уъ^1,

 

Следовательно, а = (3; 0; 1; 3) — оптимальное решение нашей задачи (из второй теоремы двойственности сразу следует, что /?=(—2; —1/3; 4/3) — оптимальное решение задачи, двойственной к данной). #

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 | 151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 | 176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 |