Линейное программирование
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
?: . Для получения оптимального плана подставим координаты в целевую функцию и получим: , оптимальный план: .
Задание №2. Решить транспортную задачу
Решить транспортную задачу. Заданы мощности поставщиков аi (i=1,2,3), емкости потребителей bj (j=1,2,3) и матрица стоимостей перевозок единицы продукции от каждого поставщика каждому потребителю. Требуется найти план перевозок, при котором суммарные транспортные затраты будут наименьшими.
Исходные данные:
Таблица №5 - Исходные данные
ПотребителиB1B2B3Поставщики142022A150389A218345А312276
Решить задачу можно в том случае если задача закрыта, то есть должно выполнять равенство: 50+18+12=14+20+22, получается 8056; введем дополнительного потребителя
-56=24.
Таблица №6 - Ввод дополнительного потребителя
ПотребителиB1B2B3ВфПоставщики14202224A1503890A2183450А3122760
Составим исходный план перевозок Х1 (Рисунок 4) методом северо-западного угла, распределяя мощности поставщиков по порядку между потребителями, так чтобы каждая перевозка была максимально возможной.
План перевозок оформим в виде таблицы, разделенной на клетки. В центре каждой клетки плана поместим перевозки , а в правом верхнем углу - стоимость перевозки единицы продукции. В клетки, соответствующие нулевым перевозкам, нули не вписываем, оставляя их пустыми. В таком случае план Х1 будет содержать не больше, чем m+n-1 положительных перевозок или занятых клеток, где m - число поставщиков, n - число потребителей. Остальные компоненты плана Х1, соответствующие нулевым перевозкам, будем называть свободными клетками. Если число занятых клеток K = m + n -1, то план перевозок называется невырожденным, если K < m + n - 1, то вырожденным.
Подсчитаем суммарную стоимость перевозок по плану Х1:
Проверим план Х1 (Рисунок 4) на оптимальность. Найдем потенциалы поставщиков и потенциалы потребителей.
Рисунок 4 - План Х1 (План )
По условию для занятых клеток:
Один из потенциалов всегда задается произвольно, зададим . Тогда из системы получим , , , , , , . Эти потенциалы полезно записать справа и снизу от плана .
По условию для свободных клеток:
Подставим потенциалы в неравенства, получим:
; 4 > 0; -1 < 3; 4 = 4
; -4 < 2; 4 < 7; 5 < 6
Мы видим, что не выполняется одно неравенство
Следовательно, план можно улучшить, введя в план перевозку . С этой целью составим цикл, имеющий начало в свободной клетке (4, 1), а остальные вершины - в занятых клетках, последовательно увеличивая и уменьшая перевозки, попавшие в цикл, на величину . Цикл и последовательность увеличения и уменьшения перевозок изображено на рисунке 5.
Важно отметить, что при составлении цикла следует двигаться только по горизонтали или вертикали, так что бы в каждую строку и каждый столбец плана перевозок, охваченных циклом, попали только две перевозки.
Выбираем , то есть в качестве выбирается наименьшая из перевозок, из которых вычитается. При включении в план перевозки =12 суммарная стоимость перевозок изменится на , то есть уменьшится на 48 ед. и для нового плана составит:
Рисунок 6 - План Х2 (План )
По условию для занятых клеток:
По условию для свободных клеток:
Подставим потенциалы в неравенства, получим:
; -1 0
; 3 > 2; 8 > 7; 9 > 6
Мы видим, что не выполняются три неравенство причем
;
;
.
Следовательно, план можно улучшить, введя в план перевозку , для которой разность оказалась меньше разностей . С этой целью составим цикл, имеющий начало в свободной клетке (3, 3), а остальные вершины - в занятых клетках, последовательно увеличивая и уменьшая перевозки, попавшие в цикл, на величину . Цикл и последовательность увеличения и уменьшения перевозок изображено на рисунке 6.
Выбираем , то есть в качестве выбирается наименьшая из перевозок, из которых вычитается. При включении в план перевозки =4 суммарная стоимость перевозок изменится на , то есть уменьшится на 12 ед. и для нового плана составит:
Рисунок 7 - План Х3 (План )
По условию для занятых клеток:
По условию для свободных клеток:
Подставим потенциалы в неравенства, получим:
; 6 = 6; 2 4
; -1 7
Мы видим, что не выполняются три неравенство причем
;
;
.
Следовательно, план можно улучшить, введя в план перевозку , для которой разность оказалась меньше разностей . С этой целью составим цикл, имеющий начало в свободной клетке (2, 2), а остальные вершины - в занятых клетках, последовательно увеличивая и уменьшая перевозки, попавшие в цикл, на величину . Цикл и последовательность увеличения и уменьшения перевозок изображено на рисунке 7.
Выбираем , то есть в качестве выбирается наименьшая из перевозок, из которых вычитается. При включении в план перевозки =8 суммарная стоимость перевозок изменится на , то есть уменьшится на 24 ед. и для нового плана составит:
Рисунок 8 - План Х4
По условию для занятых клеток:
По условию для свободных клеток:
Подставим потенциалы в неравенства, получим:
; 9 = 9; 3 = 3; -4 < 4
; 0 < 2; 5 < 7; -3 < 0
Из уравнений и неравенств следует, что он?/p>