Полная версия

Главная arrow Математика, химия, физика arrow Математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

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

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

Классическая транспортная задача линейного программирования формулируется следующим образом.

Имеется т пунктов отправления: Ар А2, ..., Ат, в которых сосредоточены запасы однородного товара (груза) в количестве соответственно а{, а2,..., ат единиц. Кроме того, имеется п пунктов назначения: Bv В2, ..., Вп, подавших заявки соответственно на bv b2,..., Ьп единиц товара.

Предполагается, что сумма всех заявок равна сумме всех запасов:

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

Требуется составить такой план перевозок, при котором все заявки были бы выполнены и общая стоимость всех перевозок была минимальна.

При такой постановке задачи показателем эффективности плана перевозок является стоимость, поэтому поставленную задачу точнее называют транспортной задачей по критерию стоимости.

Приведем математическую формулировку этой задачи. Обозначим х — количество груза, доставляемого из /-го пункта отправления А. в j-й пункт назначения В. (/ = 1, m;j = 1, п). Неотрицательные переменные хп, х12,..., хтп (число которых, очевидно, равно тп) должны удовлетворять следующим условиям:

1. Суммарное количество груза, направляемое из каждого пункта отправления во все пункты назначения, должно быть равно запасу груза в данном пункте. Это даст нам т условий-равенств:

или в краткой форме записи

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

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

или

т п

Знак двойной суммы ЕЕ означает, что суммирование осуще-

i=i i=

ствляется по всем комбинациям индексов (/ = 1, ..., mj- 1, ..., п), т.е. по всем комбинациям пунктов отправления с пунктами назначения.

Функция (3.52) линейна, ограничения-равенства (3.50), (3.51) также линейны. Перед нами — типичная задача линейного программирования с ограничениями-равенствами (ОЗЛП).

Как и всякую другую задачу линейного программирования, ее можно было бы решить симплекс-методом, но некоторые особенности данной задачи позволяют решить ее более просто. Причиной является то, что все коэффициенты при переменных в уравнениях (3.50), (3.51) равны единице. Кроме того, имеет значение структура связей между условиями. Нетрудно убедиться, что не все т + п уравнений нашей задачи независимыми. Действительно, складывая между собой все уравнения (3.50) и все уравнения (3.51), мы должны получить одно и то же в силу условия (3.49). Таким образом, условия (3.50), (3.51) связаны одной линейной зависимостью и фактически из этих уравнений только т + п - 1, а нет + п являются линейно независимыми. Значит, ранг системы уравнений (3.50), (3.51)

г = т + п - 1,

а следовательно, можно разрешить эти уравнения относительно т + п - 1 базисных переменных, выразив их через остальные, свободные.

Подсчитаем количество свободных переменных:

Как известно, в задаче линейного программирования оптимальное решение достигается в одной из вершин ОДР, где по крайней мере к переменных обращаются в нуль. Значит, в нашем случае для оптимального плана перевозок по крайней мере (т - 1 ){п- 1) значений х.. должны быть равны нулю.

Условимся о терминологии. Значения х.. количества единиц груза, направляемых из пункта А. в пункт В., будем называть перевозками.

Любую совокупность значений (х.) (i = 1, ..., т; j = 1, ..., п) будем называть планом перевозок или просто планом.

План (х.) будем называть допустимым, если он удовлетворяет условиям (3.50), (3.51), так называемым балансовым условиям: все заявки удовлетворены, все запасы исчерпаны.

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

План (х.) будем называть оптимальным, если он среди всех допустимых планов приводит к наименьшей стоимости всех перевозок.

Перейдем к изложению методов решения транспортной задачи (ТЗ). Эти методы не требуют манипуляций с симплекс-таблицами, а сводятся к более простым операциям непосредственно с таблицей, где в определенном порядке записаны все условия ТЗ. Такая таблица называется транспортной (табл. 3.28). В транспортной таблице записываются:

  • • пункты отправления (ПО) и назначения (ПН);
  • • запасы, имеющиеся в пунктах отправления а.;
  • • заявки, поданные пунктами назначения b
  • • стоимости перевозки из каждого пункта отправления в каждый пункт назначения с...

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

Таблица 3.28

В правом верхнем углу каждой клетки проставлена стоимость перевозки единицы товара (груза) из ПО А. в ПН В. В правом столбце помещены запасы товара в каждом ПО, в нижней строке — заявки, поданные каждым ПН. Для ТЗ сумма запасов равна сумме заявок; общее значение этой суммы записывается в правой нижней клетке таблицы.

Ранее мы показали, что ранг системы уравнений-ограничений ТЗ равен г = т + п - 1, где т — число строк, а п — число столбцов транспортной таблицы. Значит, в каждом опорном плане, включая оптимальный, будут отличны от нуля не более чем т + п - 1 перевозок.

Клетки таблицы, в которых мы будем записывать эти отличные от нуля перевозки, условимся называть базисными, а остальные (пустые) — свободными.

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

  • • сумма перевозок в каждой строке таблицы должна быть равна запасу данного ПО;
  • • сумма перевозок в каждом столбце должна быть равна заявке данного ПН;
  • • общая стоимость перевозок — минимальная.

В дальнейшем все действия по нахождению решения ТЗ будут сводиться к преобразованию транспортной таблицы 3.28

При описании этих преобразований удобно пользоваться нумерацией клеток таблицы (подобной нумерации клеток шахматной доски). Клеткой (А., В) или, короче, клеткой (i,j) мы будем называть клетку, стоящую в /-й строке и j-м столбце транспортной таблицы. Например, самая верхняя левая клетка будет обозначаться (1, 1), стоящая под ней — (2, 1) и т. д.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>