semopt7 (Практические занятия)

Занятие 7. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.РЕШЕНИЕ ОСНОВНОЙ ЗАДАЧИА.2. Решение основной задачиПостановка задачиНайти максимум функцииnf ( x) = ∑ c j x jj =1при ограниченияхn∑ aij x j ≥ bi ,j =1n∑ aij x j ≤ bi ,i = 1, … , m ;i = m + 1, … , p ;j =1x j ≥ 0 , j = 1, … , n .Задача линейного программирования называется основной. Предполагается, чтоbi ≥ 0 , i = 1, … , p .Стратегия поискаДля решения основной задачи симплекс-методом она должна быть приведена кканонической задаче путем введения в каждое ограничение по одной дополнительнойпеременной: в каждое ограничение-неравенство со знаком « ≤ » вводится дополнительнаяпеременная со знаком « + » (она становится базисной), а в каждое ограничениенеравенство со знаком « ≥ » вводится дополнительная переменная со знаком «–».Каноническая задача записывается следующим образом:nf ( x) = ∑ c j x j → max ,j =1n∑ aij x j − x n +i = bi ,i = 1, … , m ;j =1n∑ aij x j + x n +i = bi ,i = m + 1, … , p ;j =1x1 ≥ 0, … , x n + p ≥ 0 .Так как в общем случае в уравнениях нет базисных переменных, то для того,чтобы можно было применить симплекс-метод, делается переход к М-задаче.

В каждоеиз m первых уравнений вводится искусственная переменная со знаком « + » (онастановится базисной), а к целевой функции добавляется сумма искусственных200переменных, умноженная на « − M ». В результате получаем задачу в расширеннойформе:nf ( x) = ∑ c j x j − Mj =1m∑ x n + p +i → max ,i =1n∑ aij x j − x n +i + x n + p +i = bi ,i = 1, … , m ;j =1n∑ aij x j + x n +i = bi ,i = m + 1, … , p ;j =1x1 ≥ 0, … , x n + p + m ≥ 0 .З а м е ч а н и я. Если решается задача поиска минимума целевой функции, то припереходе к M -задаче перед числом M ставится знак « + ».Пример 1. Найти условный максимум в задачеf ( x) = x1 − x 2 → max ,−1x1 + 2 x 2 ≥ 4 ,3x1 + 2 x 2 ≤ 14 ,x1 , x 2 ≥ 0 .† Приведем поставленную основную задачу к канонической.

Так как первоенеравенство имеет знак « ≥ » , введем дополнительную переменную x 3 со знаком «–».Поскольку во втором неравенстве знак « ≤ », то введем дополнительную переменную x 4со знаком «+» (она становится базисной). В итоге получим каноническую задачу:f ( x) = x1 − x 2 → max ,− x1 + 2 x 2 − x 3 = 4 ,3x1 + 2 x 2 + x 4 = 14 ,x1 ,..., x 4 ≥ 0 .Поскольку в первом уравнении нет базисных переменных, то перейдем к M -задаче. Дляэтого введем искусственную переменную x 5 и добавим ее к целевой функции скоэффициентом « − M ».

В результате получим задачу в расширенной форме:f ( x) = x1 − x 2 − M x 5 → max ,− 1x1 + 2 x 2 − 1x3 + 0 x 4 + 1x5 = 4 ,3x1 + 2 x 2 + 0 x3 + 1x 4 + 0 x5 = 14 ,x1 , … , x5 ≥ 0 .Применим алгоритм симплекс-метода.1. Найдем начальное базисное решение. Базисными переменными являются x 5 , x 4 ,а свободными x1 , x 2 , x 3 . Приравняем свободные переменные к нулю. Тогда201x1 = x 2 = x3 = 0 и x 4 = 14 , x5 = 4 . Начальное базисное решение (0; 0; 0; 14; 4)T .Начальному базисному решению соответствует начало координат на рис. 1.2. Заполним табл. 1 согласно алгоритму.1c iBБПБРx1−1x2−M0x5x4414−1322Таблица 1cj−M00x3x4x5−100110БРa irzjΔjx27− x1 + 2 x 2 = 4x∗21f (x ) = 0 − 124∇fx13x1 + 2 x 2 = 14Рис. 131 . Вычислим относительные оценки Δ j , j = 1, … , 5 :Δ1 = 1 − [(−M ) ⋅ (−1) + 0 ⋅ 3] = 1 − M ;Δ 2 = −1 − [(−M ) ⋅ 2 + 0 ⋅ 2] = −1 + 2M ;Δ 3 = 0 − [(−M ) ⋅ (−1) + 0 ⋅ 0] = −M ;Δ 4 = 0 − [(−M ) ⋅ 0 + 0 ⋅ 1] = 0 ;Δ 5 = −M − [(−M ) ⋅ 1 + 0 ⋅ 0] = 0 .Результаты приведены в табл.

