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

Запишем исходные данные в виде матрицы планирования.
Потребители
Поставщики B1 B2 B3 B4 Мощность поставщиков
A1 7 8 1 2 160
A2 4 5 9 8 140
A3 9 2 3 6 170
Потребности 120 50 190 120
Обозначим через xij – количество груза, перевозимого от i-ого поставщика j-ому потребителю.
Целевая функция – это совокупные транспортные издержки.
fx=i=13j=14Cij*Xij=7x11+8x12+x13+2x14+4x21+5x22+9x23+8x24+9x31+2x32+3x33+6x34 min
j=14Xij=ai для i=1,2,3 j=13Xij=bj для j=1,2,3,4 Xij≥0 .
Данная задача является открытой.
ai=160+140+170=470;
bj= 120+50+190+120=480 .
ai≠ bj
Для того, чтобы сделать задачу закрытой, необходимо добавить дополнительного (фиктивного) поставщика с запасами равными 10-ти.
Решаем задачу методом потенциалов. Первоначальный план находим по методу северо-западного угла.
Поставщики Потребители Потенциал Ui
120 50 190 120
160 7
120 8
- 40 1 2
+ 0
140 4 5
+ 10 9
- 130 8 3
170 9 2 3
+ 60 6
- 110 9
10 0 0 0 0
10 15
Потенциал Vj
7 8 12 15
Последовательность заполнения клеток следующая:
x11 = min(160,120) = 120;
x12 = min(40,50) = 40;
x22 = min(140,10) = 10;
x23 = min(130,190) = 130;
x33 = min(170,60) = 60;
x34 = min(110,120) = 110;
x44 = min(10,10) = 10.
Число занятых клеток равно: m n 1 3 4 1 6. Опорный план является вырожденным.
В данном случае необходимо добавить клетку с нулевым значением. Пусть x25 = 0.
Таким образом, число занятых клеток становится равно 7.
Затраты на перевозку составят:
F(x) = 7*120 + 8*40 + 5*10 + 9*130 + 3*60 + 6*110 + 0*10 = 3220 ден. ед.
Находим для каждой строки и каждого столбца потенциалы по формуле: Vj Ui Cij для заполненных клеток.
Полагая u 1 0, получим:
u1 = 0; v1 = 7;u2 = 3; v2 = 8;
u3 = 9; v3 = 12;u4 = 15; v4 = 15;
* u1 = 0, тогда v1 = 0+7=7 . Находим v2 = 0+8=8. Т. к. известно значение v2, то найдем u2 = 8-5=3 и т.д.Расчеты осуществляем в таблице.
Для проверки плана на оптимальность составляем матрицу оценок:
dij Ui Cij Vj
Получим матрицу:
d=00-11-13000 -41183703 00
Наличие отрицательной оценки свидетельствует о том, что план неоптимален.
Построим контур перераспределения для клетки (1, 4). Он показан пунктиром. Вершинам контура присвоены соответствующие знаки «+» и «-».
Наименьшая поставка в клетке со знаком «-» равна 40. Значит проведем перераспределение поставок, увеличив поставки в клетках со знаком «+» на 40 и уменьшив поставки в клетках со знаком «-» также на 40.
Новый план представлен в таблице.
Поставщики Потребители Потенциал Ui
120 50 190 120
160 7
- 120 8
1 2
+ 40 0
140 4
+ 5
50 9
- 90 8 -10
170 9 2 3
+ 100 6
- 70 -4
10 0 0 0 0
10 2
Потенциал Vj
7 -5 -1 2
Снова находим для каждой строки и каждого столбца потенциалы по формуле: Vj Ui Cij для заполненных клеток и отображаем их в новой таблице.
Полагая u 1 0, получим:
u1 = 0; v1 = 7;u2 = -10; v2 = -5;
u3 = -4; v3 = -1;u4 = 2; v4 = 2;
Расчеты осуществляем в таблице.
Для проверки плана на оптимальность составляем матрицу оценок:
dij Ui Cij Vj
Получим матрицу:
d=0132 0-1300-4-2-5-7703 00
Наличие отрицательной оценки свидетельствует о том, что план неоптимальный.
Построим контур перераспределения для клетки (2, 1). Он показан пунктиром. Вершинам контура присвоены соответствующие знаки «+» и «-».
Наименьшая поставка в клетке со знаком «-» равна 70