Методы оптимизации в технико-экономических задачах
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
а или столбец и процесс повторяется.
Опорный план приведен в таблице.
Потребители ЗаводыB1B2B3B4В5ЗапасыA15 123 1224 10 2524A230 02 122 1416 7 15A330 24 27 29 1610 16А415 17 21 2 153 924Потребности12131431979 79
Так как число отличных от нуля компонент точно не совпадает с (m + n -1), n-число складов, m- количество магазинов, то базис является вырожденным. Следовательно для устранения этого вводим нулевую загрузку в клетку с наибольшим тарифом.
F=5*12+3*12+30*0+2*1+22*14+29*16+2*15+3*9=927
Планы перевозок будут следующие:
1)С завода А1 будет отправлено 12 шт. товара потребителю B1 и 12 шт. товара потребителю B2
2)С завода А2 будет отправлена 1 шт. товара потребителю B2 и 14 шт. товара потребителю B3
)С завода А3 будет отправлено 15 шт. товара потребителю B4
)С завода А4 будет отправлено 15 шт. товара потребителю B4 и 9 шт. товара потребителю B5.
2. Метод Фогеля
Магазины Склады B1B2B3B4В5Запасыш1ш2ш3ш4ш5A15 123 24 510 725 24222714A230 2 1322 216 7 155551416A330 24 27 729 10 916143332А415 17 21 2 243 24113Потребности12131431979 79Штраф 1101184Штраф 210118Штраф 325126Штраф 4126Штраф 526
Для каждой строки и столбца находим штраф - это модуль разности двух наименьших стоимостей перевозок. Заполнение выполняется с наибольшего штрафа. Опорный план приведен в таблице.
Так как число отличных от нуля компонент точно совпадает с (m + n -1), n-число складов, m- количество магазинов, то базис является невырожденным.
Минимальная стоимость перевозок составляет:
fmin = 5*12+24*5+7*10+2*13+22*2+27*7+10*9+2*24= 647
Планы перевозок будут следующие:
1)С завода А1 будут отправлены 12 шт. товара потребителю B1, 5 шт. товара потребителю B3 и 7 шт. товара потребителю B4.
2)С завода А2 будут отправлены 13 шт. товара потребителю B2и 2 шт. товара потребителю B3.
)С завода А3 будет отправлено 7 шт. товара потребителю B3 B2и 9 шт. товара потребителю B5.
)С завода А4 будут отправлены 24 шт. товара потребителю B4.
3. Метод двойного предпочтения
В каждой строке отмечаем галочкой клетку с наименьшим тарифом, затем то же сделать для каждого столбца. Далее выбираем клетку, в которой находятся две галочки, если таких клеток оказалось несколько, то выбираем ту, у которой наименьший тариф. В эту клетку записывается максимально возможное значение. Максимально возможное значение будет равно минимальному из чисел ai и bj. Опорный план приведен в таблице.
Потребители Заводы B1B2B3B4В5ЗапасыA15 123 24 1210 25 24A230 2 1322 16 4 215A330 24 27 229 7 10 716А415 17 21 2 243 24Потребности12131431979 79
Так как число отличных от нуля компонент точно совпадает с (m + n -1), n-число складов, m- количество магазинов, то базис является невырожденным.
F=5*12+24*12+2*13+4*2+27*2+29*7+10*7+2*24=757
Планы перевозок будут следующие:
1)С завода А1 будет отправлено 12 шт. товара потребителю B1 и 12 шт. товара потребителю B3
2)С завода А2 будут отправлены 13 шт. товара потребителю B2 и 2 шт. товара потребителю B5
)С завода А3 будет отправлено 2 шт. товара потребителю B3, 7 шт. товара потребителю B4 и 7 шт. товара потребителю B5
)С завода А4 будет отправлено 24 шт. товара потребителю B4.
Найденный опорный план проверяем на оптимальность с помощью метода потенциалов.
. Метод потенциалов
В первой строке произвольно задаём потенциал, равный нулю. При определении остальных потенциалов необходимо следить, чтобы выполнялось условие .
Далее для клеток, не вошедших в базис, вычисляются косвенные стоимости , которые принято указывать в верхнем правом углу. Затем, для каждой свободной (пустой) клетки определяется разность , где k и l - индексы клеток, не вошедших в базис. Эти значения пишутся в нижнем правом углу клеток.
Потребители Заводы B1B2B3B4В5ЗапасыПот-лыA15 123 2 124 1210 26 1625 7 16240A230 5 252 13 22 24 -2 16 26 -107 2 150A330 8 22 24 5 19 27 229 720 7163А415 -19 3417 -22 3921 0 212 243 17 -2021-24Потребности12131431979 79Пот-лы52242627
Проанализируем полученную таблицу. Не все коэффициенты положительны, следовательно, организуем цикл пересчета. Для этого выберем самый максимальный по модулю отрицательный коэффициент и с этой клетки организуем цикл пересчета.
Потребители Заводы B1B2B3B4В5ЗапасыПот-лыA15 12 3 2 124 1210 26
-1625 7 16240A230 5 252 13 22 24 -2 16 26 -107 2 150A330 8 22 24 5 19 27 229
710
7163А415 -19 3417 -22 3921 0 212 243 -17 2024-24Потребности12131431979 79Пот-лы5224267
Выполнив цикл пересчета получим таблицу.
Потребители Заводы B1B2B3B4В5ЗапасыПот-лыA15 12 3 2 124 510 725 7 16240A230 5 252 13 22 24
16 10
67
2
150A330 8 22 24 5 19 27 929 13
1610
7163А415 -3 1817 -6 2321 16 52 243 -1 424-8Потребности12131431979 79Пот-лы5224107
Проанализируем полученную таблицу. Не все коэффициенты положительны, следовательно, организуем цикл пересчета. Для этого выберем самый максимальный по модулю отрицательный коэффициент и с этой клетки организуем цикл пересчета.
Выполнив цикл пересчета получим таблицу.
Потребители Заводы B1B2B3B4В5ЗапасыПот-лыA15 12 3 4
-124
510 725 7 16240A230 3 272 13
24
2
16 8
87 5
215-2A330 8 22 24 7 17 27 729 13 1610 9163А415 -3 1817 -6 2321 16 52 243 -1 424-8Потребности12131431979 79Пот-лы5424107
Проанализируем полученную таблицу. Не все коэффициенты положительны, следовательно, организуем цикл пересчета. Для этого выберем самый максимальный по модулю отрицательный коэффициент и с этой клетки организуем ци