Методы оптимальных решений

 

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

Теперь решим эту задачу графическим методом. Построим область допустимых значений, ограниченную прямыми линиями.

На рисунке 1 заштрихована область допустимых решений. Для определения направления движения к оптимуму построим вектор-градиент Ñ, координаты которого являются частными производными целевой функции, т.е. .

Что бы построить этот вектор, нужно соединить точку (-5; 2) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации – в противоположном направлении. Для удобства можно строить вектор, пропорциональный вектору Ñ. Так, на рисунке 1 изображен вектор градиент (-5; 2).

 

Рисунок 1. Максимум целевой функции достигается в точке (0, 4).

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

Отсюда легко записать решение исходной задачи:

б) 

Построим область допустимых значений, ограниченную прямыми линиями.

На рисунке 2 заштрихована область допустимых решений. Для определения направления движения к оптимуму построим вектор-градиент Ñ, координаты которого являются частными производными целевой функции, т.е. .

Что бы построить этот вектор, нужно соединить точку (12; 4) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации – в противоположном направлении. Для удобства можно строить вектор, пропорциональный вектору Ñ. Так, на рисунке 2 изображен вектор градиент (12; 4).

Рисунок 2. Минимум целевой функции достигается в точке (0, 0).

Отсюда легко записать решение исходной задачи:

 

Задание 3

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

Допустим имеется три поставщика продукции с соответствующими предложениями а1, а2 и а3 и три потребителя, спрос которых составляет в1, в2 и в3 соответственно. Стоимость перевозки единицы груза из каждого пункта отправления до каждого пункта назначения задается матрицей С.

Решение.

Определим баланс предложения и спроса:

Так как общее предложение превышает общий спрос, то необходимо ввести в модель фиктивный пункт потребления (Вn+1) в n + 1-м столбце матрицы транспортной задачи. При этом стоимости перевозки для фиктивного пункта потребления равны нулю.

Потребность в грузе фиктивного пункта назначения равна разности предложения и спроса.

Составим исходную транспортную матрицу.

Таблица 6

Исходная транспортная матрица

Пункт назначения Пункт отправления		В1		В2		В3		В4
		98		122		100		80
А1	140		4		2		3		0
А2	120		5		3		2		0
А3	140		1		2		3		0

 

Процедура построения потенциального (оптимального) плана состоит в следующем.

В качестве первого приближения к оптимальному плану берется любой допустимый план (например, построенный методом минимального элемента) (таблица 3).

Таблица 7

Метод минимального элемента

Пункт назначения Пункт отправления		В1		В2		В3		В4
		98		122		100		80
А1	140		4	60	2		3	80	0
А2	120		5	20	3	100	2		0
А3	140	98	1	42	2		3		0

 

Общие затраты на транспортировку составляют:

В этом плане m + n – 1, где m – число строк, n – число столбцов транспортной таблицы. Для этого плана можно определить платежи (αi и βj) так, чтобы в каждой базисной клетке выполнялось условие:

Уравнений всего m + n – 1, а число неизвестных равно m + n. Следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из m + n – 1 можно найти остальные платежи, а по ним вычислить псевдостоимости для каждой свободной клетки.

 

Таблица 3

Расстановка потенциалов

Пункт назначения Пункт отправления		В1		В2		В3		В4		αi
		98		122		100		80
А1	140		4	60	2		3	80	0
А2	120		5	20	3	100	2		0
А3	140	98	1	42	2		3		0
βj

 

Так как в ячейке А2В4 псевдостоимость больше стоимости, то план не является оптимальным и может быть улучшен переносом перевозок по циклу, соответствующему данной свободной клетке. Цена этого цикла равна разности между стоимостью и псевдостоимостью в этой свободной клетке.

После этого необходимо подсчитать потенциалы.

Таблица 8

Перераспределение поставок

Пункт назначения Пункт отправления		В1		В2		В3		В4		αi
		98		122		100		80
А1	140		4	80	2		3	60	0
					+				-
А2	120		5		3	100	2	20	0
									+
А3	140	98	1	42	2		3		0
βj

 

Таким образом, получаем оптимальный план. При этом стоимость всей перевозки составляет:

 

Задание 4

Построить сетевую модель выполнения комплекса работ и рассчитать  основные временные параметры для всех событий и работ.

Таблица 9

Код работ	to	tнв	tп
1-2	2	3	4
1-4	3	4	5
1-6	4	5	7
2-3	1	3	4
2-6	1	2	4
3-5	1	5	9
4-6	0	0	0
5-6	0	0	0
6-7	2	3	4
6-8	4	5	6
7-8	0	0	0
8-9	5	6	7
8-10	6	7	8
8-11	6	7	10
8-12	6	8	10
9-12	0	0	0
10-13	2	3	4
11-12	2	4	5
12-13	2	3	5