Транспортная задача. Матричные игры: Методические указания к практическим занятиям, страница 10

Имеется   работ и    станков, каждый станок может выполнить любую из работ. Известно, что  затраты на выполнение   работы    станком  составляют     денежных единиц,    Требуется распределить работы по станкам (по одной работе на каждый станок) так, чтобы  минимизировать суммарные затраты.

Положим

Математическую модель задачи о назначениях можно записать в  виде

                                         (12)

                            (13)

                                      (14)

Ограничения (13)-(14) отражают требования, что каждая работа выполняется только одним станком и каждый станок выполняет только одну работу.

Заметим, что с учётом (13) ограничения (14) можно  заменить на  целые числа, т.е. задача (12)-(14) отличается от  задачи (2)-(4) только дополнительным требованием  целочисленности всех переменных   С другой стороны, применение  метода потенциалов  к ТЗ с целыми значениями всех     и     всегда даёт целочисленный оптимальный план, см. упражнение   6 . В (13) все правые части целые (равны  единице), и поэтому задачу о назначениях можно просто решать методом потенциалов, не обращая внимания на условие целочисленности 

Пример 7. Решить задачу о назначениях с  исходными данными 

Решение. На рис 9а) представлена начальная опорная таблица, полученная методом МС. Признак оптимальности не выполнен,   После перестройки по циклу      получается  таблица  9б), удовлетворяющая признаку  оптимальности (проверьте!). В соответствующем оптимальном плане    для шести остальных переменных, т е. минимум  затрат    достигается при выполнении 1-ой работы на 1-ом станке, 2-ой – на 3-ем, 3-ей – на 2-ом.

Рис.9

Задача о назначениях вырождена – любая  её опорная таблица содержит     заполненных нулями занятых клеток. Это приводит к тому, что в методе потенциалов возможно многократное повторение  одного и того же  плана, представленного  различными опорными таблицами. Описание способов «ускорения» поиска оптимального плана задачи о назначениях выходит за рамки данных указаний.

Упражнения

1. Построить начальные опорные таблицы методом СЗУ и методом МС,  сравнить соответствующие им значения целевой функции     и    для транспортных задач, условия которых представлены в следующих таблицах:

2. В ТЗ выполнено условие баланса (1) и равенство