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

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

 

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

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

 

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

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

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

 

БП СП			B
Z

 

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

БП СП			B
Z

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

БП СП			B
Z

 

d.

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

БП СП			B
		-1
Z

 

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

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

 

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

 

БП СП			B
		-1
Z	-2

 

6. В Z строке есть отрицательные элементы (-2), следовательно оптимальное решение не найдено и необходимо выполнить симплекс преобразование для СТ2.

7. Рассмотрим СТ2:

БП СП			B
		-1
Z	-2

 

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

 

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

БП СП			B
		-1
Z	-2

 

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

 

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

БП СП			B
		-1
Z	-2

 

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

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

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

БП СП			B
Z

 

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

c.

БП СП			B
Z

 

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

 

БП СП			B
Z

 

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

 

БП СП			B
	-1
Z

 

 

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

После вычисления всех элементов таблицы СТ3 выглядит так:

БП СП			B
	-1
Z

 

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

 

Ответ: Z_max=8 при этом ,