2.202100x3x4c iBБПБРx1−1x2−M0x5x4414−1322−10M−2M− 1 + 2MM010−M01− MТаблица 2cj−Mx5БРa ir10−M0zjΔj⊗41. Проанализируем относительные оценки. Оценка Δ 2 = −1 + 2M > 0 , так какM > 0 и, следовательно, текущее базисное решение x 4 = 14 , x5 = 4 , x1 = x 2 = x3 = 0не оптимально. Рассмотрим коэффициенты столбца при переменной x 2 . Поскольку обакоэффициента положительны, то r = 2 и переменная x 2 должна быть введена в числобазисных.51. Определим переменную, выводимую из базиса. Для этого вычислим отношенияБР4 14. Имеем ,(табл.

3). Выберем из них наименьшее значение. Следовательно, s = 12 2a irи из числа базисных должна быть удалена переменная x5 и заменена переменной x 2 .Таблица 3cj100−1−Mc iBБПБРx1x2x3x4x5БРa ir−M0x5x4414−1322−1010M−2MM0102⊗7zj1− M−1 + 2M−M0−M0Δj⊗61. Вычислим новое базисное решение, занося результаты пересчета табл. 3 в табл. 4.Таблица 4cj100−1−Mc iBБПБР−1x220x410x1x21241−0x3x4x5121012−1−1БРa irzjΔj203В табл. 4 в столбец БП введена переменная x 2 вместо x 5 . Первой пересчитываетсястрока, соответствующая введенной переменной x 2 .

Она получается в результатеделения каждого элемента разрешающей строки табл. 3, помеченной ⊗, на разрешающийэлемент, равный 2. Остальные элементы пересчитываются по «правилупрямоугольника». Для второй строки имеем:14 −4⋅2= 10 ,20−2 ⋅ (−1)= 1,23−1−2 ⋅ (−1)= 4,22⋅0= 1,22−2⋅2= 0,20−1⋅ 2= −1 .2Перейдем к шагу 3.32. Вычислим оценки Δ j , j = 1, … , 5 . Строка Δ j пересчитывается по табл. 3 такжесогласно «правилу прямоугольника»:Δ1 = 1 − M −(−1 + 2M ) ⋅ (−1) 1= ,22Δ4 = 0 −Δ2 = 0 ,(−1 + 2M ) ⋅ 0= 0;21c iBБПБР−1x220x410x1−Δ 3 = −M −Δ5 = 0 −−1x211241212⊗0−10(−1 + 2M ) ⋅ (−1)1=− ,22(−1 + 2M ) ⋅ 11= −M + .2200x3x41210−121−2100Таблица 5cj−Mx5БРa ir12−11−2−M +zj12Δj42. Проанализируем относительные оценки и, как следствие, текущее базисное1решение x 2 = 2 , x 4 = 10 , x1 = x3 = x5 = 0 .

Оценка Δ 1 = > 0 , поэтому рассмотрим2коэффициенты столбца при переменной x1 . Так как этот столбец содержит одинположительный коэффициент, то r = 1 и переменная x1 должна быть введена в числобазисных переменных.52. Определим переменную, выводимую из базиса. Для этого вычислимБР10наименьшее из неотрицательных отношений. Оно равно(табл. 6).4a ir204Следовательно, s = 2 и поэтому из базиса должна быть удалена переменная x 4 изаменена переменной x1 .1c iBБПБР−1x220x410x1−−1x211241212⊗00x3x41210−0−10121−2100Таблица 6cj−Mx5БРa ir--12−1−10⊗4zj12−M +Δj1262.

