1.2.2 Построение опорного плана методом минимальной стоимости
Итак, произведем расчеты согласно исходным данным приведенным выше методом минимальной стоимости.
Согласно условию задачи составим таблицу (тарифы cij располагаются в нижнем правом углу ячейки).
Поставщик |
Потребитель |
Запас |
||||||
B 1 |
B 2 |
B 3 |
||||||
A 1 |
- |
- |
- |
120 |
||||
|
1 |
|
2 |
|
9 |
|||
A 2 |
- |
- |
- |
110 |
||||
|
3 |
|
4 |
|
1 |
|||
A 3 |
- |
- |
- |
20 |
||||
|
6 |
|
4 |
|
8 |
|||
A 4 |
- |
- |
- |
70 |
||||
|
2 |
|
3 |
|
3 |
|||
A 5 |
- |
- |
- |
180 |
||||
|
0 |
|
0 |
|
0 |
|||
Потребность |
225 |
135 |
140 |
|
Минимальный элемент матрицы тарифов находится в ячейке A1B1 и равен 1, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B1 наиболее рентабельный.
Запасы поставщика A1 составляют 120 единиц продукции. Потребность потребителя B1 составляет 225 единиц продукции.
От поставщика A1 к потребителю B1 будем доставлять min = (120 , 225) = 120 единиц продукции.
Разместим в ячейку A1B1 значение равное 120
Мы полностью израсходовали запасы поставщика A1. Вычеркиваем строку 1 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
Минимальный элемент матрицы тарифов находится в ячейке A2B3 и равен 1, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A2 к потребителю B3 наиболее рентабельный.
Запасы поставщика A2 составляют 110 единиц продукции. Потребность потребителя B3 составляет 140 единиц продукции. От поставщика A2 к потребителю B3 будем доставлять min = (110 , 140) = 110 единиц продукции.
Разместим в ячейку A2B3 значение равное 110
Мы полностью израсходовали запасы поставщика A2. Вычеркиваем строку 2 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
Минимальный элемент матрицы тарифов находится в ячейке A4B1 и равен 2, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A4 к потребителю B1 наиболее рентабельный.
Запасы поставщика A4 составляют 70 единиц продукции. Потребность потребителя B1 составляет 105 единиц продукции.
От поставщика A4 к потребителю B1 будем доставлять min = (70 , 105) = 70 единиц продукции.
Разместим в ячейку A4B1 значение равное 70
Мы полностью израсходовали запасы поставщика A4. Вычеркиваем строку 4 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
Минимальный элемент матрицы тарифов находится в ячейке A3B2 и равен 4, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A3 к потребителю B2 наиболее рентабельный.
Запасы поставщика A3 составляют 20 единиц продукции. Потребность потребителя B2 составляет 135 единиц продукции.
От поставщика A3 к потребителю B2 будем доставлять min = (20 , 135) = 20 единиц продукции.
Разместим в ячейку A3B2 значение равное 20
Мы полностью израсходoвали запасы поставщика A3. Вычеркиваем строку 3 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
Минимальный элемент матрицы тарифов находится в ячейке A5B1 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A5 к потребителю B1 наиболее рентабельный.
Запасы поставщика A5 составляют 180 единиц продукции. Потребность потребителя B1 составляет 35 единиц продукции.
От поставщика A5 к потребителю B1 будем доставлять min = (180 , 35) = 35 единиц продукции.
Разместим в ячейку A5B1 значение равное 35
Мы полностью удовлетворили потребность потребителя B1. Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.
Минимальный элемент матрицы тарифов находится в ячейке A5B2 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A5 к потребителю B2 наиболее рентабельный.
Запасы поставщика A5 составляют 145 единиц продукции. Потребность потребителя B2 составляет 115 единиц продукции. От поставщика A5 к потребителю B2 будем доставлять min = ( 145 , 115 ) = 115 единиц продукции.
Разместим в ячейку A5B2 значение равное 115
Мы полностью удовлетворили потребность потребителя B2. Вычеркиваем столбец 2 таблицы, т.е исключаем его из дальнейшего рассмотрения.
Минимальный элемент матрицы тарифов находится в ячейке A5B3 и равен 0, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A5 к потребителю B3 наиболее рентабельный.
Запасы поставщика A5 составляют 30 единиц продукции. Потребность потребителя B3 составляет 30 единиц продукции.
От поставщика A5 к потребителю B3 будем доставлять 30 единиц продукции.
Разместим в ячейку A5B3 значение равное 30
Мы полностью израсходoвали запасы поставщика A5. Вычеркиваем строку 5 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
Заполненные нами ячейки будем называть базисными, остальные - свободными.
Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.
Количество базисных ячеек (задействованных маршрутов) равно 7, что и требовалось.
Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.
S0 = 1 * 120 + 1 * 110 + 4 * 20 + 2 * 70 + 0 * 35 + 0 * 115 + 0 * 30 = 450 ден. ед.
Общие затраты на доставку всей продукции, для начального решения , составляют 450 ден. ед.
- Введение
- 1. Транспортная модель закрытого типа
- 1.1 Условие задачи
- 1.2 Построение опорных планов транспортной модели
- 1.2.1 Построение опорного плана методом северо-западного угла
- 1.2.2 Построение опорного плана методом минимальной стоимости
- 1.2.3 Построение опорного плана методом Фогеля
- 1.3 Оптимизация транспортной модели закрытого типа
- 1.3.1 Метод потенциалов на основе опорного плана, построенного методом северо-западного угла
- 1.3.2 Метод потенциала на основе опорного плана, построенного методом минимальной стоимости
- 1.3.3 Метод потенциалов на основе опорного плана, построенного методом Фогеля
- 2. Транспортная модель открытого типа
- 2.3.1 Метод потенциала на основе опорного плана, построенного методом Фогеля
- Заключение