Вторая теорема двойственности.

Рекомендованная литература: [ 3, 5, 6, 7, 8, 11]

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

Розглянуті питання з теми:

Постановка задачи

Нахождение опорного плана

Метод последовательного улучшения плана перевозок, цикл пересчета

Решение транспортной задачи методом потенциалов

Постановка задачи

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

Рассмотрим постановку задачи и ее математическую модель.

Пусть некоторый однородный продукт, сосредоточенный у m поставщиков A1,A2,...,Am в количестве соответственно a1, a2,..., am единиц, необходимо доставить n потребителям B1, B2,..., Bn в количестве b1, b2, ..., bn единиц. Известна стоимость cij перевозки единицы груза от i-го поставщика к j-ому потребителю, заданная в виде таблицы (матрицы): Вторая теорема двойственности. - student2.ru .

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

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

Математическая модель транспортной задачи: обозначим через xij - количество единиц груза, направляемого из i-го пункта отправления Ai в j-й пункт назначения Bj (i=1, ..., m; j=1, ...,n), и которые будем называть перевозками. Все переменные xij ³ 0, их количество - m×n. Эти переменные могут быть записаны в виде матрицы перевозок Х= Вторая теорема двойственности. - student2.ru .

Так как от i-го поставщика к j-ому потребителю запланировано к перевозке xij единиц груза, то стоимость одной перевозки составит сijxij. Стоимость всего плана выразится двойной суммой, т.к. суммирование производится по всем комбинациям индексов (i=1, ...,m; j=1, ...,n), т.е. по всем комбинациям пунктов отправления с пунктами назначения. Причем суммарная стоимость всех перевозок, т.е. сумма всех xij, умноженных на соответствующие стоимости cij, должна быть минимальной:

L= Вторая теорема двойственности. - student2.ru =min, (1)

Систему ограничений получаем из следующих условий:

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

Вторая теорема двойственности. - student2.ru (2)

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

Вторая теорема двойственности. - student2.ru (3)

Мы имеем типичную ЗЛП с ограничениями-равенствами. Математическая формулировка ТЗ будет следующей: на множестве неотрицательных (допустимых) решений системы ограничений Вторая теорема двойственности. - student2.ru найти такое решение X=(x11,x12,…,xij, …,xmn), при котором значение линейной функции (1) минимально.

В рассмотренной модели предполагается, что сумма всех заявок равна сумме всех запасов Вторая теорема двойственности. - student2.ru (4)

Если суммарная мощность поставщиков равна суммарной мощности потребителей, т.е. Вторая теорема двойственности. - student2.ru , такая задача называется задачей с правильным балансом, а ее модель закрытой. В противном случае ТЗ называется задачей с неправильным балансом, а ее модель открытой.

Для открытой модели возможны два случая:

а) суммарные запасы превышают суммарные потребности Вторая теорема двойственности. - student2.ru ;

б) суммарные потребности превышают суммарные запасы Вторая теорема двойственности. - student2.ru .

Линейная функция одинакова в обоих случаях.

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

В случае (а), когда суммарные запасы превышают суммарные потребности, сверх имеющихся n пунктов назначения B1, B2, ..., Bn вводится фиктивный потребитель Вn+1 (Bф), потребности которого Вторая теорема двойственности. - student2.ru . Положим стоимости всех перевозок из всех ПО в фиктивный ПН Bф равными нулю: ciф = 0 (i=1, ...,m)., т.к. груз не перевозится. Т.о., отправление какого-то количества груза xiф из пункта Ai в пункт Bф попросту будет означать, что в пункте Ai осталось не отправленным xiф ед. груза. Введением bф сравнивается баланс ТЗ.

В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Аm+1 (Aф), запасы которого Вторая теорема двойственности. - student2.ru . Положим стоимость перевозок из ПО Aф в любой ПН равным нулю: cфj=0(j=1, ...,n). Т.е. какая-то часть заявок xфj на каждом пункте останется неудовлетворенной, будем считать, что она как бы покрывается за счет фиктивного ПО Aф.

Таким образом, стоимость перевозки единицы груза как до фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, т.к. груз в обоих случаях не перевозится.

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

Условие задачи в определенном порядке можно записать в виде таблицы, которую назовем транспортной таблицей или матрицей планирования.

Вторая теорема двойственности. - student2.ru ПН ПО B1 B2 ... Bn Запасы ai
A1 c11 x11 c12 x12 ...   c1n x1n a1
A2 c21 x21 c22 x22 ...   c2n x2n a2
... ... ... ... ... ...
Am cm1 xm1 cm2 xm2 ...   cmn xmn am
Заявки bj b1 b2 ...   bn Вторая теорема двойственности. - student2.ru

В транспортной таблице записываются

n пункты отправления и запасы, имеющиеся в пунктах отправления,

n пункты назначения и заявки, поданные пунктами назначения,

n стоимости перевозок из каждого пункта отправления в каждый пункт назначения в правом верхнем углу каждой ячейки

n количество единиц груза xij, запланированных к перевозке от i-го поставщика к j-му потребителю в самой ячейке.

Клеткой (i,j) называется клетка, стоящая в i-й строке и j-м столбце транспортной таблицы.

Пример. Составить математическую модель ТЗ, исходные данные которой таковы:

Вторая теорема двойственности. - student2.ru ПН ПО B1 B2 Bn Запасы ai
A1      
A2      
Заявки bj  

Введем переменные задачи (матрицу перевозок) Х= Вторая теорема двойственности. - student2.ru

Запишем матрицу стоимостей С= Вторая теорема двойственности. - student2.ru .

Целевая функция равна сумме произведений всех соответствующих элементов матриц С и Х: Z(X)= 9x11+5x12+3x13+4x21+6x22+8x23. Она должна достигать минимального значения.

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

