webdonsk.ruКак сделать план невырожденным
Добавил пользователь Валентин П. Обновлено: 30.08.2024
Пример. На три базы поступили ящики с заготовками деталей, которые необходимо доставить на четыре завода. Исходные данные представлены в нижеследующей транспортной таблице.
Таблица 10.3
Определите оптимальный план доставки заготовок на заводы с учетом минимизации совокупных транспортных затрат.
Решение
Обозначим искомые объемы поставок от i-ой базы-поставщика к j-му заводу-потребителю через .
Математическая модель данной задачи будет иметь вид:
I итерация:
1 этап: проверка сбалансированности запасов и потребностей.
Представленная транспортная задача является открытой, т.к. суммарная мощность баз-поставщиков меньше суммарной потребности заводов-потребителей на 200 ящиков:
,
,
.
Сведем данную транспортную задачу к закрытой: введем фиктивную базу А4 с недостающей мощностью а4 = 200 ящиков:
.
Зададим значения условных транспортных затрат на единицу груза от данной базы к заводам-потребителям равными нулю, результаты занесем в следующую таблицу.
Таблица 10.4
С учетом фиктивного поставщика математическая модель будет иметь вид:
2 этап: разработка исходного опорного плана.
Таблица 10.5
Таблица 10.6
Таблица 10.7
Таблица 10.8
Продолжая данные рассуждения, в результате получим следующее распределение поставок:
Таблица 10.9
Совокупные транспортные издержки для данного плана поставок составят (усл. ден. ед.):
.
3 этап: проверка вырожденности опорного плана.
Количество задействованных клеток в таблице поставок (таблица 10.9): N=6. Ранг r системы ограничений транспортной задачи равен:
.
Так как, , следовательно, опорный план транспортной задачи вырожденный. Определим количество фиктивных поставок:
Таблица 10.10
4 этап: расчет потенциалов.
Аналогично последовательно находим потенциалы строк и колонок по остальным загруженным клеткам, результаты расчетов представлены в таблице 10.11.
Таблица 10.11
5 этап: проверка плана на оптимальность.
По таблице 10.11 для незагруженных клеток проверим условие оптимальности ():
Таблица 10.12
7 этап: построение контура перераспределения поставок.
Построим контур перераспределения поставок (таблица 10.13).
Таблица 10.13
В таблице 10.13 начиная с ВМН разделим вершины на загружаемые
и разгружаемые.
8 этап: определение минимального элемента в контуре перераспределения и перераспределение поставок по контуру.
9 этап: получения нового опорного плана.
В результате перераспределения поставок по контуру получим новый опорный план (таблица 10.14).
Таблица 10.14
Совокупные транспортные издержки для данного плана поставок составят (усл. ден. ед.):
II итерация:
1 этап: проверка вырожденности опорного плана.
Опорный план условно невырожденный.
2 этап: расчет потенциалов.
Результаты расчета потенциалов приведены в таблице 10.15.
Таблица 10.15
Таблица 10.16
5 этап: построение контура перераспределения поставок.
Построим контур перераспределения поставок (таблица 10.17).
Таблица 10.17
В таблице 10.17 начиная с ВМН разделим вершины на загружаемые
и разгружаемые.
6 этап: определение минимального элемента в контуре перераспределения и перераспределение поставок по контуру.
7 этап: получения нового опорного плана.
В результате перераспределения поставок по контуру получим новый опорный план (таблица 10.18).
Таблица 10.18
Совокупные транспортные издержки для данного плана поставок составят (усл. ден. ед.):
.
III итерация:
1 этап: проверка вырожденности опорного плана.
Опорный план невырожденный.
2 этап: расчет потенциалов.
Результаты расчета потенциалов приведены в таблице 10.19.
Таблица 10.19
Таблица 10.20
5 этап: построение контура перераспределения поставок.
Построим контур перераспределения поставок (таблица 10.21).
Таблица 10.21
В таблице 10.21 начиная с ВМН разделим вершины на загружаемые
6 этап: определение минимального элемента в контуре перераспределения и перераспределение поставок по контуру.
7 этап: получения нового опорного плана.
В результате перераспределения поставок по контуру получим новый опорный план (таблица 10.22).
Таблица 10.22
Совокупные транспортные издержки для данного плана поставок составят (усл. ден. ед.):
VI итерация:
1 этап: проверка вырожденности опорного плана.
Опорный план невырожденный.
2 этап: расчет потенциалов.
Результаты расчета потенциалов приведены в таблице 10.23.
Таблица 10.23
Найденный опорный план оптимальный, так как для всех незагруженных клеток выполняется условие оптимальности. Оптимальное решение является единственным, так как все неравенства строгие.
Ответ: оптимальное распределение поставок:
.
Данное распределение поставок обеспечит оптимальные транспортные издержки в размере 2300 усл. ден. ед.
СКАЧАТЬ методические указания к решению транспортной задачи: Транспортная задача с ограничениями на пропускную способность
Читайте также: