Решебник_МО

противоречит требованию xn+s 0.

Выбрав r-й разрешающий столбец, будем вначале интересоваться только теми строками, для которых коэффициенты ajr

расстояние вдоль положительного направления оси r от начала координат до гиперплоскости xn+j = 0. Мы заинтересованы как можно скорее выйти на вершину многогранника и в лучшем случае добьемся своей цели после первого же шага ЖИ. Рассмотрим точку

которая определяет расстояние от начала координат до последней отделяющей гиперплоскости xn+k = 0, и точку

которая определяет расстояние до первой не отделяющей гиперплоскости xt+n = 0.

Если xrA xrB , то отрезок [ xrA , xrB ] является ребром первого

ранга многогранника, а точки xrA и xrB его вершинами. Случай равенства называется вырождением, поскольку ребро стягивается в точку. Выбрав в качестве разрешающего коэффициента akr, после шага ЖИ найдем опорное решение.

Если xrA >xrB, то гиперплоскость хn+k=0 является отделяющей для точки xrB, а гиперплоскость xn+t=0 является отделяющей для точки

xrA. Следовательно, отрезок [ xrA , xrB ] не принадлежит многограннику

G, и на оси xr нет ни одной его вершины. В этом случае имеет смысл выбрать другой положительный коэффициент asq и провести анализ для q-го столбца. В случае неудачи можно поочередно просмотреть все положительные коэффициенты s-й строки, и при отсутствии вершин на соответствующих осях либо сделать шаг ЖИ, беря в качестве разрешающего любой положительный коэффициент s-й строки, либо начать просмотр другой строки с отрицательным свободным членом. Действуя указанным образом, мы или убедимся в

121

недопустимости задачи, или после конечного числа шагов ЖИ выйдем в одну из вершин многогранника, т.е. найдем опорное решение ЗЛП.

СИМПЛЕКС-МЕТОД. ПОИСК ОПТИМАЛЬНОГО РЕШЕНИЯ

Пусть имеется матрица опорного решения ЗЛП, в которой все bj ≥ 0. Если Z-строка не содержит положительных коэффициентов, то при перемещении по любой координатной оси в положительном направлении значение целевой функции изменится на величину

коэффициенты, то при движении в положительном направлении по соответствующим осям получим Z ci xi 0 . Поэтому для

увеличения Z можно двигаться по любой координатной оси xr, для которой cr > 0. Однако при перемещении вдоль xr нельзя покидать границ многогранника, т.е. движение возможно только до соседней ближайшей вершины.

Координата точки пересечения r-оси с гиперплоскостью xn+j = 0

направлении, и, следовательно, двигаясь по ребру xr, важно учитывать лишь те гиперплоскости, для которых аjr < 0, так как bi > 0.

Следовательно, сделав шаг ЖИ с разрешающим элементом akr < 0, мы войдем в новую вершину, в которой правый коэффициент Z-

Если в r-столбце, где сr > 0, нет отрицательных коэффициентов, т.е. все ajr > 0, то целевая функция не ограничена.

Если среди свободных членов, стоящих в строках с отрицательными коэффициентами ajr, есть нулевые, то это

122

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

xk+n = akrxr, т.е. в любом случае выйдем за пределы многогранника G. Если в z-строке, кроме cr, есть другие положительные

коэффициенты, например cq > 0, то нужно рассмотреть возможность движения по оси хq. Если все возможные направления окажутся запрещенными, то следует перейти к новому набору координатных осей, сделав шаг ЖИ с разрешающим элементом аkr < 0 в столбце сr > 0 и в строке с bk = 0. В результате получим новую матрицу, где столбец свободных членов остается прежним. Будем преобразовывать матрицу по рассмотренному правилу до тех пор, пока не перейдем в другую вершину G или не убедимся в неограниченности целевой функции или же в оптимальности точки начала координат.

Решением задачи ЛП является точка начала координат относительно полученной матрицы. Для переменных хi, которым соответствуют столбцы этой матрицы xi0 = 0; а для всех переменных xj, которым соответствуют строки матрицы хj0 = bj.

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

Пример 32. Требуется минимизировать целевую функцию Z=6x1+9x2+9x3, параметры которой связаны системой неравенств x1+2x2+3x31, x12x2+x33, 4x13x2+2x3 –1, x1+2x2+x32, 2x1+x2+3x3 1 и x1,x20.

Решение. Составим матрицу условий задачи:

123

Приведем задачу к каноническому виду. Переменная x3 является свободной, обозначим соответствующий ей столбец матрицы через x3*. Так как требуется определить минимум функции, инвертируем знаки элементов Z-строки. Получим матрицу:

Теперь избавимся от свободной переменной х*3, выполнив шаг ЖИ с разрешающим элементом а53. Получим матрицу:

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

Решением ЗЛП является точка начала координат относительно полученной матрицы: x1= 0, x2= 3, x3=0, minZ= – (–Z) = – (–9)=9.

Пример 28. Требуется максимизировать целевую функцию

Z=x3+x5max, параметры которой связаны системой неравенств

2x1+2x3x4+x50, 2x2x3x4+2x50, x12x24x4+x50, 2x1+x2+1x3=1 и x1,x3,x40, ,x520.

Решение. Составим матрицу условий задачи:

124

Приведем задачу к каноническому виду. Выполним первичные преобразования, связанные с заманой переменных. В связи с имеющимся параметрическим ограничением x5 20 введем вспомогательную переменную x5=x5*+20 и пересчитаем, исходя из этого условия, элементы последнего столбца матрицы. Так как x520 ограничена в задаче сверху, то изменим знак у x5*, инвертируя знаки в соответствующем ей столбце матрицы. Переобозначим переменные.

