84411 (675866), страница 2
Текст из файла (страница 2)
m
-
xij = bj j=1, ......, n
i=1
спрос j-го потребителя должен быть полностью удовлетворен
-
xij 0 i=1, ...., m; j=1, ...., n
xij – объем перевозок от i-го поставщика j-му потребителю
Транспортная таблица:
| Мощность АБЗ | Спрос зон-потребителей, тыс.т/год | ||||||
| тыс.т/год | B1=50 | B2=60 | B3=45 | B4=70 | Bф=135 | Ui | Ki |
| 433,3 | 440,3 465,3 | 449,3 450,3 | 437,3 495,3 | 0 | |||
| X1=90 | 50 | 40 | 0 | 5/9 | |||
| 433,3 471,3 | 440,3 | 449,3 503,3 | 437,3 458,3 | 0 | |||
| X2=90 | 60 | 30 | 0 | 6/9 | |||
| 433,3 466,3 | 440,3 511,3 | 449,3 | 437,3 478,3 | 0 | |||
| X3=90 | 45 | 45 | 0 | ½ | |||
| 433,3 500,3 | 440,3 455,3 | 449,3 466,3 | 437,3 | 0 | |||
| X4=90 | 70 | 20 | 0 | 7/9 | |||
| Vj | 433,3 | 440,3 | 449,3 | 437,3 | 0 | ||
Так как задача не сбалансирована, то определяем спрос фиктивного потребителя:
Вф= аi - bj = 360 – 225 = 135 тыс.т/год
В верхний правый угол клеток вносится суммарная величина приведенных затрат на приготовление и транспортировку 1т аб, Сpi + E*Kpi + Cij
С помощью правила минимального элемента вносим в таблицу перевозки xij.
Проверяем план на вырожденность:
m + n - 1 = 8 = 8 (занятых клеток), следовательно план является невырожденным.
Строим систему потенциалов поставщиков и потребителей. Для этого потенциал столбца или строки с наибольшим кол-вом занятых клеток приравниваем нулю, в данном случае это потенциал столбца Bф, остальные потенциалы определяем исходя из условия оптимальности для занятых клеток (Ui + Vj = Сpi + E*Kpi + Cij).
Проверяем план на оптимальность:
-
число занятых клеток не должно превышать величину m + n – 1
-
для каждой занятой клетки сумма потенциалов должна равняться суммарной величине затрат на приготовление и транспортировку 1т аб.
-
для каждой свободной клетки должно выполняться неравенство :
Ui + Vj Сpi + E*Kpi + Cij
Все три условия выполняются, следовательно план является оптимальным с точки зрения транспортной задачи.
Определяем значения коэффициентов интенсивности.
Ki = xij / xi
xij – cуммарный объем поставок i-го АБЗ реальным потребителям
xi – мощность i-го АБЗ
Так как ни один Ki не равен нулю или единице, то рассматриваемый вариант размещения АБЗ соответствующей мощности не есть наилучший, поэтому необходимо его улучшить.
Отыскиваем смешанную строку с минимальной величиной Ki и в этой строке мощность АБЗ уменьшаем до следующей возможной величины, в нашем случае это третья строка.
Строим новую транспортную таблицу не забывая, что суммарная мощность АБЗ должна равняться суммарному спросу потребителей. Также необходимо пересчитать величину Сpi + E*Kpi + Cij для клеток третьей строки.
| Мощность АБЗ | Спрос зон-потребителей, тыс.т/год | ||||||
| тыс.т/год | B1=50 | B2=60 | B3=45 | B4=70 | Bф=90 | Ui | Ki |
| 433,3 | 424,3 465,3 | 450,3 | 421,3 495,3 | -16 0 | |||
| X1=90 | 50 | 40 | -16 | 1 | |||
| 449,3 471,3 | 440,3 | 466,3 503,3 | 437,3 458,3 | 0 | |||
| X2=90 | 60 | 30 | 0 | 6/9 | |||
| 449,3 485,3 | 440,3 530,3 | 466,3 468,3 | 437,3 497,3 | 0 | |||
| X3=45 | 45 | 0 | 0 | ||||
| 449,3 500,3 | 440,3 455,3 | 466,3 | 437,3 | 0 | |||
| X4=90 | 5 | 70 | 15 | 0 | 15/18 | ||
| Vj | 449,3 | 440,3 | 466,3 | 437,3 | 0 | ||
Новый вариант также не является наилучшим, поэтому уменьшаем мощность АБЗ во втором пункте.
| Мощность АБЗ | Спрос зон-потребителей, тыс.т/год | ||||||
| тыс.т/год | B1=50 | B2=60 | B3=45 | B4=70 | Bф=45 | Ui | Ki |
| 433,3 | 439,3 465,3 | 450,3 | 421,3 495,3 | -18 0 | |||
| X1=90 | 50 | 40 | -16 | ||||
| 452,3 489,3 | 458,3 | 469,3 521,3 | 440,3 476,3 | 1 0 | |||
|
| 45 _ | + | 3 | ||||
| 451,3 485,3 | 457,3 530,3 | 468,3 | 439,3 497,3 | 0 | |||
|
| 0 + | _ 45 | 2 | ||||
| 449,3 500,3 | 455,3 | 466,3 | 437,3 | -2 0 | |||
|
| 15 + | 5 _ | 70 | 0 | |||
| Vj | 449,3 | 455,3 | 466,3 | 437,3 | -2 | ||
X2=45
X4=90Для одной свободной клетки не выполняется условие Ui + Vj Сpi + E*Kpi + Cij поэтому план необходимо улучшить.
Строим цикл для этой клетки. Вершине свободной клетки присваиваем знак “-”, для остальных вершин этот знак чередуется. Перевозка хп = 5. Перемещаем эту перевозку по циклу, прибавляя ее в клетках со знаком “+” и отнимая в клетках со знаком “-”. После строим новую транспортную таблицу с учетом изменений.
| Мощность АБЗ | Спрос зон-потребителей, тыс.т/год | ||||||
| тыс.т/год | B1=50 | B2=60 | B3=45 | B4=70 | Bф=45 | Ui | Ki |
| 433,3 | 440,3 465,3 | 450,3 | 422,3 495,3 | -18 0 | |||
| X1=90 | 50 | 40 | -18 | 1 | |||
| 451,3 489,3 | 458,3 | 468,3 521,3 | 440,3 476,3 | 0 | |||
| X2=45 | 40 | 5 | 0 | 8/9 | |||
| 451,3 485,3 | 458,3 530,3 | 468,3 | 440,3 497,3 | 0 | |||
| X3=45 | 5 | 40 | 0 | 1/9 | |||
| 448,3 500,3 | 455,3 | 465,3 466,3 | 437,3 | -3 0 | |||
| X4=90 | 20 | 70 | -3 | 1 | |||
| Vj | 451,3 | 458,3 | 468,3 | 440,3 | 0 | ||
План является оптимальным, теперь подсчитываем коэффициенты интенсивности. Так как не все коэффициенты равны нулю или единице, то уменьшаем мощность завода в 3-м пункте.
| Мощность АБЗ | Спрос зон-потребителей, тыс.т/год | ||||||
| тыс.т/год | B1=50 | B2=60 | B3=45 | B4=70 | Bф=18 | Ui | Ki |
| 433,3 | 439,3 465,3 | 450,3 | 421,3 495,3 | -78 0 | |||
| X1=90 | 50 | 40 | -16 | 1 | |||
| 452,3 489,3 | 458,3 | 469,3 521,3 | 440,3 476,3 | -59 0 | |||
| X2=45 | 45 | 3 | 1 | ||||
| 511,3 545,3 | 517,3 590,3 | 528,3 | 499,3 557,3 | 0 | |||
| X3=18 | 0 | 18 | 62 | 0 | |||
| 449,3 500,3 | 455,3 | 466,3 | 437,3 | -62 0 | |||
| X4=90 | 15 | 5 | 70 | 0 | 1 | ||
| Vj | 449,3 | 455,3 | 466,3 | 437,3 | -62 | ||
План является оптимальным, подсчитываем значения коэффициентов интенсивности. Так как все коэффициенты равны либо 1, либо 0, то данный план является наилучшим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
