ДВОЙСТВЕННЫЙ СИМПЛЕКСНЫЙ МЕТОД (СМ)

Использование идеи двойственности в сочетании с общей идеей СМ позволило разработать еще один метод решения задач линейного программирования: двойственный СМ или метод последовательного уточнения оценок.

Оказывается полезным в ряде случаев:

a. с его помощью можно решить задачу без использования искусственных переменных;

b. облегчается решение ряда вопросов, например, анализ на чувствительность.

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

 

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

1. Определяется возможность применения двойственного СМ.

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

1. Проверяется полученное базисное решение на оптимальность:

1) если вектор b≥0, то получено оптимальное решение;

2) если имеется отрицательная правая часть для некоторого i, но все  в этой строке неотрицательные. В этом случае задача неразрешимая;

3) определяется переменная, которая должна быть исключена из базиса, т.е. разрешающая строка. В каждой разрешающей строке выбирается такая, для которой правая часть отрицательная и по модулю самая наибольшая – отрицательная;

4) определяется переменная, которая должна быть включена в базис, т.е. разрешающий столбец. Для этого берется отношения симплексных разностей к разрешающей строки - , p - номер выбранной разрешающей строки, причем рассматриваются, только те отношения, для которых < 0. Из допустимых отношений выбирается минимальное.

3. Замена базиса и переход к шагу 2.

Пример 1:

 

Можно применить СМ:

- базисная переменная = -2 < 0;

- симплексные разности на начальном этапе неотрицательны,

 

 

			0	0	-1	-1	-1
	0	-2	1	0	-1	1	-1
	0	1	0	1	-1	-1	1
		0	0	0	1	1	1
					-1		-1

 

Все ∆ не отрицательные (-2, 1, 0, 0, 0)

			0	0	-1	-1	-1
	-1	-2	-1	0	1	-1	1
	0	3	-1	1	0	-2	2
		-2	1	0	0	2	0

 

 

(0, 3, 2, 0, 0) – оптимальное базисное решение, так как все правые части положительные.

 

Если решать эту задачу простым СМ, то пришлось бы вводить искусственные переменные.

Основное отличие простого СМ от двойственного СМ в том, что в простом СМ сначала определяется вектор, вводимый в базис, а затем вектор, исключаемый из базиса, а в двойственном СМ этот порядок обратный.

Связь между простым и двойственным СМ существует такая, как и между двойственной и исходной задачей.

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

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

При решении простым СМ мы стремимся избавиться от отрицательных симплексных разностей, т.е. стремимся в ОДР двойственной задачи, но при этом остаемся в ОДР исходной задачи. Как только нам удается найти допустимое решение двойственной задачи при допустимом решении исходной задачи, мы получаем оптимальное решение.

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

Простой симплексный критерий обуславливает нахождение в ОДР исходной задачи (правые части положительные).

Двойственный симплексный критерий обуславливает нахождение в ОДР двойственной задачи (контроль ∆ >0).

 

Задачи для самостоятельного решения.

Решить двойственным симплексным методом[3].

       1)

    

       2)        

       

Преобразуем:

3)

                              

         

 

         4)

                              

 

Пример.

Построить двойственную задачу ЛП. Решить одну из пары задач симплексным табличным методом. По полученному решению найти оптимальное решение второй задачи. Проверить теоремы двойственности.

Max f =

Так как прямая задача – задача максимизации, то все ограничения должны иметь знак “≤”, поэтому умножаем первое ограничение на (-1):

Теперь можно записать двойственную задачу:

Min z = - y₁ + y₂

 

Решим прямую задачу:

Max f = 16/5x₁ + x₂ + 8x₃

 

 

 

Для решения задачи симплексным методом приведем ее к каноническому виду. Для этого в первое и второе ограничения введем балансовые переменные  и  соответственно:

Для получения начального базиса в первое ограничение вводим еще одну искусственную переменную :

В целевую функцию балансовые переменные входят с нулевым коэффициентом, а искусственные с очень большим коэффициентом (-М):

max f = 16/5x₁ + x₂ + 8x₃ + 0(x₄+x₅) – Mx_6.

Таблица 1.

базис	B	C	16/5	1	8	0	0	- М
		CБ	А1	А2	А3	А4	А5	А6
X6	1	- М	1	3	1	-1	0	1
X5	1	0	1	1	2	0	1	0
∆	- М		-М -16/5	-3М - 1	-М-8	-М	0	0
X2	1/3	1	1/3	1	1/3	-1/3	0	1/3
X5	2/3	0	2/3	0	5/3	1/3	1	-1/3
∆	1/3		-43/5	0	-23/3	-1/3	0	1/3+M
базис	B	C	16/5	1	8	0	0	- М
		CБ	А1	А2	А3	А4	А5	А6
X2	0	1	0	1	-1/2	-1/2	-1/2	1/2
X1	1	16/5	1	0	5/2	1/2	3/2	-1/2
∆	16/5		0	0	-1/2	11/10	43/10	—
X2	1/5	1	1/5	1	0	-2/5	-1/5	—
X3	2/5	8	2/5	0	1	1/5	3/5	-1/5
∆	17/5		1/5	0	0	6/5	23/5	—

 

Оптимальное решение прямой задачи:

Искомое значение целевой функции:

