Симплекс метод. Реферат "Решение задачи линейного программирования симплексметодом" 2008

• Название: Реферат "Решение задачи линейного программирования симплексметодом" 2008
• Дата: 20.05.2022
• Размер: 358.5 Kb.
• Имя файла: Симплекс метод.doc
• Тип: Реферат; #540950
• страница: 3 из 3

- строке максимально отрицательный коэффициент: - включаемая переменная.

6. Определение разрешающей строки: – исключаемая переменная.

7. Разрешающий элемент РЭ = 1.

8. Получение матрицы перехода

, где В(0) - матрица перехода

9. Определение элементов таблицы СТ(1) = В(0) СТ(0);

10. Исследование z-строки СТ(1) на условие оптимальности:

СТ(1)

	z								ПЧ
z	1	0	4+7M	-7M-4	-3M-1	0	0	1+4M	-12M
	0	0	1	-1	1	1	0	-1	4
	0	0	-7	7	3	0	1	-3	12
	0	1	1	-1	-1	0	0	1	0

СТ(2)

	z								ПЧ
z	1	0	0	0	5/7	0	M+4/7	M-5/7	48/7
	0	0	0	0	10/7	1	1/7	-10/7	40/7
	0	0	-1	1	3/7	0	1/7	-3/7	12/7
	0	1	0	0	-4/7	0	1/7	4/7	12/7

СТ(2) – оптимальная, т. к. коэффициенты при НБП .

, , .

3. Решение задачи линейного программирования симплекс-методом.

Двойственная задача.

Составим двойственную задачу по условиям прямой задачи и определим области допустимых решений ДП:

Прямая задачаДвойственная задача









(1)

(2)







Итак, получено: , , .

2. Приведём запись двойственной задачи к канонической форме. На основании полученных ОДР двойственных переменных введём необходимые подстановки: .

Для удобства решения свернём ограничения (1) и (2) в одно со знаком равенства, а также введем в ограничения и целевую функцию избыточные, остаточные и искусственные переменные.



(3)

(4)

3. Решим ДЗ симплекс методом:

Из (3): выразим

Из (4) выразим:



СТ(0)

	W								ПЧ
W	1	-4-M	7M-12	12-7M	0	-M	0	0	4M
	0	1	3	-3	-1	-1	1	0	1
	0	-2	4	-4	1	0	0	1	3

СТ(1)

	W								ПЧ
W	1	-10/3M	0	0	7/3M-4	4/3M-4	-7/3M+4	0	5/3M+4
	0	1/3	1	-1	-1/3	-1/3	1/3	0	1/3
	0	-10/3	0	0	7/3	4/3	-4/3	1	5/3

СТ(2)

	W								ПЧ
W	1	-40/7	0	0	0	-12/7	-7/3M+4	-M+12/7	48/7
	0	-1/7	1	-1	0	-1/7	1/3	1/7	4/7
	0	-10/7	0	0	1	4/7	-4/3	-3/7	5/7

СТ(2) – оптимальная, т. к. коэффициенты при

, ,



Задание:

1. Изучить методы решения задачи линейного программирования (графический и симплекс-метод):

2. Для заданного варианта получить решение задачи линейного программирования:

- графическим методом;

- симплекс методом для прямой задачи;

- симплекс методом для двойственной задачи.