Основные понятия и технология построения математических моделей

Запишем экономико-математическую модель для нашей задачи. Переменные: x11 – количество груза из 1-го склада в 1-й магазин. x12 – количество груза из 1-го склада в 2-й магазин. x13 – количество груза из 1-го склада в 3-й магазин. x14 – количество груза из 1-го склада в 4-й магазин. x15 – количество груза из 1-го склада в 5-й магазин. x21 – количество груза из 2-го склада в 1-й магазин. x22 – количество груза из 2-го склада в 2-й магазин. x23 – количество груза из 2-го склада в 3-й магазин. x24 – количество груза из 2-го склада в 4-й магазин. x25 – количество груза из 2-го склада в 5-й магазин. x31 – количество груза из 3-го склада в 1-й магазин. x32 – количество груза из 3-го склада в 2-й магазин. x33 – количество груза из 3-го склада в 3-й магазин. x34 – количество груза из 3-го склада в 4-й магазин. x35 – количество груза из 3-го склада в 5-й магазин. x41 – количество груза из 4-го склада в 1-й магазин. x42 – количество груза из 4-го склада в 2-й магазин. x43 – количество груза из 4-го склада в 3-й магазин. x44 – количество груза из 4-го склада в 4-й магазин. x45 – количество груза из 4-го склада в 5-й магазин. Ограничения по запасам: x11 + x12 + x13 + x14 + x15 ≤ 200 (для 1 базы) x21 + x22 + x23 + x24 + x25 ≤ 300 (для 2 базы) x31 + x32 + x33 + x34 + x35 ≤ 250 (для 3 базы) x41 + x42 + x43 + x44 + x45 ≤ 180 (для 4 базы) Ограничения по потребностям: x11 + x21 + x31 + x41 = 150 (для 1-го магазина) x12 + x22 + x32 + x42 = 100 (для 2-го магазина) x13 + x23 + x33 + x43 = 200 (для 3-го магазина) x14 + x24 + x34 + x44 = 220 (для 4-го магазина) x15 + x25 + x35 + x45 = 210 (для 5-го магазина) Целевая функция: 5x11 + 7x12 + 8x13 + 7x14 + 6x15 + 4x21 + 6x22 + 5x23 + 8x24 + 5x25 + 6x31 + 4x32 + 5x33 + 8x34 + 7x35 + 7x41 + 6x42 + 6x43 + 4x44 + 5x45 → min 
Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 200 + 300 + 250 + 180 = 930 ∑b = 150 + 100 + 200 + 220 + 210 = 880 Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 50 (930—880). Тарифы перевозки единицы груза к этому магазину полагаем равны нулю. Занесем исходные данные в распределительную таблицу. 
B1 B2 B3 B4 B5 B6 Запасы
A1 5 7 8 7 6 0 200
A2 4 6 5 8 5 0 300
A3 6 4 5 8 7 0 250
A4 7 6 6 4 5 0 180
Потребности 150 100 200 220 210 50
Поиск первого опорного плана( метод наименьшей стоимости, )
B1 B2 B3 B4 B5 B6 Запасы
A1 5 7 8 7 6[200] 0 200
A2 4[150] 6 5[150] 8 5 0 300
A3 6 4[100] 5[50] 8[40] 7[10] 0[50] 250
A4 7 6 6 4[180] 5 0 180
Потребности 150 100 200 220 210 50
Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 9 . Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 6*200 + 4*150 + 5*150 + 4*100 + 5*50 + 8*40 + 7*10 + 0*50 + 4*180 = 4310 Улучшение опорного плана( метод потенциалов)Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v5 = 6; 0 + v5 = 6; v5 = 6 u3 + v5 = 7; 6 + u3 = 7; u3 = 1 u3 + v2 = 4; 1 + v2 = 4; v2 = 3 u3 + v3 = 5; 1 + v3 = 5; v3 = 4 u2 + v3 = 5; 4 + u2 = 5; u2 = 1 u2 + v1 = 4; 1 + v1 = 4; v1 = 3 u3 + v4 = 8; 1 + v4 = 8; v4 = 7 u4 + v4 = 4; 7 + u4 = 4; u4 = -3 u3 + v6 = 0; 1 + v6 = 0; v6 = -1 
v1=3 v2=3 v3=4 v4=7 v5=6 v6=-1
u1=0 5 7 8 7 6[200] 0
u2=1 4[150] 6 5[150] 8 5 0
u3=1 6 4[100] 5[50] 8[40] 7[10] 0[50]
u4=-3 7 6 6 4[180] 5 0
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (2;5): 1 + 6 > 5; ∆25 = 1 + 6 - 5 = 2 > 0 Выбираем максимальную оценку свободной клетки (2;5): 5 Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 
1 2 3 4 5 6 Запасы
1 5 7 8 7 6[200] 0 200
2 4[150] 6 5[150][-] 8 5[+] 0 300
3 6 4[100] 5[50][+] 8[40] 7[10][-] 0[50] 250
4 7 6 6 4[180] 5 0 180
Потребности 150 100 200 220 210 50
Цикл приведен в таблице (2,5 → 2,3 → 3,3 → 3,5). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. 
B1 B2 B3 B4 B5 B6 Запасы
A1 5 7 8 7 6[200] 0 200
A2 4[150] 6 5[140] 8 5[10] 0 300
A3 6 4[100] 5[60] 8[40] 7 0[50] 250
A4 7 6 6 4[180] 5 0 180
Потребности 150 100 200 220 210 50
Проверим оптимальность опорного плана