По последней таблице находим оптимальное решение двойственной задачи. Оно находится в индексной строке таблицы, в столбцах балансовых переменных А_4, А_5.

Значение целевой функции двойственной задачи:

т. е. оптимальные значения целевой функции прямой и двойственной задач совпадают. Следовательно, теорема 2 (основная теорема двойственности) выполняется.

 

Проверим теперь, будут ли выполняться остальные теоремы двойственности.

Подставим оптимальное решение  в ограничение прямой задачи:

Первое ограничение выполняется, как равенство, поэтому .

Второе ограничение выполняется, как равенство, поэтому .

Как видим, теорема 3 выполняется.

Для проверки теоремы 4 выпишем ограничение двойственной задачи при оптимальных значениях переменных:

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

Аналогично для второго ограничения:

Оно выполняется, как неравенство, следовательно, оптимальное значение переменой .

Третье ограничение:

выполняется, как равенство, поэтому оптимальное значение соответствующей переменной

.

Этим было получено оптимальное решение прямой задачи . Следовательно, теорема 4 выполняется.

 

ВАРИАНТЫ ЗАДАНИЙ

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

Задача 1.

17x₁-5x₂+x₃+x₄-8x₅→max,

3x₁-x₂-x₃+4x₄+7x₅≤11,

x₁-5x₂-5x₃+x₄+2x₅≥-8,

x₁+x₂+x₃+3x₄-x₅=4,

x₁≥0, x₄≥0.

 

Задача 2.

4x₁-6x₂-2x₃+3x₄+x₅→min,

x₁+2x₂-3x₃+x₄-3x₅≥-5,

2x₁-3x₂+x₃+x₄+2x₅≥1,

-2x₁-x₂-x₄-x₅≤3.

 

Задача 3.

3x₂-2x₃+x₄→min,

-x1+x3-x₄=5,

2x₁+x₂-2x₃+2x₄≤7,

x₁+x₂+x₃+3x₄-x₅=4,

x₁≥0, x₂≥0, x₃≥0,x₄≥0.

 

         Задача 4.

4x₁+x₂+x₃+2x₄+x₅→max,

4x₁+x₂-x₃-x₄+x₅≥9,

x₁+x₂-x₃+x₄+6x₅=10,

-x₁-3x₂+5x₃≤1,

x₁≥0, x₂≥0, x₃≥0,x₄≥0.

 

Задача 5.

 11x₁+44x₂ →max

3x₁+5x₂≥18,

X₁+9x₂≥30,

2x₁+7x₂≥27,

X₁≥0, x₂≥0

 

Задача 6.

5x₁+7x₂+13x₃ →min

2x₁+x₂+4x₃≥22,

X₁+x₂+x₃=9,

X₁+2x₂+2x₃≤18,

X₁≥0, x₂≥0, x₃ не имеет ограничений в знаке

 

Задача 7.

X₁+2x₂→max,

3x₁-4x₂[A]1,

5x₁+6x₂[B]2,

-7x₁+8x₂[C]3,

X₂≥0.

 

	A	B	C		A	B	C
1	≥	=	≤	11	≥	≤	≥
2	≥	≥	≤	12	=	≤	≥
3	≥	≤	≥	13	≥	≥	=
4	=	≥	≥	14	≥	=	≤
5	≥	≤	=	15	=	≥	≤
6	=	≤	≥	16	=	=	≥
7	≤	≥	≤	17	≥	=	≥
8	≤	≤	≥	18	≤	≥	=
9	≤	≥	≥	19	=	=	≤
10	≤	≤	=	20	≤	=	≥

 

Задача 8.

7x₁+x₃-4x₄→max,

x₁-x₂+2x₃-x₄≤6,

2x₁+x₂-x₃≤-1,

x₁,x₂,x₃,x₄≥0.

 

Задача 9.

x₁+x₃+x₅→max,

x₁+2x₂+3x₃-x₄-x₅≤6,

x₁-x₂-2x₃+x₄+x₅≤5,

x₁,x₂,x₃,x₄,x₅≥0.

 

 

Задача 10.

4x₁+5x₂+2x₃+x₄+x₅→min,

-3x₁+5x₂+4x₃+2x₄+2x₅=1,

-4x₁-6x₂-x₃+x₄+3x₅=-1,

x₁,x₂,x₃,x₄,x₅≥0.

 

Задача 11.

6x₁+3x₂-x₃-2x₄→max,

3x₁+2x₂+x₃+x₄≤0,

2x₁+2x₂-x₃-x₄=1,

x₂≥0,x₃≥0,x₄≥0.

СПИСОК ЛИТЕРАТУРЫ

1. Вентцель Е.С. Исследование операций. Задачи, принципы, методология: Учеб.пособие для вузов.-М.: Дрофа, 2007.

2. Зайченко Ю.П. Исследование операций.-К.: Выща шк., 2007.

3. Зайченко Ю.П. Исследование операций. Сборник задач.-К.: Выща шк., 2007.

4. Куликов Ю.Г., Шеховцова Н.Ф., Зикеева Л.П. Экономико-математические методы и модели (раздел «Линейное программирование»): Учебное пособие для практических занятий.-М.: Московский психолого-социальный институт, 2006.

 

 

---

Дата добавления: 2018-04-15; просмотров: 895; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!