Математическая постановка транспортной задачи линейного программирования

| Категория реферата: Рефераты по экономико-математическому моделированию
| Теги реферата: культурология, сочинение 7
| Добавил(а) на сайт: Данил.

2. Модели транспортной задачи

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

Для доказательства теоремы необходимо показать, что при заданных условиях существует хотя бы один план задачи и линейная функция на множестве планов ограничена.
Доказательство. Пусть [pic]= M > 0[pic].

Тогда величины xij = aibj /M (i = 1,2,3, ... m; j = 1,2,3, ..., n) являются планом, так как они удовлетворяют системе ограничений
( 2 ) и ( 3 ) .
Действительно, подставляя значения в (2) и (3) , находим

[pic]= ai ,

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

[pic],
Выберем из значений Cij наименьшее C((=min Cij и заменим в линейной функции все коэффициенты на C(( ; тогда, учитывая ( 2 ) имеем
[pic]
Объединяя два последних неравенства в одно двойное , окончательно получаем
C((M ( Z ( C( M, т. е. линейная функция ограничена на множестве планов транспортной задачи.

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

Транспортная задача, в которой суммарные запасы и потребности не совпадают, т. е. не выполняется условие [pic], называется открытой. Для открытой модели может быть два случая: a) суммарные запасы превышают суммарные потребности [pic]; b) суммарные потребности превышают суммарные запасы [pic].
Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.
Найти минимальное значение линейной функции
[pic] при ограничениях
[pic], i = 1, 2, ..., m, (случай а)
[pic], j = 1, 2, ..., n;
[pic], i = 1, 2, ..., m, (случай б)
[pic], j = 1, 2, ..., n, xij ( 0 (i = 1, 2, ..., m; j = 1, 2, ..., n).
Открытая модель решается приведением к закрытой модели.
В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Bn+1, потребности которого bn+1 = [pic]. В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Am+1, запасы которого am+1 = [pic].
Стоимость перевозки единицы груза как фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.
После преобразований задача принимает вид закрытой модели и решается обычном способом. При равных стоимостях перевозки единицы груза от поставщиков к фиктивному потребителю затраты на перевозку груза реальным потребителям минимальны, а фиктивному потребителю будет направлен груз от наименее выгодных поставщиков. То же самое получаем и в отношении фиктивного поставщика.

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

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

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

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

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

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

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

Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.

Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждое неизвестное входит лишь в два уравнения системы (2) и (3) и коэффициенты при неизвестных равны единице] для определения оптимального плана транспортной задачи разработаны специальные методы. Два из них - метод потенциалов и Венгерский метод - рассматриваются ниже.

4. Методы определения первоначального опорного плана

4.1. Метод минимального элемента

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

Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:
|2 |3 |4 |15|
|11|6 |10|1 |
|8 |9 |3 |3 |
|4 |1 |2 |21|
|10|20|10| |

Решение:
Задача сбалансирована.
Строим первоначальный опорный план методом минимального элемента.

1. Выясним минимальную стоимость перевозок. [pic]Первая перевозка будет осуществляться с пункта производства [pic]в пункт потребления [pic]и она составит максимально возможное число единиц продукта [pic]:. В этом случае, потребности пункта потребления [pic]будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки [pic].Выясним минимальную стоимость перевозок (без учета столбца № 2).

2. [pic]Вторая и третья перевозки будут осуществляться с пункта производства [pic]и [pic]в пункт потребления [pic]и