Лекция 9. Столбцовые симплекс-таблицы. Двойственный симплекс-метод (1162205), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

В соответствующей симплекс-таблице переменныеvj , j = 1, 2, . . . , n должны быть базисными. ЕслиPэто условие неnвыполнено, то введем дополнительное условие j=1 vj ≥ n. Выпишемстроку, соответствующую этому неравенству. Пусть в полученнойggddсимплекс-таблице IB, IBи IN, INсуть базисныеи небазисные наборыPnпеременных xj , vj .

Тогда в неравенстве j=1 vj ≥ n. выразим всепеременные через небазисные:XX XX Xxij xj +vij vj ≥ n.−vi0 +gi∈IBgdi∈IBi∈INggi∈IBi∈IN18 / 26Двойственный симплекс-методПоследнее неравенство соответствует вспомогательной строкесимплекс-таблицыxn+2−n −Pgi∈IBvi0−Pgi∈IBxij1−Pgi∈IBvijТеперь, выводя эту строку из базиса и получая решение задачи (7) уже сэтим дополнительным условием, получаем такое решение задачи, длякоторого все переменные vj будут базисными. Не меняя обозначений,gdбудем считать, что IB= 1, 2, . . .

, n. В таком случае |IB| = m. Кроме того,dэлементы xij , i = 0, 1, . . . n, j ∈ IN полученной симплекс-таблицы будутявляться элементами таблицы, соответствующей исходной задаче.P Дляdполучения элементов xi0 , i ∈ IBосталось решить систему a0 = i∈I d ai xi0 ,BPпосле чего вычислить элемент x00 = i∈I d ci xi0 . Полученная таблицаBdxij , i ∈ 0, 1, . . .

n, j ∈ INявляется двойственно допустимойсимплекс-таблицей для исходной задачи (1).19 / 26Двойственный симплекс-методРассмотрим ранее обсуждавшийся пример:x2x3x4→ max,= 1 − 3x1 + 5x2 ≥ 0,= 3 + 8x1 − 15x2 ≥ 0,x1,2 ≥ 0.Соответствующая симплекс-таблица при IB = {3, 4}, IN = {1, 2} имеет видx0x1x2x3x4t000013t10-103-8t2-10-1-515Данная таблица не является двойственной допустимой: t2 ≺ 0.20 / 26Двойственный симплекс-методВведем дополнительное ограничение x5 = 10 − x1 − x2 ≥ 0, послевыведения x5 из базиса и введения вместо нее в базис x2 получаемтаблицу уже двойственно допустимую:x0x1x2x3x4x5t01001051-1470t11-118-230t51015-15-121 / 26Двойственный симплекс-методДля этой таблицы s = 4, l = 1, поэтому сделаем итерацию двойственногосимплекс-метода, пересчитав столбцы таблицы:x0x1x2x3x4x5t083/23147/2383/23-3/2300t41/23-1/231/238/23-10t58/2315/238/23-5/230-1Теперь, выбирая по правилу метода s = 3, l = 5 получим оптимальнуютаблицу.22 / 26Двойственный симплекс-методРассмотрим в качестве следующего примера задачу о кратчайшем пути изP1 в P5 в графе, изображенном на рис.

4, где цифрами указаны длины дуг:P2i3P5- i4 3>P1 64i 1QQQs 3 Qi- iP32P4Рис. 423 / 26Двойственный симплекс-методСоответствующая задача ЛП есть4x1 + 3x2 + 3x3 + 4x4 + 2x5 + x6x1 + x2−x1 + x3−x2 + x4 + x5−x5 + x6−x3 − x4 − x6xi→=====≥min,1000−10, i = 1, . . . , 624 / 26Двойственный симплекс-методВыразив все переменные через x2 , x4 и перейдя к задаче на max, получимсимплекс-таблицу:x0x1x2x3x4x5x6t0-7101000t2-11-110-1-1t41000-111Данная таблица не является двойственно допустимой: t2 ≺ 0.25 / 26Двойственный симплекс-методОднако учитывая, что в искомой цепи будет не более 3 дуг, то здесь выборM будет проще: M ≥ 3. Выберем вспомогательное неравенство в видеx7 = 3 − x2 − x4 ≥ 0.

Выводя из базиса x7 и вводя вместо x7 переменнуюx2 , приходим к таблицеx0x1x2x3x4x5x6x7t0-4-23-20330t71-11-1011-1t42-11-1-1220Теперь, выбирая s = 1, l = 7, получим решение x = (0, 1, 0, 0, 1, 1)T ,которому соответствует цепь P1 → P3 → P4 → P5 .26 / 26.

Характеристики

Список файлов лекций