Четыре предприятия данного экономического района для производства продукции использует три вида сырья. Потребности в

Четыре предприятия данного экономического района для производства продукции использует три вида сырья. Потребности в сырье каждого из предприятий соответственно равны b1, b2, b3 и b4 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны a1, a2 и a3 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей. Составить такой план перевозок, при котором общая себестоимость перевозок является минимальной. Задачу решить методом потенциалов.

Занесем исходные данные задачи в распределительную таблицу.
Bj
Ai B1 B2 B3 B4 запасы
A1 7 4 2 6 150
A2 1 3 5 4 130
A3 8 10 1 3 160
потребители 100 190 80 70
Проверим условие разрешимости задачи.
A=i=1mai=150+130+160=440;
B=j=1nbj=100+190+80+70=440.
Как видно, суммарная потребность груза в пунктах назначения равна запасам груза на базах. Следовательно, модель исходной транспортной задачи является закрытой.
Составим первый план транспортной задачи методом северо-западного ушла.
Заполнение клеток таблицы начнем с новой верхней клетки.
Bj
Ai B1 B2 B3 B4 запасы
A1 7
100 4
50 2 6 150
A2 1 3
130 5 4 130
A3 8 10
10 1
80 3
70 160
потребители 100 190 80 70
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 =6.
Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно:
S=7∙100+4∙50+3∙130+10∙10+1∙80+3∙70=1680
Оптимизируем план производства и организации перевозок методом потенциалов. Составим систему уравнений для определения потенциалов
α1+β1=7
α1+β2=4
α2+β2=3
α3+β2=10
α3+β3=1
α3+β4=3
Проверим оптимальность опорного плана. Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=-1; α3=6
β1=7; β2=4; β3=-5; β4=-3
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆13=2-0+5=7
∆14=6-0+3=9
∆21=1+1-7=-7
∆23=5+1+5=11
∆24=4+1+3=8
∆31=8-6-7=-5
Опорный план не является оптимальным, так как существуют отрицательные оценки свободных клеток.
Выбираем максимальную оценку свободной клетки 2;1: ∆21=-7.
Для этого в клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Bj
Ai B1 B2 B3 B4 запасы
A1 - 7
100 + 4
50 2 6 150
A2 + 1 - 3
130 5 4 130
A3 8 10
10 1
80 3
70 160
потребители 100 190 80 70
Цикл приведен в таблице 2,1→2,2→1,2→1,1.
Из грузов, стоящих в минусовых клетках, выбираем наименьшее.
Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем из стоящих в минусовых клетках. В результате перемещения числа k=100 по циклу получим новую распределительную таблицу, в которой клетка 2;1 стала занятой.
Bj
Ai B1 B2 B3 B4 запасы
A1 7 4
150 2 6 150
A2 1
100 3
30 5 4 130
A3 8 10
10 1
80 3
70 160
потребители 100 190 80 70
Оптимизируем план производства и организации перевозок методом потенциалов

. Составим систему уравнений для определения потенциалов
α1+β2=4
α2+β1=1
α2+β2=3
α3+β2=10
α3+β3=1
α3+β4=3
Проверим оптимальность опорного плана. Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=-1; α3=6
β1=2; β2=4; β3=-5; β4=-3
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆11=7-0-2=5;
∆13=2-0+5=7;
∆14=6-0+3=9;
∆23=5+1+5=11;
∆24=4+1+3=8;
∆31=8-6-2=0.
Опорный план является оптимальным, так как все оценки свободных клеток положительны.
Минимальные затраты составят:
Smin=4∙150+1∙100+3∙30+10∙10+1∙80+3∙70=1180
Анализ оптимального плана.
Из 1-го склада необходимо весь груз направить в 2-й магазин.
Из 2-го склада необходимо груз направить в 1-й магазин (100 ед.), в 2-й магазин (30 ед.)
Из 3-го склада необходимо груз направить в 2-й магазин (10 ед.), в 3-й магазин (80 ед.), в 4-й магазин (70 ед.).
Составим первый план транспортной задачи методом наименьшей стоимости.
Заполнение клеток таблицы начнем с новой верхней клетки.
Bj
Ai B1 B2 B3 B4 запасы
A1 7 4
150 2 6 150
A2 1
100 3
30 5 4 130
A3 8 10
10 1
80 3
70 160
потребители 100 190 80 70
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 =6.
Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно:
S=4∙150+1∙100+3∙30+10∙10+1∙80+3∙70=1180
Оптимизируем план производства и организации перевозок методом потенциалов. Составим систему уравнений для определения потенциалов
α1+β2=4
α2+β1=1
α2+β2=3
α3+β2=10
α3+β3=1
α3+β4=3
Проверим оптимальность опорного плана. Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=-1; α3=6
β1=2; β2=4; β3=-5; β4=-3
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆11=7-0-2=5;
∆13=2-0+5=7;
∆14=6-0+3=9;
∆23=5+1+5=11;
∆24=4+1+3=8;
∆31=8-6-2=0.
Опорный план является оптимальным, так как все оценки свободных клеток положительны.
Минимальные затраты составят:
Smin=4∙150+1∙100+3∙30+10∙10+1∙80+3∙70=1180
Анализ оптимального плана.
Из 1-го склада необходимо весь груз направить в 2-й магазин.
Из 2-го склада необходимо груз направить в 1-й магазин (100 ед.), в 2-й магазин (30 ед.)
Из 3-го склада необходимо груз направить в 2-й магазин (10 ед.), в 3-й магазин (80 ед.), в 4-й магазин (70 ед.).
Составим первый план транспортной задачи методом двойного предпочтения.
Используя метод двойного предпочтения, построим первый опорный план транспортной задачи