(1; 1)

0 + 1 – 5 = –4

(1; 2)

0 + 2 – 4 = –2

(1; 5)

0 – 4 – 0 = –4

(2; 3)

1 + 3 – 5 = –1

(2; 4)

1 + 1 – 8 = –6

(2; 5)

1 – 4 – 0 = –4

(3; 1)

4 + 1 – 6 = –1

(3; 2)

4 + 2 – 8 = –2

(3; 3)

4 + 3 – 7 = 0

(3; 4)

4 + 1 – 10 = –5

(4; 1)

4 + 1 – 5 = 0

(4; 4)

4 + 1 – 2 = 3

Т.к. среди свободных клеток есть такие, в которых второе условие оптимальности не выполняется, то план не оптимален.

Осуществим переход к нехудшему опорному плану. Наиболее перспективная для заполнения клетка (4; 4), т. к. ей соответствует наибольшая положительная оценка

4 + 1 – 2 = 3.

Найдем цикл перераспределения груза для этой клетки.

Выбранной для заполнения клетке присваиваем знак «+», далее знаки чередуем. Среди вершин со знаком «–» выбираем наименьшую поставку.

– объем перепоставки.

Перераспределим поставки по циклу, тем самым перейдем к новому опорному плану.

	31		52		17		20	45
35	5	4	3	1	0	0
	17		18
40	2	3	5	8	0	–2
	31		9
40	6	8	7	10	0	1
	40
50	5	6	7	2	0	1
	43		2		5
	4		5		3		1	–1	Таб.2

Транспортные затраты, соответствующие опорному плану:

(ден. ед.).

Исследуем опорный план на оптимальность. Найдем значения потенциалов, используя первое условие оптимальности. Для заполненных поставками клеток

Проверим выполнение второго условия оптимальности. Для всех пустых клеток должно выполняться неравенство:

Выпишем клетки, в которых условие нарушено:

(1; 2)

0 + 5 – 4 = 1

Осуществим переход к нехудшему опорному плану. Наиболее перспективная для заполнения клетка (1; 2), т. к. ей соответствует положительная оценка

1. Найдем цикл перераспределения груза для этой клетки.

– объем перепоставки.

Число заполненных клеток распределительной таблицы 8 равно рангу матрицы задачи r= 8, следовательно, опорный план (таб. 3) является невырожденным.

	31		52		17		20	45
35	5	4	3	1	0	0
	18		17
40	2	3	5	8	0	–1
	31		9
40	6	8	7	10	0	2
	40
50	5	6	7	2	0	2
	25		20		5
	3		4		3		0	–2	Таб.3

Транспортные затраты, соответствующие опорному плану:

(ден. ед.).

Исследуем опорный план на оптимальность.

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

Проверим выполнение второго условия оптимальности. Для всех пустых клеток должно выполняться неравенство:

Второе условие оптимальности выполняется для всех свободных клеток, следовательно, план оптимален.

Наименьшие транспортные затраты

Ответ:

; оптимальный план распределения поставок расположен в таб. 3.

Задания для самостоятельной работы.

Составить план перевозок с минимальными транспортными затратами.

а)

б)

Решение оптимизационных задач с помощью Excel

При решении оптимизационных экономических задач необходимо пройти через следующие этапы:

· Составить математическую модель экономической задачи;

· Решить полученную экстремальную математическую задачу;

· Дать экономическую интерпретацию ответу.

Рассмотрим прохождение этих этапов на примере задачи об использовании ресурсов.

Пример. Для изготовления изделий двух видов А и В на заводе используют сырье четырех типов (І, ІІ, ІІІ, IV). Для выпуска изделия А необходимо 2 единицы сырья І типа; 1 ед. сырья ІІ типа; 2 ед. сырья ІІІ типа; 1 ед. сырья IV типа. Для изготовления изделия В требуется 3 единицы сырья І типа; 1 ед. сырья ІІ типа; 1 ед. сырья ІІІ типа. Запасы сырья составляют: І типа – 21 ед., ІІ типа – 8 ед., ІІІ типа – 12 ед., IV типа – 5 ед. Выпуск одного изделия типа А приносит 3 грн. прибыли, а одного изделия типа В – 2 грн. прибыли. Составить план производства, обеспечивающий наибольшую прибыль.

Практикум по решению линейных задач математического программирования (стр. 10 из 11)

Решение оптимизационных задач с помощью Excel