Симплекс метод решения задачи линейного программирования (стр. 1 из 2)

Задача №1 (Симплекс метод решения задачи линейного программирования.)

Найти F_max = 9x₁+ 10x₂ + 16x_3, при ограничениях:

Запишем задачу в каноническом виде:

F=9x₁+ 10x₂ + 16x₃ →max

Заполним начальную таблицу:

Таблица 0.

0	9	10	16	0	0	0	Отношение,θ
i		Базис
1	0		360	18	15	12	1	0	0	30
2	0		192	6	4	8	0	1	0	24
3	0		180	5	3	3	0	0	1	60
∆j		0	-9	-10	-16	0	0	0
Zj		0	0	0	0	0	0	0

Zj вычисляется по формуле

Оценки (∆j) вычисляются по формуле

, где - коэффициент из первой строки таблицы.

Выбираем минимальную (отрицательную) оценку. Она определяет направляющий столбец.

Заполняем столбец «θ», по минимальному значению определяем направляющую строку.

На пересечение строки и столбца находится направляющий элемент.

Заполняем новую таблицу

Таблица 1.

0	9	10	16	0	0	0	Отношение,θ
i		Базис
1	0		72	9	9	0	1		0	8
2	16		24			1	0		0	48
3	0		108			0	0	-	1	72
∆j		384	3	-2	0	0	2	0
Zj		384	12	8	0	0	2	0

Изменяется базис в позиции направляющей строки. Базисным становится вектор, соответствующий направляющему столбцу, т. е.

Столбец

становится базисным, то есть единичным.

Новые значения в направляющей строке получаем делением элементов этой строки на направляющий элемент.

Остальные элементы в небазисных столбцах и в столбце

вычисляем по правилу треугольника.

Выбираем минимальную отрицательную оценку. Она определяет направляющий столбец.

Заполняем столбец «θ»

По минимальному значению определяем направляющую строку.

На пересечении направляющей строки и столбца находится направляющий элемент.

Заполнение второй таблицы осуществляется по аналогии с предыдущей.

Таблица 2.

0	9	10	16	0	0	0	Отношение,θ
i		Базис
1	10		8	1	1	0		-	0	______
2	16		20		0	1	-		0	______
3	0		96		0	0		-	1	______
∆j		400	5	0	0			0
Zj		400	14	10	16			0

Так как нет отрицательных оценок ∆j, значит выполняется признак оптимальности и не вводились искусственные переменные, то получено оптимальное решение.

Ответ:

Максимальное значение функции F_max =400 достигается в точке с координатами:

=0

=8

=20

=0

=0

=96

Задача №2 (Метод Литтла)

Найти кратчайший путь в графе, заданном графически в виде чертежа, методом Литтла.

Из чертежа запишем матрицу расстояний. (Расстояние от т.1 до т.2 равно:

, и т.д.)

1	2	3	4	5	6
1	∞	18,87	49,48	51,86	80,51	97,42
2	18,87	∞	32,06	34,48	65,15	84,01
3	49,48	32,06	∞	31,76	61,19	83,20
4	51,86	34,48	31,76	∞	32,14	53,15
5	80,51	65,15	61,19	32,14	∞	22,14
6	97,42	84,01	83,20	53,15	22,14	∞

Предположим что кратчайший путь будет следующим:

т.1→ т.2→ т.3→ т.4→ т.5→ т.6→т.1 и составит

Решение: Первый этап.