Общий вид транспортной задачи в виде таблицы
Обычно исходные данные записываются в виде таблицы:
| Пункты отправления | Пункты назначения | Запасы | ||||
| В1 | … | Bj | … | Bn | ||
| A1 | C11 x11 | … | C1j x1j | … | C1n x1n | a1 |
| … | … | … | … | … | … | … |
| Ai | Ci1 xi1 | … | Cij xij | … | Cin xin | a i |
| … | … | … | ... | … | … | … |
| Am | Cm1 xm1 | … | Cmj xmj | … | Cmn Xmn | a m |
| Потребности | b1 | … | bj | … | bn | |
Закрытая задача
Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.
то модель такой транспортной задачи называется закрытой.
В ряде случаев не требуется, чтобы весь произведенный продукт в каждом пункте производства был реализован. В таких случаях баланс производства и потребления может быть нарушен.
Открытая задача
Если для ТЗ выполняется одно из условий:
или 
то модель задачи называют открытой.
Для разрешимости ТЗ с открытой моделью необходимо преобразовать ее в закрытую. Так, при выполнении первого условия необходимо ввести фиктивный (n +1)-й пункт назначения Bn +1, т.е. в матрице задачи предусматривается дополнительный столбец. Спрос фиктивного потребителя полагают равным небалансу, т. е.
а все соответствующие тарифы – одинаковыми, чаще всего равными нулю.
Аналогично при выполнении второго условия вводится фиктивный поставщик.
При преобразовании открытой транспортной задачи в закрытую целевая функция не меняется, так как все слагаемые, соответствующие дополнительным перевозкам, равны нулю.
|
|
|
Для решения транспортной задачи разработаны специальные методы, позволяющие из бесчисленного множества решений найти оптимальное. Вот некоторые из методов:
Метод северо-западного угла
В данном методе запасы очередного по номеру поставщика используются для обеспечения запросов очередных по номеру потребителей до тех пор, пока не будут исчерпаны полностью, после чего используются запасы следующего по номеру поставщика.
Заполнение таблицы транспортной задачи начинается с левого верхнего угла, поэтому и называется метод северо-западного угла.
Метод минимальной стоимости
Метод минимальной стоимости прост и позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи C=(cij).
Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости
Метод потенциалов
Общая схема метода следующая: сначала составляют допустимый исходный план задачи, который затем исследуется на оптимальность. Если при проверке окажется, что составленный план оптимален, то решение закончено. В противном случае при помощи специального приёма осуществляется переход к новому, лучшему плану. Этот план снова исследуется на оптимальность и в случае неоптимальности опять улучшается.
|
|
|
Дата добавления: 2019-01-14; просмотров: 317; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!