2.6 Задача 3

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

1. Приводим заданную систему ограничений к каноническому виду:

Замечание: Задача ЛП в каноническом виде выглядит так:

Все ограничения должны быть типа «меньше или равно».

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

2. Составляем первую укороченную симплекс-таблицу СТ1:

БП СП					B
	1	-1	2	-1	6
	2	1	-1	0	-1
Z	-7	0	-1	4	0

В столбце свободных членов есть отрицательные элементы, следовательно, необходимо применить “Алгоритм 2 Симплекс преобразования на основе укороченных симплекс таблиц”

.

3. Выберем строку с наименьшим отрицательным свободным членом в B-столбце

Следовательно, s=2.

БП СП					B
	1	-1	2	-1	6
	2	1	-1	0	-1
Z	-7	0	-1	4	0

4. Рассмотрим элементы s-ой строки. Среди элементов s-ой строки есть отрицательный элемент - -1, следовательно, система совместна, и в качестве разрешающего столбца выбираем столбец, содержащий этот отрицательный элемент в s-ой строке:

БП СП					B
	1	-1	2	-1	6
	2	1	-1	0	-1
Z	-7	0	-1	4	0

5. Выбираем разрешающую строку k, которая соответствует наименьшему положительному из отношений элементов правой части уравнений на соответствующие элементы разрешающего столбца:

Минимальное отношение соответствует второй строке, следовательно, k=2.

БП СП					B
	1	-1	2	-1	6
	2	1	-1	0	-1
Z	-7	0	-1	4	0

6. Тогда элемент стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим элементом

7. Далее выполняем все п.4 “Алгоритм 1 Симплекс преобразования на основе укороченных симплекс таблиц”.

Переходим к новой симплекс таблице СТ2 по следующим правилам:

1. Меняем местами СП и БП соответствующие разрешающему элементу.

БП СП					B
3
Z

2. На месте разрешающего элемента в новой таблице стоит величина ему обратная:

БП СП					B
3			-1
Z

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

БП СП					B
3	-2	-1	-1	0	1
Z

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

БП СП					B
			-2
3	-2	-1	-1	0	1
Z			1

5. Все остальные элементы матрицы вычисляются по формулам:

Например, вычислим некоторые элементы таблицы :

Полученная СТ2 следующая:

БП СП					B
	5	1	-2	-1	4
3	-2	-1	-1	0	1
Z	-9	-1	-1	4	1

8. Все элементы столбца свободных членов положительные, а в строке Z есть отрицательные элементы, следовательно, далее необходимо применить “Алгоритм 1 Симплекс преобразования на основе укороченных симплекс таблиц”.

9. Выбираем разрешающий столбец l соответствующий наименьшему отрицательному элементу в Z строке:

Следовательно,

БП СП					B
	5	1	-2	-1	4
3	-2	-1	-1	0	1
Z	-9	-1	-1	4	1

10. Выбираем разрешающую строку k, которая соответствует наименьшему положительному из отношений элементов правой части уравнений (элементы столбца B) на соответствующие элементы разрешающего столбца:

Следовательно, , так как минимальное положительное отношение соответствует первой строке.

11. Тогда элемент стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим элементом

12. Переходим к новой симплекс таблице СТ2 по следующим правилам:

    1. Меняем местами СП и БП соответствующие разрешающему элементу.

БП СП					B
3
Z

2. На месте разрешающего элемента в новой таблице стоит величина ему обратная:

БП СП					B
3
Z

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

БП СП					B
3
Z

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

БП СП					B
3
Z

5. Все остальные элементы матрицы вычисляются по формулам:

Полученная СТ3 следующая:

БП СП					B
3
Z

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

Ответ: Z_max=, ,