2015-02-04
1132
Экономико-математическая модель транспортной задачи
Существуют поставщики и потребители некоторого однородного груза.
У каждого поставщика имеется определенное количество единиц этого груза (мощность поставщика).
Каждому потребителю нужно некоторое количество единиц этого груза (спрос потребителя).
Известны затраты на перевозку единицы груза от каждого из поставщиков к каждому из потребителей.
Цель транспортной задачи – составить такой план перевозок от поставщиков к потребителям, при котором:
1. суммарные затраты на перевозку груза будут минимальны;
2. по возможности будут задействованы все мощности поставщиков;
3. по возможности будет удовлетворен весь спрос потребителей.
Закрытая модель транспортной задачи – модель, в которой суммарная мощность поставщиков равна суммарному спросу потребителей. В противном случае, модель открытая.
Открытая модель всегда сводится к закрытой.
Порядок решения для закрытой модели:
1. составляется специальная таблица;
2. находится первоначальный план поставок (методы северо-западного угла и минимальной стоимости);
3. первоначальный план поставок оптимизируется распределительным методом.
Метод северо-западного угла
Северо-западный угол таблицы – это ее левый, верхний угол, т.е. клетка в первой строке и первом столбце.
Метод минимальной стоимости
На каждом шаге поставка делается в клетку с наименьшей стоимостью перевозки единицы груза среди всех незаполненных клеток.
Распределительный метод решения транспортной задачи
Для того, чтобы оптимизировать первоначальный план поставок, необходимо составить матрицу оценок.
Оценка клетки (i, j) = оценка i -й строки + оценка j -го столбца + число в левом верхнем углу клетки (i, j).
Оценки строки и столбца выбираются таким образом, чтобы оценки всех отмеченных клеток были равны нулю.
Оценки всех клеток записываются в виде матрицы оценок. Если она не содержит отрицательных чисел, то получен оптимальный план поставок. Иначе проводится оптимизация плана поставок.
Двигаясь из клетки с отрицательной оценкой по отмеченным клеткам (запрещается делать два последовательных шага в одной строке или в одном столбце), строят так называемый цикл пересчета. Внутри этого цикла перераспределяют поставки. Для полученной таблицы находят матрицу оценок и т.д.
