Определение рационального варианта размещения производственно-хозяйственных предприятий (на примере АБЗ) и выбор оптимального маршрута поездки коммивояжера

| Категория реферата: Рефераты по математике
| Теги реферата: шпоры по психологии, контрольная работа 10 класс
| Добавил(а) на сайт: Zabirov.

В верхний правый угол клеток вносится суммарная величина приведенных затрат на приготовление и транспортировку 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 ( |450,3 |421,3 ( |-16( 0 | | |
| | |465,3 | |495,3 | | | |
|X1=90 |50 | |40 | | |-16 |1 |
| |449,3 ( |440,3 |466,3 ( |437,3 ( |0 | | |
| |471,3 | |503,3 |458,3 | | | |
|X2=90 | |60 | | |30 |0 |6/9 |
| |449,3 ( |440,3 ( |466,3 ( |437,3 ( |0 | | |
| |485,3 |530,3 |468,3 |497,3 | | | |
|X3=45 | | | | |45 |0 |0 |
| |449,3 ( |440,3 ( | 466,3 |437,3 |0 | | |
| |500,3 |455,3 | | | | | |
|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 | |450,3 |421,3 ( |-18( 0 | | |
| | |439,3 ( | |495,3 | | | |
| | |465,3 | | | | | |
|X1=90 |50 | |40 | | |-16 | |
| |452,3 ( | 458,3 | 469,3( |440,3 ( |1 ( 0 | | |
| |489,3 | |521,3 |476,3 | | | |
|X2=45 | | 45 _| | | + |3 | |
| |451,3 ( | 457,3 (| 468,3 |439,3 ( |0 | | |
| |485,3 |530,3 | |497,3 | | | |
|X3=45 | | | 0 | | _ |2 | |
| | | |+ | |45 | | |
| |449,3 ( | 455,3 | 466,3 |437,3 | -2 ( 0 | | |
| |500,3 | | | | | | |
|X4=90 | | 15 | 5 |70 | |0 | |
| | |+ |_ | | | | |
|Vj |449,3 |455,3 |466,3 |437,3 |-2 | | |

Для одной свободной клетки не выполняется условие

Ui + Vj ( Сpi + E*Kpi + Cij поэтому план необходимо улучшить.
Строим цикл для этой клетки. Вершине свободной клетки присваиваем знак “-”, для остальных вершин этот знак чередуется. Перевозка хп = 5. Перемещаем эту перевозку по циклу, прибавляя ее в клетках со знаком “+” и отнимая в клетках со знаком “-”. После строим новую транспортную таблицу с учетом изменений.

|Мощность|Спрос зон-потребителей, тыс.т/год |
|АБЗ | |
|тыс.т/го|B1=50 |B2=60 |B3=45 |B4=70 |Bф=45 |Ui |Ki |
|д | | | | | | | |
| |433,3 | |450,3 |422,3 ( |-18 ( 0| | |
| | |440,3 ( | |495,3 | | | |
| | |465,3 | | | | | |
|X1=90 |50 | |40 | | |-18 |1 |
| | 451,3 (| 458,3 | 468,3 |440,3 ( | 0 | | |
| |489,3 | |( 521,3 |476,3 | | | |
|X2=45 | |40 | | |5 |0 |8/9 |
| | 451,3 | 458,3 (| 468,3 | 440,3 (|0 | | |
| |( 485,3 |530,3 | |497,3 | | | |
|X3=45 | | |5 | |40 |0 |1/9 |
| | 448,3 (| 455,3 |465,3 ( |437,3 |-3 ( 0 | | |
| |500,3 | |466,3 | | | | |
|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 | |450,3 |421,3 ( |-78 ( 0 | | |
| | |439,3 ( | |495,3 | | | |
| | |465,3 | | | | | |
|X1=90 |50 | |40 | | |-16 |1 |
| | 452,3 (| 458,3 | 469,3 (|440,3 ( |-59 ( 0 | | |
| |489,3 | |521,3 |476,3 | | | |
|X2=45 | |45 | | | |3 |1 |
| | 511,3 | 517,3 (| 528,3 | 499,3 |0 | | |
| |( 545,3 |590,3 | |( 557,3 | | | |
|X3=18 | | |0 | |18 |62 |0 |
| | 449,3 (| 455,3 | 466,3 |437,3 | -62 ( 0| | |
| |500,3 | | | | | | |
|X4=90 | |15 |5 |70 | |0 |1 |
|Vj |449,3 |455,3 |466,3 |437,3 |-62 | | |

План является оптимальным, подсчитываем значения коэффициентов интенсивности. Так как все коэффициенты равны либо 1, либо 0, то данный план является наилучшим.

Рассчитать значение целевой функции для каждого из промежуточных вариантов и построить таблицу.

|Вариант |Мощность АБЗ, расположенного в пункте, |Значение целевой|
|размещения|тыс.т/год |функции, zi, |
| | |тыс.руб. |
| |М1 |М2 |М3 |М4 | |
|1 |50 |60 |45 |70 |98912,5 |
|2 |90 |60 |0 |75 |99037,5 |
|3 |90 |40 |5 |90 |100067,5 |
|4 |90 |45 |0 |90 |100072,5 |
|-наилучший| | | | | |