Вычислим новое базисное решение. Результат пересчета табл. 6 приведентабл. 7.1c iBБПБРx1−1x2−1x2011x12681041000x3x4−Mx538141814381−4−Таблица 7cjБРa irzjΔjПерейдем к шагу 3.33. Вычислим оценки Δ j , j = 1, … , 5 , и определим, является ли решение x1 =x2 =26, x3 = x 4 = x5 = 0 оптимальным (табл. 8).8205в10,41c iBБПБРx1−1x2−1x2268011x1104101−10000x3x4−Mx53814585−81838−14181−8Таблица 8cjБРa ir145−8−−M +zj58Δj2610, x2 =,481026x3 = x 4 = x5 = 0 является оптимальным. Решение исходной задачи x1∗ =, x 2∗ =48получается путем отбрасывания дополнительных переменных x 3 , x 4 и искусственнойВсе оценки Δ j неположительны, следовательно, решение x1 =переменной x 5 . Графически оно соответствует точке x ∗ (рис.

1). ■Пример 2. Найти условный максимум в задачеf ( x) = −2 x1 + 4 x 2 → max,− x1 + 2 x 2 ≤ 4,3 x1 + 2 x 2 ≤ 14,x1, x 2 ≥ 0.† Приведем поставленную основную задачу к канонической. Так как обанеравенства имеют знак « ≤ », то введем дополнительные переменные x 3 и x 4 со знаком«+» (они становятся базисными). В итоге получим каноническую задачу:f ( x) = −2 x1 + 4 x 2 → max,−1x1 + 2 x 2 + 1x 3 + 0 x 4 = 4,3 x1 + 2 x 2 + 0 x 3 + 1x 4 = 14,x1, x 2 , x 3 , x 4 ≥ 0.Решим ее симплекс-методом.1.

Найдем начальное базисное решение: x1 = x 2 = 0 (так как x1 , x 2 – свободныепеременные), x3 = 4 , x 4 = 14 .2. Заполним табл. 1 согласно алгоритму.206c iBБПБР−2x100x3x4414−13400x2x3x4221001Таблица 1cjБРa irzjΔj31. Вычислим оценки Δ j , j = 1, … , 4 , и определим, является ли базисное решениеx3 = 4, x 4 = 14 , x1 = x 2 = 0 оптимальным (табл. 2).Таблица 2cj400x2x3x40220100010zj−2400Δjc iBБПБР−2x100x3x4414−13БРa ir⊗41. Проанализируем относительные оценки. Оценка Δ 2 > 0 , поэтому исследуемоерешение не является оптимальным.

Рассмотрим столбец x 2 . Его коэффициентыположительны. Значит, r = 2 и в базис должна быть введена переменная x 2 .51. Определим переменную, которая должна быть выведена из базиса, вычисливБРнаименьшее из неотрицательных отношений. Оно равно 2 (табл. 3). Следовательно,a irиз базиса должна быть выведена переменная x3 и заменена переменной x 2 .Таблица 3cj400x2x3x4БРa ir02201000102 ⊗7zj−2400Δjc iBБПБР−2x100x3x4414−13⊗20761. Вычислим новое базисное решение. Результаты пересчета табл. 3 приведены втабл. 4.c iBБПБР4x220x410−2x1−124400x2x3x4112−100Таблица 4cjБРa ir1zjΔjПерейдем к шагу 3.32.

Вычислим оценки Δ j ,j = 1, … , 4 , и определим, является ли решениеx 2 = 2, x 4 = 10, x1 = x3 = 0 оптимальным (табл. 5).c iBБПБР4x220x410−2x1−124−20Таблица 5cj400x2x3x4100412−1210zj0−20ΔjБРa ir4 2. Все оценки Δ j , j = 1, … , 4 , неположительны, значит, исследуемое решениеx 2 ∗ = 2, x 4 ∗ = 10, x1∗ = x 3∗ = 0 оптимально. Значение целевой функции в точкемаксимума f max = 8 . Найденному решению соответствует вершина А на рис.

2. Однако,как следует из геометрической интерпретации исходной задачи, она имеет бесконечноемножество решений, лежащих на ребре АВ. В этом легко убедиться с помощьюсимплекс-метода, если ввести в базис переменную x1 вместо переменной x 4 , которойсоответствует оценка Δ 4 = 0 . Соответствующие расчеты приведены в табл. 6. Заметим,что равенство нулю оценки Δ1 для небазисной переменной x1 также свидетельствует оналичии бесконечного множества решений.2083x1 + 2 x 2 = 14x2∇f− x1 + 2 x 2 = 44B32A1−2f (x ) = 0c iBБПБР4x2−2x1268104Все оценки Δ j ,21345x1Рис.

2Таблица 6cj−2x1400x2x3x40110−204381−4218140zj0−20ΔjБРa irj = 1, … , 4 неположительны, значит, исследуемое базисное26 ∗ 10; x1 =; x3∗ = x 4∗ = 0 оптимально. Значение целевой функции в84точке максимума f max = 8 . Полученному решению соответствует вершина В на рис. 2.Равенство нулю оценки Δ 4 для небазисной переменной x 4 в табл. 6 свидетельствует оналичии бесконечного множества решений. ■решение x 2∗ =209.