Контрольная работа по «Методы оптимальных решений»

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

2. Подсчитаем число занятых  клеток таблицы, их 6, а должно  быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 12*61 + 14*51 + 10*89 + 5*95 + 11*34 + 7*70  = 3675

II. Улучшение опорного  плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v2 = 12; 0 + v2 = 12; v2 = 12

u2 + v2 = 10; 12 + u2 = 10; u2 = -2

u1 + v3 = 14; 0 + v3 = 14; v3 = 14

u3 + v3 = 11; 14 + u3 = 11; u3 = -3

u3 + v1 = 5; -3 + v1 = 5; v1 = 8

u3 + v4 = 7; -3 + v4 = 7; v4 = 10

 

	v1=8	v2=12	v3=14	v4=10
u1=0	18	12[61]	14[51]	9
u2=-2	15	10[89]	17	8
u3=-3	5[95]	13	11[34]	7[70]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;4): 0 + 10 > 9; ∆14 = 0 + 10 - 9 = 1

Выбираем максимальную оценку свободной клетки (1;4): 9

Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

Пункты отправления	В1	В2	В3	В4	Запасы
А1	18	12[61]	14[51][-]	9[+]	112
А2	15	10[89]	17	8	89
А3	5[95]	13	11[34][+]	7[70][-]	199
Потребности	95	150	85	70

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 51. Прибавляем 51 к объемам грузов, стоящих в плюсовых клетках и вычитаем 51 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

Пункты отправления	В1	В2	В3	В4	Запасы
А1	18	12[61]	14	9[51]	112
А2	15	10[89]	17	8	89
А3	5[95]	13	11[85]	7[19]	199
Потребности	95	150	85	70

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v2 = 12; 0 + v2 = 12; v2 = 12

u2 + v2 = 10; 12 + u2 = 10; u2 = -2

u1 + v4 = 9; 0 + v4 = 9; v4 = 9

u3 + v4 = 7; 9 + u3 = 7; u3 = -2

u3 + v1 = 5; -2 + v1 = 5; v1 = 7

u3 + v3 = 11; -2 + v3 = 11; v3 = 13

 

	v1=7	v2=12	v3=13	v4=9
u1=0	18	12[61]	14	9[51]
u2=-2	15	10[89]	17	8
u3=-2	5[95]	13	11[85]	7[19]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.

Минимальные затраты составят: F(x) = 12*61 + 9*51 + 10*89 + 5*95 + 11*85 + 7*19  = 3624

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 2-й магазин (61), в 4-й магазин (51)

Из 2-го склада необходимо весь груз направить в 2-й магазин

Из 3-го склада необходимо груз направить в 1-й магазин (95), в 3-й магазин (85), в 4-й магазин (19)