4.1. транспортная задача линейного программирования
4.1. транспортная задача линейного программирования
Постановка задачи. Некоторый однородный продукт, сосредоточенный у m поставщиков Лі в количестве аі(і=1..ш) единиц соответственно, необходимо доставить n потребителям Bj в количестве bj(j=1..n) единиц. Известна стоимость счперевозки единицы груза от і-го поставщика к j-му потребителю.
Необходимо составить план перевозок, позволяющий вывести все грузы, полностью удовлетворить потребности и имеющий минимальную стоимость.
Обозначим через хчколичество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю. Так как от і-го поставщика к j-му потребителю запланировано к перевозке xij единиц груза, то стоимость перевозки составит сц-хч-.
Стоимость всего плана выразится двойной суммой
m n
Z=II сч*ч
i=1 j=1
Систему ограничений получаем из следующих условий задачи: а) все грузы должны быть перевезены, т.е.
IХч = ai ' i = 1.m
j=1
б) все потребности должны быть удовлетворены, т.е.
m
IХч = bj ' j = 1.n
i=1
Таким образом, математическая модель транспортной задачи имеет следующий вид: найти минимальное значение линейной функции
mn
Z II cx. (4.1)
i=1 j=1
при ограничениях
Ilxij = ai , i = 1..m (4.2)
m
Ix4= bj , j = 1..n (4.3)
> 0, i = 1,...,m; j = 1,...,n; (4.4)
В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т.е.
m n
I ai =I bj. (4.5)
Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е выполняется условие (4.5), называется закрытой моделью; в противном случае открытой. Для открытой модели может быть два случая:
а) Суммарные запасы превышают суммарные потребности
m n
Z ai >Z bj
б) Суммарные потребности превышают суммарные запасы
mn
Z ai <Z bj
i=1 j=1
Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.
Найти минимальное значение линейной функции
mn
Z=ZZ c«x4
i=1 j=1
При ограничениях
n
Z x4< ai ' i = 1-m
^ (случай "а")
Z x4= bj , J = 1..n , x4> 0
i=1 n
ZxiJ = ai , i=1.. m
Jm=1 (случай "б")
Z x4< bj , J = 1..n , x4> 0
i=1
Открытая модель решается приведением к закрытой модели.
В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Вп+1 , потребность которого
mn
bn+1 = Z ai-Z bj
i=1 J=1
В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Ат+1 , запасы которого
nm am+1 =Z bJ"Z ai
Как стоимость перевозки единицы груза до фиктивного потребителя, так и стоимость перевозки груза от фиктивного поставщика полагаются равными нулю, так как груз в обоих случаях не перевозится.
Транспортная задача имеет n+m уравнений с mn неизвестными.
Матрицу Х=(хц)т!ІЬ удовлетворяющую условиям (4.2)-(4.4), называют планом перевозок транспортной задачи (хцперевозками).
Определение. План Х*, при котором целевая функция (4.1) обращается в минимум, называется оптимальным.
Теорема 4.1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось условие баланса
m n
Z аі = Z bj
1=1 j=i
План транспортной задачи называется опорным, если положительным перевозкам соответствует система линейно независимых векторов (1=1..m, j=1..n), где векторы при
переменных хц (1=1..m, j=1..n) в матрице системы ограничений (4.2)-(4.3).
Теорема 4.2. Существует план, содержащий не более m+n-1 положительных перевозок, при этом система векторов ,
соответствующая таким перевозкам (хц > 0), линейно-независима.
Таким образом, опорный план транспортной задачи содержит m+n-1 положительных перевозок. Дадим другое определение опорного плана.
Определение. План транспортной задачи называется опорным, если из его основных коммуникаций невозможно составить замкнутый маршрут.
Методы составления первоначальных опорных планов
Метод северо-западного угла используют для нахождения произвольного опорного плана транспортной задачи.
Схема метода: 1) Полагают верхний левый элемент матрицы Х
хп=гпт(аьЬ1). Возможны три случая:
а) если а1 < b1 , то х11=а1 и всю первую строку, начиная со второго
элемента, заполняют нулями.
б) если а1 > b1 , то х11 = b1 , а все оставшиеся элементы первого
столбца заполняют нулями.
в) если а1 = b1 , то х11 = а1 = b1 , и все оставшиеся элементы первых
столбца и строки заполняют нулями.
На этом один шаг метода заканчивается.
2) Пусть проделано k шагов, (к*)-й шаг состоит в следующем.
Определяют верхний левый элемент незаполненной части матрицы Х. Пусть это элемент хЛ*(Л + * = k + Л).
Тогда полагают хЛ* = mina^b*/1), где
,(k)
*-1
j=1
и
,(k)
Л-1
1=1
і*
Если a*} < Ь*}, то заполняют нулями к ю строку, начиная с g _го
элемента. В противном случае заполняют нулями оставшуюся часть м -го столбца.
Метод минимального элемента позволяет построить начальный опорный план транспортной задачи и является вариантом метода северозападного угла, учитывающим специфику матрицы С=(сіі)тп. В отличие от метода северо-западного угла данный метод позволяет сразу получить достаточно экономичный план и сокращает общее количество итераций по его оптимизации.
Схема метода: элементы матрицы С нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х .
Пусть элементом с минимальным порядковым номером оказался
0
элемент хц.
Тогда полагают хц0=тт^ , bj)
Возможны три случая:
а) если min(ai , bj) = ai , то оставшуюся часть і-й строки заполняют
нулями;
б) если min(ai , bj) = bj , то оставшуюся часть j-го столбца
заполняют нулями.
в) если аН^ , то оставшуюся часть строки и столбца заполняют
нулями.
Далее этот процесс повторяют с незаполненной частью матрицы. Пусть элементом с k-м порядковым номером оказался х(Л).
Тогда х(Л) = тіп(аЛк) , b)k)), где
af = ал-Z xkg) g = 1..k-1
j=1
bV = Ьм-У>(М u = 1..k-1
MM 1—t lM
i=1
Возможны три случая:
x (k) = a(k)
а) a к < Ь<Мм> , тогда км к и оставшуюся часть строки к заполняют
нулями;
б) akk) > bM>, тогда xfM = bV и остаток столбца м заполняют нулями;
в) akk) = bMk), тогда оставшуюся часть строки к и столбца м
заполняют нулями.
Метод потенциалов
Для транспортной задачи (ТЗ), как и для любой ЗЛП, существует двойственная к ней задача. Исходная задача
m n
minSS CijXij (4.6) 1=1 j=1
S Xij = ai 1 = 1,m
j=1
m
SXij = bj j = 1,n
i=1
(4.7)
(4.8)
> 0, i = 1,m, j = 1,n (4.9)
Обозначим двойственные переменные для каждого ограничения вида (4.7) через U1 (i=1,...,m) и вида (4.8)Vj (j=1,...,n), тогда двойственная задача имеет вид
m
n
max
S aiUi +S bjVj
.i=1 j=1
(4.10)
Ui+Vj < Cij , i = 1,m, j
1,n
(4.11)
Переменные задачи двойственной к транспортной Ui и Vj называют потенциалами.
Теорема 4.3. Для оптимальности плана X=(Xij)mn ТЗ необходимо и достаточно существования чисел (потенциалов) V1, V2, ... , Vn и U1, U2, Um таких, что Ui+Vj < Cj для i=1,...,m , j=1,...,n ,
Ui +Vj = Cj , если Xij>0.
Из теоремы следует: для того чтобы опорный план был оптимальным, необходимо выполнение следующих условий:
а) для каждой занятой клетки (отличного от нуля элемента матрицы
Х) сумма потенциалов должна быть равна стоимости перевозки единицы
груза
Ui+Vj = Cj; (4.12)
б) для каждой незанятой клетки (Xij=0) сумма потенциалов должна
быть меньше или равна стоимости перевозки единицы груза
Ui+Vj< Cij (4.13)
Таким образом, для проверки плана на оптимальность необходимо сначала построить систему потенциалов. Для построения системы потенциалов используем условие
Ui+Vj = Cj , Xij>0.
Систему потенциалов можно построить только для невырожденного опорного плана. Такой план содержит m+n-1 занятых клеток, поэтому для него можно составить систему из m+n-1 линейно-независимых уравнений вида (4.12) с неизвестными Ui и Vj . Уравнений на одно меньше, чем переменных, поэтому система является неопределенной и одному неизвестному (обычно U1) придают нулевое значение. После этого остальные потенциалы определяются однозначно.
Проверка выполнения оптимальности для незанятых клеток.
Просматриваем строки и для каждой незанятой клетки проверяем выполнения условия (4.13), т.е. суммируем потенциалы тех строк и столбцов, на пересечении которых стоит незанятая клетка. Если для всех незанятых клеток Ui+Vj < Су, то по теореме 4.3 проверяемый план
является оптимальным. Если для некоторых клеток Ui+Vj>Cij, то план является неоптимальным. Тогда для каждой клетки, в которой не выполняется условие оптимальности, находим величину (Ui+Vj)-Cij>0.
Выбор клетки, в которую необходимо послать перевозку.
Загрузке подлежит в первую очередь клетка, которой соответствует max((Ui+Vj)-Qj).
Построение цикла и определение величины перераспределения груза.
Для определения количества единиц груза, подлежащих перераспределению, отмечаем знаком "+", незанятую клетку, которую надо загрузить. Это означает, что клетка присоединяется к занятым клеткам. Занятых клеток стало m+n, поэтому появляется цикл, все вершины которого за исключением клетки, отмеченной знаком "+", находятся в занятых клетках, причем этот цикл единственный. Отыскиваем цикл и, начиная движение от клетки, отмеченной знаком "+", поочередно проставляем знаки "-" и "+". Затем находим д =min Xij,
где Xij -перевозки, стоящие в вершинах цикла, отмеченной знаком "-". Величина 00 определяет, сколько единиц груза можно перераспределить
по найденному циклу. Значение о0 записываем в незанятую клетку,
отмеченную знаком "+". Двигаясь по циклу, вычитаем $0 из объемов
перевозок, расположенных в клетках, которые отмечены знаком "-", и прибавляем к объемам перевозок, находящихся в клетках, отмеченных знаком "+". Если 0 0 соответствует несколько минимальных перевозок,
то при вычитании оставляем в соответствующих клетках нулевые перевозки в таком количестве, чтобы во вновь полученном опорном плане занятых клеток было m+n-1.
Проверка нового плана на оптимальность.
Для проверки на оптимальность опорного плана можно вновь построить систему потенциалов и проверить выполнение условия оптимальности для каждой незанятой клетки. Если полученный план снова окажется неоптимальным, то следует выполнить вычисления, приведенные в предыдущем пункте. Процесс повторяют до тех пор, пока все незанятые клетки не будут удовлетворять условию (4.13).
Пример 4.1. Решить ТЗ:
| 5 4 6 3 | 200 |
| 1 10 2 1 | 300 |
| 2 3 3 1 | 100 |
| 150 150 250 50 | >Ч600 600 |
Решение. Условие баланса выполнено. Следовательно, имеем ТЗ закрытого типа.
 |
