Частным случаем задачи линейного программирования является транспортная задача. ТЗ в общем виде состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А1 , А2 , ..., Аm в n пунктов назначения B1 , B2 , ..., Bn. В качестве критерия оптимальности можно взять минимальную стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим задачу с первым критерием, обозначив через сn тарифы перевозок единицы груза из i-го пункта отправления в j-й пункт назначения, через ai - запасы груза в пункте Аi через bj - потребности в грузе пункта Bj , xij - количество единиц груза, перевозимого из i-го пункта в j-й пункт. Составим математическую модель задачи. Так как от i-гo поставщика к j-му потребителю запланировано к перевозке xij единиц груза. Таблица 2.2 Поставщики | Потребители | Запасы | B1 | B2 | ... | Bn | А1 | C11 X11 | C12 X12 | ... | C1n X1n | a1 | А2 | C21 X21 | C22 X22 | ... | C2n X2n | a2 | ... | ... | ... | ... | ... | ... | Аm | Cm1 Xm1 | Cm2 Xm2 | ... | Cmn Xmn | am | Потребности | b1 | b2 | ... | bn | ∑ai=∑bj |
Соответственно математическая постановка задачи состоит в определении минимума целевой функции при условиях: | (i = l, ..., m), | (2.18) | | (j = 1, ..., n), | (2.19) | xij ≥ 0 | (i = l, ..., m; j = l, ..., n). | (2.20) |
Всякое неотрицательное решение систем уравнений (2.18)-(2.20), определяемое матрицей X=(xij ), называют опорным планом ТЗ, а план X*=(xij ), при котором функция Z принимает минимальное значение - называется оптимальным планом ТЗ. Все данные, а затем и опорный план, удобно занести в распределительную таблицу (см, в примерах параграфа). Если общее количество груза в пунктах отправления и общая потребность в нем в пунктах назначения совпадают, т.е. то модель ТЗ называется закрытой. Теорема 4. Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение. Для доказательства теоремы необходимо показать, что хотя бы один план задачи и линейная функция на множестве планов при заданных условиях существу ограничена. Доказательство: Тогда величины xij = aibj /M (i = 1, 2, ..., m; j = 1, 2, ..., n) являются планом, так как они удовлетворяют, системе ограничений (2.18), (2.19). Действительно, подставляя значения xij в (2.18) и (2.19), имеем Выберем из значений Cij наибольшее С'= mах Cij и заменим в линейной функции (2.17) все коэффициенты на С' тогда, учитывая (2.18), получаем Выберем из значений Cij наименьшее С''=min Cij и заменим в линейной функции все коэффициенты на С'' тогда, имеем Объединяя два последних неравенства в одно двойное, окончательно получаем C"M ≤ Z ≤ C'M, т. е. линейная функция ограничена на множестве планов транспортной задачи. Ч.Т.Д. Если общее количество груза в пунктах отправления и общая потребность в нем в пунктах назначения не совпадают ТЗ называется открытой. Введением фиктивного потребителя (если ), или фиктивного отправителя (если , любая задача приводится к закрытой модели (во всех фиктивных ячейках таблицы полагают cij= 0). Для разрешимости задачи равенство (2.21) является необходимым и достаточным условием. Нахождение опорных и оптимального планов ТЗ можно вести симплексным методом, но, ввиду специфики ТЗ, и большого ее прикладного значения, разработаны специальные методы. Нахождение опорных планов ТЗ можно осуществить одним из пяти методов: северо-западного угла, минимальной стоимости, аппроксимации Фогеля, двойного предпочтения и дельта-метода.
|