Индивидуальное задание №1 (стр. 6 )

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты

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

Вычислим значения Di по строкам как частное от деления

и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей

Разрешающий элемент равен 2 и находится на пересечении ведущего столбца и ведущей строки

Формируем следующую часть симплексной таблицы.

Вместо переменной x5 в план 2 войдет переменная x1

Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x5 плана 1 на разрешающий элемент РЭ=2

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x1 плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x1 и столбец x1 .

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

Представим расчет каждого элемента в виде таблицы:

B	x1	x2	x3	x4	x5
400 / 2 = 200	2 / 2 = 1	2 / 2 = 1	0 / 2 = 0	-1 / 2 = -0.5	1 / 2 = 0.5

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

Окончательный вариант симплекс-таблицы:

План	Базис	В	x1	x2	x3	x4	x5
3	x3	450	0	0.5	1	0.75	-0.25
	x1	200	1	1	0	-0.5	0.5
Индексная строка	F(X3)	650	0	0.5	0	0.25	0.25

Оптимальный план можно записать так:

x3 = 450

x1 = 200

F(X) = 1*200 + 1*450 = 650

Сколько изделий каждого вида необходимо произвести, чтобы получить максимум прибыли при условии, что необходимо выполнить план выпуска?

x1 + 2x2 + 2x3 ≤ 1100

3x1 + 4x2 + 2x3 ≤ 1500

x1 = 100

x2 = 100

x3 = 300

xi ≥ 0

Целевая функция:

F(x) = 2x1 + x2 + 3x3 → max

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

x1 = 100

x2 = 100

x3 = 300

F(X) = 2*100 + 1*100 + 3*300 = 1200

Задание №2

Решение задач линейного программирования двойственным симплекс-методом (P – методом).

Условие задачи.

I вариант

min (3x1+4x2)

при следующих ограничениях:

x1+x2<=4

2x1+x2>=3

3x1+2x2>=6

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

Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).

Определим минимальное значение целевой функции F(X) = 3x1+4x2 при следующих условиях-ограничений.

x1+x2≤4

-2x1-x2≤-3

-3x1-2x2≤-6

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

1x1 + 1x2 + 1x3 + 0x4 + 0x5 = 4

-2x1-1x2 + 0x3 + 1x4 + 0x5 = -3

-3x1-2x2 + 0x3 + 0x4 + 1x5 = -6

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

Решим систему уравнений относительно базисных переменных:

x3, x4, x5,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,4,-3,-6)

План	Базис	В	x1	x2	x3	x4	x5
0	x3	4	1	1	1	0	0
	x4	-3	-2	-1	0	1	0
	x5	-6	-3	-2	0	0	1
Индексная строка	F(X0)	0	-3	-4	0	0	0

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

Среди отрицательных значений базисных переменных выбираем наибольший по модулю.

Ведущей будет 3-ая строка, а переменную x5 следует вывести из базиса.

В строку θ заносим следующие величины:

Минимальное значение θ соответствует 1-му столбцу, т. е. переменную x1 необходимо ввести в базис.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный -3.

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

План	Базис	В	x1	x2	x3	x4	x5
0	x3	4	1	1	1	0	0
	x4	-3	-2	-1	0	1	0
	x1	-6	-3	-2	0	0	1
Индексная строка	F(X0)	0	-3	-4	0	0	0

Представим расчет каждого элемента в виде таблицы:

B	x1	x2	x3	x4	x5
2 / 1 = 2	1 / 1 = 1	0.67 / 1 = 0.67	0 / 1 = 0	0 / 1 = 0	-0.33 / 1 = -0.33

В базисном столбце все элементы положительные.

Конец итераций: найден оптимальный план

Окончательный вариант симплекс-таблицы:

План	Базис	В	x1	x2	x3	x4	x5
1	x3	2	0	0.33	1	0	0.33
	x4	1	0	0.33	0	1	-0.67
	x1	2	1	0.67	0	0	-0.33
Индексная строка	F(X1)	6	0	-2	0	0	-1

Оптимальный план можно записать так:

x1 = 2

x2 = 0

F(X) = 3*2 = 6