Число занятых клеток равно 6 и совпадает с рангом матрицы ограничений ТЗ:
г = m + n 1 = 2+4-1 = 6.
Итерация 1. Для проверки полученного опорного плана на оптимальность находим систему потенциалов для занятых клеток ( ху>0).
Для этого, например , полагаем U1= 0 ( записываем U1= 0 слева в табл. 4.2).
| V, = 5 | V 4 | V3 = 6 | V4 = 2 і і | ||
| и, = 0 | 5 5 | 4 1 100+ | 6 100- ■ | І2 1 3 | 1200 |
| U2 = -4 | 1 1 150- | 1 2 150+ | 1-2 | 300 | |
| из = -1 | 4 ГТ" 01 | 1 п~ 50- | 1 С 50 | ]100 | |
| 150 | 150 | 250 | 50 |
Далее, исходя из занятых клеток (1 , 2) и (1 , 3) , находим V2=
= 4 0 = 4, V3= 6 0 = 6 (записываем сверху в таблице ). На основе
базисной клетки (2 , 3) получаем u2=2 6 =-4 , затем v1= 1-(-4) = 5; u3
=3 4= -1; V4=2.
Далее вычисляем сумму потенциалов для каждой из свободных клеток и записываем их в верхнем левом углу. Так как для клеток (3,1) и (3,3) критерий оптимальности (условие B) не выполняется:
U3+ V1 = 4 > 2, U3+ V3 = 5 > 3,
то полученный опорный план не оптимальный . Так как А31= и3+ v1су = 2 = А33,
то в любую из клеток, например, в (3,1) , проставляем некоторое число 01.
Для того, чтобы не нарушился баланс в 3-ей строке, вычитаем 01 из величины перевозки, стоящей в клетке (3, 2) , прибавляем к Х12= 100, вычитаем от Х13, прибавляем к Х23 и вычитаем от Х21, т.е. составляем цикл :
(3,1)->(3,2)->(1,2)->(1,3)->(2,3)->(2,1)->(3,1).
Знаки + и в клетках чередуются .
Заметим, что движение от одой клетки к другой происходит только по занятым, кроме первой, в которую
проставляется 01. Максимальное
значение 01 равно наименьшему уменьшаемому: 01= 50. Если 01 взять
больше, то получаем отрицательную величину в плане перевозок, а если меньше , то нарушается опорность плана.
Новый опорный план приведен в таблице 4.3
| 5 * | 4 | 6 | 4 | |
| 0 | 5 ГТ" | I LO 150 | m 50 | 4 [ГЦ |
| -4 | 1 100 | I0 ш | 200 | 0 DZ |
| -3 | 50 | і Ш | 3 1 3 | | 50 |
Итерация 2 . Проверяем полученный план Х(1) на оптимальность. Находим систему потенциалов. Они записаны в таблице слева и сверху , вычисляем сумму потенциалов для свободных клеток (записаны в левом верхнем углу клетки). Так как
U1+ V4 = 4 > 3,
то план Х(1) не является оптимальным. Для построения нового опорного плана проставляем величину 02 в клетку (1,4) и составляем
цикл:
(1,4)->(3,4)>(3,1)->(2,1)->(2,3)->(1,3)->(1,4).
Определяем значение 02 =50, при этом две клетки (1,3) и (3, 4)
обращаются в нулевые. Следовательно, план Х(2) будет вырожденным. Для дальнейшего решения необходимо оставить нуль в одной из клеток и считать ее за базисную. Целесообразнее нуль оставить в клетке с меньшей стоимостью перевозок, т.е. в клетке (3,4) . Новый опорный план приведен в таблице 4.4
| 4 | 4 | 5 | 3 | |
| 0 | 4 [Г] | 150 | 5 ПН | ш 50 |
| -3 | Ш 50 | 1 ГкП | 250 | 0 Ш |
| -2 | m 100 | 2 m | 3 Ш | ш 0 |
Итерация 3. Число занятых клеток равно 6. Находим значения потенциалов и их сумму для свободных клеток. Критерий оптимальности выполняется:
Ui+ Vj< Cij для Ху= 0; i=1,m;j=1,n;
поэтому полученный план является оптимальным:
150
50 ^
X *
50
250
и
f(x*)= 1500
 |
