Метод искусственного базиса (М-задача).
Для многих задач линейного программирования, записанных в форме основной задачи и имеющих опорные планы, среди векторов P j не всегда есть m единичных.
Рассмотрим такую задачу:
Пусть требуется найти максимум функции
F = c 1 x 1 + c 2 x 2 + ……+ c n x n (1)
при условиях
……………………………………… (2)
где b i 0 (i =l, m), m <.>n и среди векторов P 1 , P 2 , …, P n нет m единичных.
Определение . Задача, состоящая в определении максимального значения функции
F = c 1 x 1 + c 2 x 2 + ……+ c n x n -М x n +1 - …- М x n + m (3)
при условиях
……………………………………… (4)
где M - некоторое достаточно большое положительное число, конкретное значение которого обычно не задается, называется расширенной задачей (М-задачей) по отношению к задаче (1) - (2).
Расширенная задача имеет опорный план
Х=(0; 0; ...; 0; b 1 ; b 2 ; ...;b m).
определяемых системой единичных векторов P n +1 ; Р п+2 , … Р п+т , образующих базис m-ro векторного пространства, который называется искусственным. Сами векторы, так же как и переменные x n + i (i =l, m ), называются искусственными. Так как расширенная задача имеет опорный план, то ее решение может быть найдено симплексным методом.
Теорема Если в оптимальном плане X*=(x* 1 , x * 2 , ...; x * n , x * n +1 ; ...; x * n + m) расширенной задачи (3) - (4) значения искусственных переменных x * n + i =0 (i =1, m ), то X*=(x* 1 , x * 2 , ...; x * n) является оптимальным планом задачи (1) - (2).
Таким образом, если в найденном оптимальном плане расширенной задачи, значения искусственных переменных равны нулю, то тем самым получен оптимальный план исходной задачи.
Значения индексной строки ∆ 0 , ∆ 1 , …, ∆ n состоят из двух частей, одна из которых зависит от M, а другая - нет. Заполняют симплекс - таблицу, которая содержит на одну строку больше, чем обычная симплексная таблица. При этом в (m+2)-ю строку помещают коэффициенты при M, а в (m+1)-ю – слагаемые, не содержащие M. При переходе от одного опорного плана к другому в базис вводят вектор, соответствующий наибольшему по абсолютной величине отрицательному числу (m+2)-й строки. Искусственный вектор, исключенный из базиса, в следующую симплекс-таблицу не записывают. Пересчет симплекс-таблиц при переходе от одного опорного плана к другому производят по общим правилам симплексного метода.
Итерационный процесс по (m+2) -и строке ведут до тех пор, пока:
либо все искусственные векторы не будут исключены из базиса;
либо не все искусственные векторы исключены, но (m+2)-я строка не содержит больше отрицательных элементов в индексах ∆ 1 , …, ∆ n .
В первом случае базис отвечает некоторому опорному плану исходной задачи и определение ее оптимального плана продолжают по (m+1)-й строке.
Во втором случае, если значение ∆ 0 отрицательное, исходная задача не имеет решения; если же ∆ 0 =0, то найденный опорный план исходной задачи является вырожденным и базис содержит по крайней мере один из векторов искусственного базиса.
Этапы нахождения решения задачи (1) - (2)
методом искусственного базиса:
Составляют расширенную задачу (3) - (4).
Находят опорный план расширенной задачи.
С помощью обычных вычислений симплекс-метода исключают искусственные переменные из базиса. В результате либо находят опорный план исходной задачи (1) - (2), либо устанавливают ее неразрешимость.
Используя найденный опорный план задачи (1) - (2), либо находят симплекс-методом оптимальный план исходной задачи, либо устанавливают ее неразрешимость.
Пример.
Найти минимум функции F = - 2x 1 + 3x 2 - 6x 3 - x 4
при ограничениях:
2x 1 +x 2 -2x 3 +x 4 =24
x 1 +2x 2 +4x 3 ≤22
x 1 -x 2 +2x 3 ≥10
x i ≥0, i =1,4
Решение.
Запишем данную задачу в форме основной задачи: найти максимум функции F = 2x 1 - 3x 2 + 6x 3 + x 4
при ограничениях:
2x 1 +x 2 -2x 3 +x 4 =24
x 1 +2x 2 +4x 3 +x 5 =22
x 1 -x 2 +2x 3 - x 6= 10
x i ≥0, i =1, 6
В системе уравнений последней задачи рассмотрим векторы из коэффициентов при неизвестных:
Среди векторов P 1 , Р 2 , … P 6 только два единичных (P 4 и P 5). Поэтому в левую часть третьего уравнения системы ограничений задачи добавим дополнительную неотрицательную переменную х 7 и рассмотрим расширенную задачу, состоящую в максимизации функции
F = 2x 1 - 3x 2 + 6x 3 + x 4 - Мх7
при ограничениях:
2x 1 +x 2 -2x 3 +x 4 =24
x 1 +2x 2 +4x 3 +x 5 =22
x 1 -x 2 +2x 3 - x 6 +x 7= 10
Расширенная задача имеет опорный план Х=(0; 0; 0; 24; 22; 0; 10), определяемый системой трех единичных векторов: P 4 , P 5 , Р 7 .
Понятие двойственной (соапряженной) задачи линейного программирования.
Правила построения двойственной задачи.
С каждой задачей линейного программирования (ЗЛП), которая называется двойственной задачей (или сопряженной) по отношению к исходной задаче, которая называется прямой.
Двойственная задача строится по отношению к прямой задаче, записанной в стандартной форме:
F=c 1 x 1 +c 2 x 2 +…+c n x n max (3.6)
a 11 x 1 +a 12 x 2 +…+a 1n x n ≤ b 1 ,
a 21 x 1 +a 22 x 2 +…+a 2n x n ≤ b 2 ,
………………………………
a k1 x 1 +a k2 x 2 +…+a kn x n ≤ =b k , (3.7)
a k+1,1 x 1 +a k+1,2 x 2 +…+a k+1,n x n =b k+1 ,
………………………………
a m1 x 1 +a m2 x 2 +…+a mn x n =b m ,
x j ≥ 0, , l ≤ n (3.8)
Задача, состоящая в нахождении минимального значения функции
L = b 1 y 1 + b 2 y 2 + … + b m y m (3.9)
при условиях
a 11 y 1 + a 12 y 2 +…+ a m1 y m ≥ c 1
a 21 y 1 + a 22 y 2 +…+ a m2 y m ≥ c 2
………………………………
a 1 l y 1 + a 2 l y 2 +…+ a m l y m ≥ c l (3.10)
a l +1,1 y 1 + a l +1,2 y 2 +…+ a l +1,m y m = c l+1
………………………………
a m1 y 1 + a m2 y 2 +…+ a mn y m = c m
y i ≥ 0, , k ≤ m (3.11)
называется двойственной по отношению к задаче (3.6) – (3.8).
Правила построения двойственной задачи приведены в таблице:
Структурные характеристики ЗЛП |
Задача линейного программирования |
|
Двойственная |
||
1. Целевая функция |
Максимизация (max) |
Минимизация (min) |
2. Количество переменных |
n переменных |
Равно количеству ограничений прямой задачи (3.7), y i , т.е. m |
3. Количество ограничений |
m ограничений |
Равно количеству переменных прямой задачи x j , , т.е n |
4. Матрица коэффициентов в системе ограничений |
||
5. Коэффициенты при переменных в целевой функции |
c 1 ,c 2, …,c n |
b 1 ,b 2, …,b m |
6. Правая часть системы ограничений |
b 1 ,b 2, …,b m |
c 1 ,c 2, …,c n |
7. Знаки в системе ограничений |
а) x j ≥ 0- условие неотрицательности |
j-е ограничение имеет знак «≥» |
б) на переменную x j не наложено условие неотрицательности |
j-е ограничение имеет знак «=» |
|
в) i-е ограничение имеет знак «≤» |
переменная y i ≥0 |
|
г) i-е ограничение имеет знак «=» |
на переменную y i не наложено условие неотрицательности |
Примечание
Прямая задача на максимум и двойственная на минимум являются взаимодвойственными задачами. Поэтому можно считать задачу (3.9) – (3.11) прямой ЗЛП, а задачу (3.6) – (3.8) – двойственной к ней задачей. При этом правила построения двойственной ЗЛП сохраняются, лишь с тем изменением, что исходной считается задача на минимум.
Если исходная задача решается на max (min), а в системе ограничений) i -е (j -е) ограничение имеет знак «≤» («≥»), то для построения двойственной задачи необходимо:
а) либо домножить обе части i -го (j -го) неравенства на (-1) и поменять знак на «≤» («≥»)
б) либо привести i -е (j -е) ограничение к равенству путем введения дополнительной переменной x n+ i ≥0
Необходимым условием применения симплекс-метода является наличие опорного плана, то есть допустимого базисного решения канонической системы уравнений. Для этого должны выполняться следующие условия:
- система должна иметь каноническую (ступенчатую) структуру;
- присутствуют только ограничения-равенства;
- правые части ограничений положительны;
- переменные задачи положительны.
Без этих условий нельзя получить опорный план. Однако в реальных задачах далеко не всегда выполняются перечисленные условия.
Существует специальный метод, называемый искусственным базисом, который позволяет в любой задаче линейного программирования получить начальный опорный план.
Пусть задача линейного программирования приведена к стандартному виду:
Пусть все /? > 0, но часть или все базисные переменные отрицательны, X; 0. Следовательно, опорного плана нет.
Дополним уравнения-ограничения искусственными переменными (предполагаем, что все x j j - 1, п ).
Введем т переменных (по количеству уравнений): х лМ т, которые в новой системе будут базисными, а отрицательные х-
В результате получим следующую эквивалентную задачу.
Здесь переменные x n+i не имеют никакого отношения к исходной задаче линейного программирования. Они служат лишь для получения опорного плана и называются искусственными переменными. А новая
целевая функция /(.т) сформирована для полноты задачи.
В оптимальном опорном плане искусственные переменные должны быть равны нулю. В противном случае нарушится условие первоначальной задачи.
В начальном опорном плане искусственные переменные являются базисными, то есть не равны нулю, а в оптимальном плане искусственные переменные должны быть равны нулю. Значит, искусственные переменные должны стать в оптимальном плане свободными. В этом переводе и состоит основная идея метода: перевод искусственных переменных из базисных переменных в свободные. Рассмотрим механизм такого перевода на примере.
Перепишем ЗЛП в стандартной форме. Для этого введем дополнительные переменные х } , х А, х 5 , х 6 и запишем задачу в канонической форме.
Свободные переменные х, х 2 = 0, при этом базисные переменные примут значения х 3 =-5, х 4 = -5, х 5 = 7, х 6 =9. Так как часть базисных переменных отрицательны, следовательно опорного плана нет. Для получения начального опорного плана введем переменные х 7 , х 8 в двух первых уравнениях-ограничениях и сформулируем вспомогательную задачу:
Таким образом, начальным базисом является
Симплекс-таблица с искусственным базисом
Х 4 |
|||||||||||
Запишем последовательности опорных планов.
Для первых трех шагов приращения А к вычисляются только по искусственным переменным, которые входят в искусственную целевую функцию /(х) = х 7 + х 8 с коэффициентом с, = 1.
На третьем шаге искусственные переменные исключены, так как все А к положительны.
Итак, симплекс-метод с введением искусственных переменных включает два этапа.
Формирование и решение вспомогательной задачи ЛП с введением искусственных переменных. Искусственные переменные в начальном опорном плане являются базисными. Искусственная целевая функция включает только искусственные переменные. При получении смежных опорных планов искусственные переменные из базисных переводим в свободные. В результате получен оптимальный опорный план для вспомогательной задачи /(х) = 0.
Оптимальный опорный план вспомогательной задачи ЛП является начальным опорным планом основной задачи ЛП. Задача решается для исходной целевой функции /(х) обычным симплекс-методом.
Замечания
- 1. Введение искусственных переменных требуется в двух случаях:
- ряд базисных переменных х, в канонической форме отрицательны;
- если трудно свести к канонической форме, то просто в любое уравнение-ограничение добавляем искусственную переменную.
- 2. Встречающиеся в практике автоматического управления задачи линейного программирования содержат от 500 до 1500 ограничений и более 1000 переменных. Ясно, что задачи такой размерности можно решать лишь с помощью ЭВМ и специального программного обеспечения. Сложность алгоритма заключается в том, что:
- ППП требует канонического вида;
- ППП для задач такой размерности требует использования больших ЭВМ (и параллельных вычислений), так как симплекс-метод хранит всю таблицу.
- 3. Вычислительную эффективность симплекс-метода можно оценить следующими показателями:
- число шагов (смежных опорных планов);
- затраты машинного времени.
Существуют такие теоретические оценки для стандартной задачи линейного программирования с т ограничений и «"переменных:
- среднее число шагов * 2 т
и лежит в диапазоне }
Значение слова неудачный
Обзор Samsung Galaxy A7 (2017): не боится воды и экономии Стоит ли покупать samsung a7
Делаем бэкап прошивки на андроиде
Как настроить файл подкачки?
Установка режима совместимости в Windows