x11+x12+x13=90,

x21+x22+x23=110. Это значит, что запасы поставщиков вывозятся полностью.

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

x11+x21=50,

x12+x22=70,

x13+x23=80. Это значит, что запросы потребителей удовлетворяются полностью.

Перевозки не могут быть отрицательными: xij>=0, i=1,2,..,m; j=1,2,...,n.

Математическую модель: найти переменные задачи, обеспечивающие минимум функции Z(X)= 9x11+5x12+3x13+4x21+6x22+8x23 и удовлетворяющие системе ограничений

Вторая теорема двойственности. - student2.ru x11+x12+x13=90,

x21+x22+x23=110,

x11+x21=50,

x12+x22=70,

x13+x23=80,

и условиям неотрицательности xij>=0, i=1,2,..,m; j=1,2,...,n.

Рассмотрим необходимое и достаточное условие разрешимости задачи.

Теорема. Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, т.е.

Вторая теорема двойственности. - student2.ru ,

имеет решение.

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

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

Вторая теорема двойственности. - student2.ru

Выберем из значений Сij наибольшее С’=max Cij и заменим в линейной функции L= Вторая теорема двойственности. - student2.ru все коэффициенты на С'; тогда, учитывая (2), получаем Вторая теорема двойственности. - student2.ru £C’ Вторая теорема двойственности. - student2.ru =C’ Вторая теорема двойственности. - student2.ru =C’M.

Выберем из значений Сij наименьшее С’’=minCij и заменим в линейной функции L= Вторая теорема двойственности. - student2.ru все коэффициенты на С'’; тогда, учитывая (2), получаем Вторая теорема двойственности. - student2.ru ³C’’ Вторая теорема двойственности. - student2.ru =C’’ Вторая теорема двойственности. - student2.ru =C’’M.

Объединяя два последних неравенства в одно двойное, окончательно получим

C’’M£L£C’M,

т.е. линейная функция ограничена на множестве планов ТЗ.¨

Нахождение опорного плана

Решение ТЗ, как и других ЗЛП, начинается с нахождения опорного плана. В отличие от ОЗЛП с произвольными ограничениями и минимизируемой функцией, решение ТЗ всегда существует.

Любая совокупность значений (xij) (i=1, ...,m; j=1, ...,n), удовлетворяющая условиям (2), (3) (так называемым «балансовым условиям»): все заявки удовлетворены, все запасы исчерпаны называется допустимым планом перевозок (решением).

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

Опр.1. Опорным планом ТЗ называется любой допустимый план, для которого векторы условий, соответствующие положительным компонентам, линейно независимы, т.е. если в допустимом плане отличны от нуля не более r=m+n-1 базисных перевозок xij, а остальные перевозки равны нулю.

Система ограничений закрытой ТЗ содержит m+n уравнений, связанных соотношением Вторая теорема двойственности. - student2.ru , и mn переменных. Не все m+n уравнений нашей задачи являются линейно независимыми. Так, складывая между собой почленно все уравнения (2) Вторая теорема двойственности. - student2.ru i=1,2,…,m и все уравнения (3) Вторая теорема двойственности. - student2.ru j=1,2,…,n, получаем два одинаковых уравнения. В транспортной таблице такое сложение равнозначно соответственно по членному сложению столбцов и почленному сложению строк.

Наличие в системе ограничений 2-х одинаковых уравнений говорит о ее линейной зависимости. Если одно из этих уравнений отбросить, то в общем случае система ограничений должна содержать m+n-1 линейно независимых уравнений.

Опорный план называется невырожденным, если он содержит m+n-1 положительных компонент (перевозок), иначе он называется вырожденным.

Таким образом, если каким-либо способом получен невырожденный опорный план ТЗ, то в матрице Вторая теорема двойственности. - student2.ru (i=1,2,…,m; j=1,2,…,n) значений его компонент положительными являются только m+n-1, а остальные равны нулю.

Опр.2. Опорным планом ТЗ называется любой допустимый план в котором отличны от нуля не более m+n-1 перевозок, а остальные равны нулю.

Клетки таблицы, в которых мы будем записывать отличные от нуля перевозки, условимся называть занятыми, а остальные (пустые) - свободными. Занятые клетки соответствуют базисным переменным, и для невырожденного опорного плана их количество равно m+n-1.

Как известно, базисным переменным, включенным в опорный план, соответствует система линейно независимых векторов.

Для проверки линейной независимости векторов условий, соответствующих компонентам допустимого плана, используют циклы.

Циклом называется такая последовательность клеток таблицы ТЗ (i1,j1),(i1,j2),(i2,j2),...,(ik,j1), в котором только две соседние клетки расположены в одном столбце или одной строке таблицы, причем последняя клетка находится в той же строке или столбце, что и первая. Построение циклов начинают какой-либо занятой клетки, вычерчивают вспомогательную линию, параллельную столбцам или строкам таблицы к другой занятой клетке, в которой возможен поворот под углом 90°, и продолжают вычерчивание к следующей занятой клетке, стремясь возвратиться к исходной клетке. Если такой возврат возможен, то получен цикл и план является не опорным. Клетки, в которых происходит поворот под прямым углом, определяют вершины цикла.

Система векторов условий ТЗ линейно независима тогда и только тогда, когда из соответствующих им клеток таблицы нельзя образовать ни одного цикла. Следовательно, допустимый план ТЗ Х= Вторая теорема двойственности. - student2.ru (i=1,2,…,m; j=1,2,…,n) является опорным только в том случае, когда из занятых им клеток нельзя образовать ни одного цикла, все вершины которого лежат в занятых клетках.

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

Для проверки возможности образования цикла используется метод вычеркивания:

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

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

Существует несколько схем построения первоначального опорного плана:

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

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

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

Наши рекомендации