Предварительный этап. Находим исходный опорный план х(0) методом ''минимального элемента'' (см. таблицу 4.5).
Таблица 4.5
| xYj | 7 | 3 | 12 | 2 | ||||
| 0 | 10- | 7 | 70 | 3 | 4 | 4 | 2 0, | 0 |
| -2 | 20+ | 5 | 1 | 7 | 2 | 8 | 40- | 0 |
| -2 | 5 | 3 | 1 | 8 | 60 | 2 | 0 | 0 |
Данный план является вырожденным, поэтому ставим ''0'' -перевозку в клетку с минимальным значением c1J, но так, чтобы не
образовалось замкнутого маршрута (цикла). В нашем примере c14 = c34 = 0, но занять клетку (1,4) нельзя, так как образуется цикл: (1,4) -(2,4) -(2,1) -(1,1) -(1,4).
Поэтому ставим ''0'' в клетку (3,4)
Итерация 1 . Проверяем план x(0) на оптимальность. Положив u1 = 0, находим потенциалы (см. таблицу). Далее находим сумму потенциалов для свободных клеток (они записаны в левом верхнем углу клетки). Так как
u1 + v4 = 2 > 0 u3 + v1 = 5 > 8,
то полученный опорный план x0 неоптимальный. Для клеток (1,4) и
(3,1) оценки одинаковы А14 = 2-0 = 2и А31 = 5-3 = 2, поэтому выбираем
любую, например, (1,4). Проставляем в эту клетку 01 и составляем цикл,
чередуя знаки ''+'' и получим 01 = 10. Новый опорный план
представлен в таблице (4.6).
| uJ | 5 | 3 | 2 | 0 | ||||
| 0 | 5 | 7 | 70 | 3 | 2 | 4 | 10 | 0 |
| 0 | 30- | 5 | 3 | 7 | 2 | 8 | 30+ | 0 |
| 0 | 5 0 2 | 3 | 3 | 8 | 60 | 2 | 0- | 0 |
Итерация 2.Находим систему потенциалов (см. слева и сверху табл. 4.6 ). Сумма потенциалов для небазисных клеток записана в левом верхнем углу. Критерий оптимальности не выполняется для клетки (3,1):
А 31 = 5 3 = 2 > 0.
Проставим в эту клетку 0 2 и составим замкнутую цепочку, в результате получаем 0 2 = 0.Опорный план x(2) представлен в таблице 4.7.
Итерация 3. Найдя систему потенциалов, убеждаемся в оптимальности плана x (2)(см. таблицу 4.7).
Таблица 4.7
| u14 | 5 | 3 | 4 | 0 | ||||
| 0 | 5 | 7 | 70 | 3 | 4 | 4 | 10 | 0 |
| 0 | 30 | 5 | 3 | 7 | 4 | 8 | 30 | 0 |
| -2 | 0 | 3 | 1 | 8 | 60 | 2 | -2 | 0 |
Транспортные издержки составляют 480 и
x* = (0, 70, 0, 30, 0, 0, 0, 0, 60). Так как четвертый потребитель фиктивный, то 10 ед. груза останутся у первого поставщика, 30 ед. у второго.
Определение оптимального плана транспортных задач, имеющих некоторые усложнения в их постановке.
1. При некоторых реальных условиях перевозки груза из определенного пункта At в пункт назначения Bj не могут быть
осуществлены. Для определения оптимальных планов таких задач предполагают, что стоимость перевозки единицы груза из пункта Л{ в пункт Bj является сколь угодно большой величиной М и при этом
условии известными методами находят решение транспортной задачи. Такой подход к нахождению решения ТЗ называется запрещением перевозок.
В отдельных ТЗ дополнительным условием является обеспечение перевозки по соответствующим маршрутам определенного количества груза. Пусть, например, из Л{ в Bj требуется обязательно перевезти a j
единиц груза. Тогда в соответствующую клетку таблицы, находящуюся на пересечении строки At и столбца Bj, записывают указанное число
atj ив дальнейшем считают эту клетку свободной со сколь угодно
большой стоимостью перевозки М. Для полученной таким образом новой транспортной задачи находят оптимальный план, который определяет оптимальный план исходной задачи.
Иногда требуется найти решение ТЗ, при котором из At в Bj
должно быть перевезено не менее заданного количества груза a j. Для
определения оптимального плана такой задачи считают, что запасы Л и
потребности Bj меньше фактических на aj единиц. После этого
находят оптимальный план новой ТЗ, на основании которого и определяют решение исходной задачи.
Пример 4.3.
