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

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

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

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

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

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

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

 

БП СП					B
		-1		-1
			-1		-1
Z	-7		-1

 

 

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

.

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

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

 

БП СП					B
		-1		-1
			-1		-1
Z	-7		-1

 

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

БП СП					B
		-1		-1
			-1		-1
Z	-7		-1

 

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

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

 

БП СП					B
		-1		-1
			-1		-1
Z	-7		-1

 

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

 

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

 

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

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

 

БП СП					B
3
Z

 

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

БП СП					B
3			-1
Z

 

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

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

 

 

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

 

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

 

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

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

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

 

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

 

 

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

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

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

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

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

 

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

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

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

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

 

БП СП					B
3
Z

 

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

 

БП СП					B
3
Z

 

 

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

БП СП					B
3
Z

 

 

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

БП СП					B
3
Z

 

 

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

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

БП СП					B
3
Z

 

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

 

Ответ: Z_max= , ,