1.2.2 Построение опорного плана методом минимальной стоимости

Итак, произведем расчеты согласно исходным данным приведенным выше методом минимальной стоимости.

Согласно условию задачи составим таблицу (тарифы cij располагаются в нижнем правом углу ячейки).

Минимальный элемент матрицы тарифов находится в ячейке 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 ден. ед.