Реферат: Транспортная задача 5

= b_j .

Выберем из значений C_ij наибольшее C¢ = max C_ij и заменим в линейной функции ( 1 ) все коэффициенты на C¢ тогда, учитывая ( 2 ) , получим

,

Выберем из значений C_ij наименьшее C ¢¢ = min C_ij и заменим в линейной функции все коэффициенты на C ¢¢ ; тогда, учитывая ( 2 ) имеем

Объединяя два последних неравенства в одно двойное , окончательно получаем

C ¢¢ M ? Z ? C ¢ M ,

т. е. линейная функция ограничена на множестве планов транспортной задачи.

2.2. Открытая модель транспортной задачи

Транспортная задача, в которой суммарные запасы и потребности не совпадают, т. е. не выполняется условие , называется открытой. Для открытой модели может быть два случая:

a) суммарные запасы превышают суммарные потребности ;

b) суммарные потребности превышают суммарные запасы .

Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.

Найти минимальное значение линейной функции

при ограничениях

,i = 1, 2, ..., m, (случай а)

, j = 1, 2, ..., n;

, i = 1, 2, ..., m, (случай б)

, j = 1, 2, ..., n,

x_ij ³ 0 (i = 1, 2, ..., m; j = 1, 2, ..., n).

Открытая модель решается приведением к закрытой модели.

В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель B_{n +1} , потребности которого b_{n +1} = . В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик A_{m +1} , запасы которого a_{m +1} = .

Стоимость перевозки единицы груза как фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.

После преобразований задача принимает вид закрытой модели и решается обычном способом. При равных стоимостях перевозки единицы груза от поставщиков к фиктивному потребителю затраты на перевозку груза реальным потребителям минимальны, а фиктивному потребителю будет направлен груз от наименее выгодных поставщиков. То же самое получаем и в отношении фиктивного поставщика.

Прежде чем решать какую-нибудь транспортную задачу, необходимо сначала проверить, к какой модели она принадлежит, и только после этого составить таблицу для ее решения.

3. Определение оптимального и опорного плана транспортной задачи

Как и при решении задачи линейного программирования, симплексным методом, определение оптимального плана транспортной задачи начинают с нахождения какого-нибудь ее опорного плана.

Число переменных X_ij в транспортной задаче с mпунктами отправления и nпунктами назначения равно nm, а число уравнений в системах (2) и (3) равноn+m. Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно n+m-1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонентов равно в точности n+m-1, то план является не выраженным, а если меньше - то выраженным.

Для определения опорного плана существует несколько методов. Три из них - метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля - рассмотрены ниже.

При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы не учитывается, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Обычно рассмотренный метод используется при вычислениях с помощью ЭВМ.