Контрольная работа: Линейная алгебра и математическое программирование

Δ15 = 1 + – с 15 = 0 + 9 – 8 = 1 0

Δ21 = + – с 21 = -5 + 5 – 6 = -6 0

Δ23 = + – с 23 = -5 + 10 – 15 = -10 0

Δ31 = + – с 31 = 0 + 5 – 25 = -20 0

Δ34 = + – с 34 = 0 + 11 – 15 = -4 0

Δ35 = + – с 35 = 0 + 9 – 18 = -9 0

Получили одну оценку Δ15 = 1 0 следовательно, исходное решение не является оптимальным и его можно улучшить.

Переход от одного решения транспортной задачи к другому.

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

Для свободной клетки Δ15 = 1 0 строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое решение. Это решение проверяем на оптимальность, и так далее до тех пор, пока не получим оптимальное решение.

Х₂ =

Стоимость перевозки при исходном решении составляет

f₂ = 175 * 5 + 215 * 10 + 10 * 20 + 240 * 10 + 160 * 6 + 175 * 8 + 25 * 4 = 8085.

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

bi ai		1	2	3	4	5
		175	225	240	160	200	𝛼i
1	350	5 175	15	18	16	8 175	0
2	400	6	10 215	15	6 160	« 2 3 4 5 6 7 8 9 10 11 » К-во Просмотров: 346 Бесплатно скачать Контрольная работа: Линейная алгебра и математическое программирование >>> Скачать <<< Меню Поиск