Предприятие розничной торговли имеет четыре крупных универмага

Прежде чем составлять исходную таблицу для расчетов необходимо проверить выполнение первого условии необходимого для решения задачи. В рассматриваемом примере:
аА = 40 bP = 27
аВ = 40 bQ = 25
аС = 60 bR = 30
bS = 35
∑a = 140  ∑b = 117 
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 23 (140—117). Тарифы перевозки единицы груза к этому магазину полагаем равны нулю. \
Поочередно рассчитаем два варианта размещения третьего склада, после сравним полученные результаты.
Вариант 1.
Шаг 1. Построение первоначального плана.
Наиболее экономичным из существующих методов построения первоначального плана, является метод «наименьшей стоимости». Его суть заключается в том, что сначала в каждой строке выбираются квадраты с минимальной стоимостью перевозки и в этих квадратах в левом верхнем углу ставится отметка. Затем тоже действие производится со столбцами (в каждом столбце выбирается квадрат с наименьшей стоимостью перевозки и ставится отметка). Таким образом, в таблице появляются квадраты, отмеченные дважды и один раз (таблица 1.2).
Таблица 1.2 − Первоначальный план перевозок
Торговый склад Потенциал Универмаг Всего предложение
Р Q R S О
V1
U1
А
* 70
10 * 85 ** 55
30 120 0 40
В
110
15 90
25 * 75 110 0 40
С
115
2 115 * 70 * 90
35 0
23 60
Всего спрос 27 25 30( 35 23 140
Первая строка – наименьшая стоимость 55 р. ст./ед;
Вторая строка – наименьшая стоимость 75 р. ст./ед;
Третья строка – наименьшая стоимость 70 р. ст./ед;
Первый столбец – наименьшая стоимость 70 р. ст./ед;
Второй столбец – наименьшая стоимость 85 р. ст./ед;
Третий столбец – наименьшая стоимость 55 р. ст./ед;
Четвертый столбец – наименьшая стоимость 90 р. ст./ед.
Первоначально максимальное количество перевозок распределяется в клетки с двойным предпочтением, начиная с наименьших значений, затем - с одинарным, а далее от меньшей стоимости к большей.
В данном примере 1 квадрата выделен дважды – квадрат АR, стоимостью транспортных издержек 55 р. ст./ед.
Первоначальный план перевозок представлен в таблице 2. Он содержит 7 перевозок (занятых квадрата), что удовлетворяет требованию второго необходимого условия m + n - 1 = (7 = 3 + 4 - 1).
Шаг 2. Построение системы потенциалов.
Начинается с того, что строке 1 присваивается потенциал 0, т.е. принимается условную стоимость издержек у склада А равной 0. От него, в соответствии с первоначальным планом, продукция отправляется P и R универсаму. Следовательно, по формуле (1.3):
VР = 0 + 70 = 70, a VR = 0 + 55 = 55.
Зная условную стоимость издержек у Р универсама, находится стоимость издержек у склада В и С, по формуле:
UВ = 70 - 110 = - 40, UС = 70 - 115 = - 45.
Аналогично, зная условную стоимость издержек у склада В и С находим условную стоимость издержек в остальных универсамах.
Вычисленные потенциалы строк: UА = 0, UВ = - 40, UС = - 45, и потенциалы столбцов: VР = 70, VQ = 85, VR = 1, V4 = 2 помещаются в добавленные строку (для Vj) и столбец (для Ui) (таблица 1.3).
Таблица 1.3 − Первоначальный план перевозок и система потенциалов
Торговый склад Потенциал Универмаг Всего предложение
Р Q R S О
V1
U1 70 50 55 45 - 45
А 0 * 70
10 * 85 ** 55
30 120 0 40
В - 40 110
15 90
25 * 75 110 0 40
С - 45 115
2 115 * 70 * 90
35 0
23 60
Всего спрос 27 25 30 35 23 140
Шаг 3. Проверка первоначального плана на оптимальность.
Проверка плана на оптимальность исходит из того, что при любом его изменении, т.е. при перестановке перевозок в свободные квадраты, условная стоимость издержек в пунктах потребления не должна стать меньше, чем в принятом нами плане . Следовательно, для свободных квадратов должно выполнятся условие:
Ui + Cij ≥ Vj
Осуществляется проверка:
Для квадрата АQ: Ui + Cij = 0 + 85 = 85 > 50,
АS: Ui + Cij = 0 + 120 = 120 > 45,
АO: Ui + Cij = 0 + 0 = 0 > - 45,
ВR: Ui + Cij = -40 + 75 = 35 < 55,
ВS: Ui + Cij = -40 + 110 = 70 > 45,
ВO: Ui + Cij = -40 + 0 = -40 > -45,
СQ: Ui + Cij = -45 + 115 = 70 > 50,
СR: Ui + Cij = -45 + 70 = 25 < 55.
Проверка показала, что условие оптимальности не выполняется лишь для квадратов BR и CR, нарушение оптимальности 20 и 30 соответственно. Выбираем максимальную разность, соответствующую свободной клетке CR.
Шаг 4. Оптимизация плана.
Для оптимизации плана необходимо переместить перевозку в квадрат СR. Перемещение производится таким образом, чтобы по отношению к выбранному квадрату образовать связку. Для этого необходимо провести замкнутую ломаную линию, состоящую из горизонтальных и вертикальных линий (по принципу хода ладьи в шахматах), в которой одной из вершин полученного многоугольника является свободный квадрат, не отвечающий условию оптимальности, а остальные вершины должны находиться в занятых квадратах (таблица 1.4).
Таблица 1.4 – Оптимизация первоначального плана распределения
Торговый склад Потенциал Универмаг Всего предложение
Р Q R S О
V1
U1 70 50 55 45 - 45
А 0 + 70
198754768351701802921010 85 - 55
2457457683530 120 0 40
В - 40 110
15 90
25 75 110 0 40
С - 45 - 115
103505679452 115 + 70 90
35 0
23 60
Всего спрос 27 25 30 35 23 140
После образования связки свободному квадрату и связанным с ним занятым квадратам присваиваются поочередно знаки «плюс» и «минус», начиная со свободного квадрата.
Из грузов, стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min СР = 2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из грузов, стоящих в минусовых клетках. В результате получим новый опорный план (таблица 1.5).
Таблица 1.5 – Оптимизированный план перевозок
Торговый склад Потенциал Универмаг Всего предложение
Р Q R S О
V1
U1 70 50 55 75 - 15
А 0 70
12 85 55
28 120 0 40
В - 40 110
15 90
25 75 110 0 40
С - 15 115
115 70
2 90
35 0
23 60
Всего спрос 27 25 30 35 23 140
Шаг 5. Проверка нового плана на оптимальность.
Для нового плана вычисляются новые значения потенциалов, и новый вариант проверяется на оптимальность, т.е. повторяются шаги 2 и 3.
Проверка на оптимальность:
Для квадрата АQ: Ui + Cij = 0 + 85 = 85 > 50,
АS: Ui + Cij = 0 + 120 = 120 > 75,
АO: Ui + Cij = 0 + 0 = 0 > - 15,
ВR: Ui + Cij = -40 + 75 = 35 < 55,
ВS: Ui + Cij = -40 + 110 = 70 < 75,
ВO: Ui + Cij = -40 + 0 = -40 < -15,
СP: Ui + Cij = -15 + 115 = 100 > 70,
СQ: Ui + Cij = -15 + 115 = 100 > 50/
Проверка показала, что условие оптимальности не выполняется лишь для квадратов BR, BS и BO, нарушение оптимальности 20, 5 и 25 соответственно. Выбираем максимальную разность, соответствующую свободной клетке BO.
Шаг 6. Оптимизация плана.
Для оптимизации плана необходимо переместить перевозку в квадрат BO (таблица 1.6).
Таблица 1.6 – Оптимизация первоначального плана распределения
Торговый склад Потенциал Универмаг Всего предложение
Р Q R S О
V1
U1 70 50 55 75 - 15
А 0 332105172720 + 70
3606792603510 85 - 55
3219452603530 120 0 40
В - 40 - 110
2844805016515 90
25 75 110 303530225425+ 0 40
С - 15 - 115
115 + 70
350519457202 90
35 0
23 60
Всего спрос 27 25 30 35 23 140
Из грузов, стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min BР = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из грузов, стоящих в минусовых клетках