Найти оптимальный план перевозок, отметив при этом единственность или не единственность оптимального плана.
Вариант 7. Компания владеет тремя фабриками М1, М2, М3 способными произвести еженедельно 50, 25 и 25 тыс. изделий соответственно. По договорам компания поставляет продукцию четырем заказчикам С1, С2, С3 и С4, каждому из которых требуется 15, 20, 20 и 30 тыс изделий еженедельно. Стоимости производства и транспортировки 1 тыс. изделий с фабрики М1 каждому из заказчиков составляют 13, 17, 17 и 14 ден. единиц соответственно; аналогичные стоимости для фабрики М2 равны 18, 16, 16 и 18 ден. единиц, а для фабрики М3 – 12, 14, 19 и 17 ден. единиц. Определить оптимальный план производства и транспортировки продукции, минимизирующий общие затраты компании.
Нужно полное решение этой работы?
Ответ
Pопт=
1210
10003010002005520000
Решение
C1 C2 C3 C4 Поставщики
M1 13 17 17 14 50
M2 18 16 16 18 25
M3 12 14 19 17 25
Потребители 15 20 20 30
Проверим необходимое и достаточное условие разрешимости задачи:
M=50+25+25=100;C=15+20+20+30=85,C<M.
Суммарная потребность груза меньше запасов груза у поставщиков. Следовательно, задача является открытой. Чтобы получить закрытую модель, введем фиктивного потребителя С5 с запасом, равным 100-85=15. Тарифы перевозки единицы груза от поставщика всем потребителям положим равными нулю. Запасы фиктивного поставщика будем рассматривать в последний момент.
Математическая модель:
Обозначим x- количество продукта, доставляемого от i-го поставщика к j-му потребителю. Тогда модель имеет следующий вид:
L = 13x11 + 17х12 + 17х13 ++14х14+18 х21 +16х22 + 16х23 + +18х24+12х31 + 14х32 + 19х33 + 17х34 → min
left0x11 + х12 + х13 +х14= 50
х21 +х22 + х23 +х24= 25
х31 + х32 + х33+х34 = 25
x11 + х21 + х31 1 = 15
х 12 +х22 +х32 = 20
х13 + х23 + х33 3 = 20
х14 + х24 +х34 = 30
Найдем начальное решение методом минимального элемента.
Минимальный элемент матрицы тарифов находится в ячейке М3С1 и равен12
. Запасы поставщика М3 составляют 25 ед. Потребность потребителя С1 составляет 15 ед. От поставщика М3 к потребителю С1 будем доставлять 15 ед. Мы полностью исчерпали запасы потребителя С1. Вычеркиваем столбец 1 таблицы, т.е. исключаем ее из дальнейшего рассмотрения. Продолжаем данные рассуждения аналогично, получим опорное решение:
C1 C2 C3 С4= 30
С5= 15
M1
5
17
30
14
15
0
M2
10
16
15
16
M3 15
12
10
14
Перемножим числа стоящие в одной клетке (для всех клеток) затем полученные произведения сложим. Получим значение суммарных затрат, для данного начального решения.
Pнач=
1225
Проверим полученный опорный план на HYPERLINK "javascript:%20void%20Tips('virozd_tz.php');" невырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1 . В нашем случае N=7, n+m=5+3=8 , что удовлетворяет условию HYPERLINK "javascript:%20void%20Tips('virozd_tz.php');" невырожденности плана. Проведем поэтапное улучшение начального решения, используя метод потенциалов.Составим вспомогательную рабочую матрицу затрат