Выполним вторичные преобразования, связанные с исключением переменных. Переменная u2 является свободной, соответствующий ей столбец матрицы обозначен как u20, ограничениеравенство – как u90. Теперь избавимся от свободной переменной u20. Для этого выполним шаг Жорданова исключения, выбрав в качестве разрешающего элемент u82. Пересчитав элементы, получим таблицу:

Выпишем зависимость u20 от новой совокупности независимых

Теперь необходимо избавиться от ограничения-равенства u90. Для этого вновь сделаем шаг Жорданова исключения, выбрав в качестве разрешающего элемент u93 , а в полученной таблице удалим столбец u90.

125

«Слабых» ограничений в матрице нет, поэтому начнем поиск опорного решения задачи. В столбце свободных членов имеется отрицательный элемент b3, и, следовательно, полученное решение (начало координат) не является опорным. Строка u3 содержит три положительных элемента u34, u35, u38, следовательно, возможно продвижение вдоль трех осей. Для выбора направления смещения вычислим:

По этим же правилам вычисляем u5A =18 и u5B =19,71, u8A =18 и u8B =46.

Для всех трех направлений urA urB , следовательно, отрезок

[ xrA , xrB ] является ребром первого ранга многогранника, а точки urA и

urB его вершинами. Выберем одно из направлений, в частности u4, и выполним замену переменных (шаг Жорданова исключения с разрешающим элементом u34).

Все элементы столбца свободных членов неотрицательные, следовательно, получено опорное решение.

Определим оптимальное решение. В Y-строке матрицы имеется положительный элемент С3, а в столбце u3 имеется отрицательный элемент а73, следовательно, решение можно улучшить. Отрицательный элемент а73 используем в качестве разрешающего.

126

В Y-строке полученной матрицы имеется положительный элемент С8, а в столбце u4 имеется отрицательный элемент а48, следовательно, решение можно улучшить. Отрицательный элемент а73 используем в качестве разрешающего а84.

Все элементы Y-строки полученной матрицы отрицательные, следовательно, получено оптимальное решение. Решением ЗЛП является точка начала координат относительно полученной матрицы: u1 = u4=u7 = u5= 0, u3=13,98, u6= 49,57, u8= 46,06.

Определим значение исключенной в ходе вторичных преобразований свободной переменной u20:

u20 = 0,5u10,5u82u40,5u5+10 = 0 0,5*46,06 0+0+10 = 13,03.

Вернемся к исходным переменным, которые были заменена в ходе первичных преобразований на этапе приведения задачи к каноническому виду: –x5*= u5= 0, x5*= 0, x5 = x5*+20 = 20, x1 = u1 = 0

x20= u20=13,03, x3= u3=13,98, x4=u4= 0, x6=u6= 49,57, x7=u7=0, x8=u8= 46,06.

Решением задачи является точка с координатами x1=x4=0, x2=13,03, x3=13,98, x5= 20, в которой целевая функция имеет значение

Z(X*) = Y = x3+x5 = 33,98.

ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

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

127

Матрица условий двойственной задачи получается путем транспонирования матрицы условий прямой задачи: в матрице условий (табл. 9) каждому i-му столбцу соответствует независимая переменная xi прямой задачи и зависимая переменная μi двойственной задачи; каждой j-й строке соответствует зависимая переменная уj прямой задачи и независимая переменная λj двойственной; в столбце свободных членов матрицы условий прямой задачи записаны коэффициенты целевой функции двойственной задачи, а в строке коэффициентов целевой функции прямой задачи – свободные члены двойственной.

Пример 34. Составим двойственную задачу к следующей ЗЛП со смешанными условиями: Z=6x1+9x2+9x3→max, x1+2x2+3x3≤1, x12x2+x33, 4x13x2+2x31, x1+2x2+x3=2 и x1,x20.

Решение. Приведем задачу к виду, содержащему один тип ограничений-неравенств: Z=6x1+9x2+9x3→max, x1+2x2+3x3≤1,

–x1+2x2–x3≤–3, –4x1+3x2–2x3≤+1, x1+2x2+x3=2 и x1,x20.

Составим двойственную задачу согласно правилу табл. 12.

128

Взаимосвязь между решениями прямой и двойственной ЗЛП следующая:

1.Транспонированная матрица условий прямой задачи совпадает с матрицей условий двойственной задачи.

2.Опорное решение одной из пары двойственных задач определяет условно-оптимальное решение другой задачи.

3.Если одна из пары двойственных задач имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем maxZ = minW.

4.Если целевая функция одной из пары двойственных задач не ограничена, то другая противоречива.

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

Решение любой задачи ЛП можно заменить решением

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

При использовании двойственного симплекс-метода для отыскания оптимального решения двойственной задачи выбирается любая s-я строка матрицы условий, в которой bs < 0, и при отсутствии

129

вырождения разрешающий элемент asк находится из условия

x3 –5, x4 1, сделав замену переменных x3 = x3*–5, x4 = x4*+1, получим каноническую матрицу (каноническую задачу):

Определим опорное решение. Слабых ограничений в матрице нет. В столбце свободных членов имеется два отрицательных элемента, следовательно, это не опорное решение.

Строка х9 содержит четыре положительных элемента а91, а93, а95 и а96, следовательно, возможно продвижение вдоль четырех осей. Для выбора направления смещения вычислим для каждой оси расстояние до самой дальней отделяющей (7) и самой ближней неотделяющей (8) плоскостей. Для оси x1:

130