Конспект лекций по курсу «Математическое программирование»

 

Рис. 4.1.

 

Для отыскания оптимального решения исходной задачи воспользуемся  второй теоремой двойственности. Для  этого запишем систему равенств (4.7) и (4.8)

Подставив у₁=2, у₂=1, после очевидных преобразований получим систему

Решив полученную систему, найдем х₁= 9/19; х₂=34/19; х₃=0; f_min= 7.

 

5. ТРАНСПОРТНАЯ ЗАДАЧА.

 

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

 

1. Задача о перевозках.

 

Имеется m пунктов отправления А₁, А₂,..., А_m, в которых сосредоточен некоторый груз в количествах а₁,а₂,...,а_m и n пунктов назначения В₁, В₂,..., В_n, в которые требуется завезти этот груз в количествах b₁,b₂,...,b_n , причем

    . Известны стоимости c_ij перевозки единицы

груза из пунктов  А_i в пункты В_j ( ; ). Предполагается, что

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

б) стоимость перевозки груза  из одного пункта в другой пропорциональна количеству перевозимого груза.

Требуется составить  такой план перевозок из пунктов  А_i в пункты В_j, при котором затраты на перевозки были бы наименьшими.

Исходные данные задачи обычно представляются в виде транспортной таблицы (табл. 5.1).

 

 

Таблица 5.1

Пн По	В1	В2	. . .	В3	Запасы
А1	С11	С12	. . .	С1n	а1
А2	С21	С22	. . .	С2n	а2
. . .	. . .	. . .	. . .	. . .	. . .
Аm	Сm1	Сm2	. . .	Сmn	аm
Потребности	в1	в2	. . .	вn

 

Стоимости c_ij проставляются в правых  верхних углах соответствующих клеток.

Составим математическую модель задачи. Пусть x_ij – количество груза, перевозимого из пункта А_i в пункт В_j. Целевая функция задачи  (общая стоимость перевозок)  записывается  следующим образом:

 

Систему ограничений записываем, руководствуясь тем, что:

а) запасы пунктов  отправления должны быть исчерпаны;

б) потребности пунктов назначения должны быть удовлетворены;

в) перевозки  могут быть только неотрицательными.

Таким образом, ограничения задачи имеют вид:

 

Мы видим, что задача о перевозках является ЗЛП.

 

2. Общая постановка транспортной задачи.

 

Транспортной задачей называется ЗЛП следующего вида:

Отметим следующую  особенность транспортной задачи как  ЗЛП специального вида: система уравнений  разбита на две группы (5.2) и (5.3) так, что каждая переменная входит ровно в одно уравнение группы с коэффициентом 1.

Уравнения (5.2) называются горизонтальными, уравнения (5.3) -вертикальными.

Любой набор  значений переменных x_ij называется планом перевозок. План перевозок называется допустимым, оптимальным или опорным, если он является допустимым, оптимальным или опорным планом ЗЛП (5.1 - 5.4).

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

 

3. Отыскание исходного опорного плана перевозок.

 

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

а) метод северо-западного угла;

б) метод минимального элемента в строке;

в) метод минимального элемента.

 Пусть имеется транспортная  задача (5.1 - 5.4). Хотя в системе  (5.2 - 5.3) m+n уравнений, опорный план содержит только m+n–1 базисных переменных. Это объясняется тем, что одно из уравнений является следствием остальных, и в жордановой форме m+n–1 уравнений.

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

Возьмем  клетку (А_i,В_j) с наименьшей стоимостью перевозок. Проставим в нее перевозку, равную min(a_i,b_j). Затем "уменьшаем" транспортную таблицу, руководствуясь правилами:

1. если a_i < b_j, то исключаем из дальнейшего рассмотрения пункт отправления (ПО) А_i (и соответствующую строку); а в "меньшей" таблице потребность пункта назначения (ПН) В_j полагаем равной  b_j - a_i ;
2. если  b_j <a_i, то исключаем ПН В_j (и соответствующий столбец); в "меньшей" таблице полагаем запас ПО А_i равным  a_i - b_j;
3. если a_i = b_j, то:

а) если в таблице  только один ПО А_i и один ПН В_j, то алгоритм останавливается;

б) если в таблице один ПО А_i и несколько ПН, то исключаем В_j , считая в "меньшей" таблице запас пункта А_i равным 0;

в) если в таблице один ПН В_j и несколько ПО, то исключаем А_i, считая в "меньшей" таблице потребность пункта В_j, равной 0;

г) если в таблице несколько ПО и несколько ПН, то исключаем либо ПО А_i, полагая в "меньшей" таблице потребность ПН В_j равной 0, либо исключаем ПН В_j, полагая запас ПО А_i равным 0.

Подобные шаги проделывают до тех пор, пока не будут  исключены все строки и столбцы.  

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

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

Воспользуемся примером (табл. 5. 2).

Таблица 5.2

Пн По	В1	В2	В3	В4	Запасы
А1	10    4	15    3	5	7	25
А2	2	5          1	8	6	5
А3	0    4	9	30   3	15    2	45
Потребности	10	20	30	15	75=75

 

Рассмотрим  произвольную клетку (А_i, В_j) - клетку транспортной таблицы с наименьшей стоимостью перевозок - клетку (2.2).  Проставим в неё перевозку x₂₂=min(a₂,b₂)=min(20,5)=5. После этого   запас пункта А₂  полностью исчерпан. Исключим мысленно из таблицы вторую строку. В меньшей транспортной таблице потребность  пункта В₂ положим равной 25–10=15. Рассматриваем клетку с минимальной стоимостью новой таблицы. Руководствуясь тем же правилом, проставляем в неё перевозку х₃₄=15. Потребность пункта В₄  полностью удовлетворена, и мы исключаем из таблицы четвертый столбец, а в полученной транспортной таблице запас пункта А₃  делаем  равным 45–15 = 30. В клетку (3,3) с минимальной стоимостью, равной 3, проставляем перевозку х₃₃=min(30,30)=30. При этом одновременно исчерпывается запас пункта А₃ и удовлетворяется потребность пункта В₃.

Переходя к новой таблице, нельзя одновременно убрать и столбец, и строку. Нужно убрать либо столбец, либо строку. Уберем, например, столбец. Третья строка еще не исключена из таблицы, запас пункта А₃ полагаем равным 0, поэтому в клетку (3,1) с минимальной стоимостью, равной 4,  ставим перевозку х₃₁=min(10,0)=0. После этого исключаем третью строку из рассмотрения. Далее полагаем х₁₂=min(15,25)=15, исключаем второй столбец, а запас пункта А₁ делаем равным 25-15=10. Наконец, в клетку (1,1) проставляем х₁₁=10. Исходный опорный план найден. Базисными переменными являются х₁₁, х₁₂, х₂₂, х₃₁, х₃₃, х₃₄. Значения базисных переменных в опорном плане равны перевозкам, проставленным в соответствующих клетках. Опорный план является вырожденным, так как х₃₁=0. Число базисных переменных равно m+n–1, т.е. 3+4–1=6.

Метод минимального элемента усваивается очень легко. Чтобы убедиться в этом, проделайте самостоятельно такой пример (табл. 5.3.):

Таблице 5.3

Пн По	В1	В2	В3	Запасы
А1	2	3	1	40
А2	4	2	5	60
А3	3	2	6	50
Потребности	70	40	40	150=150

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

Таблица 5.4

Пн По	В1	В2	В3	Запасы
А1	2	3	40    1	40
А2	20     4	40     2	0    5	60
А3	3 50	2	6	50
Потребности	70	40	40	150=150

 

5.4. Циклы пересчета

5.4.1. Понятие цикла пересчета

 

Пусть имеется транспортная задача (5.1 - 5.4) и соответствующая таблица 5.1. Циклом называется замкнутая ломаная линия, вершины которой лежат в клетках таблицы, а звенья попеременно принадлежат то строке, то столбцу.

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

Цикл называется означенным, если его вершинам попеременно приписаны знаки "+" и "–".

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

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

В таблице 5.4 пунктиром показан  один цикл пересчета, который проходит через свободную клетку (1,1).

 

5.4.2. Максимально допустимый сдвиг  по циклу  пересчета.

 

Сдвигом на величину h ≥ 0 по циклу пересчета называется увеличение на число h перевозок, стоящих в положительных вершинах цикла, и уменьшение на число h перевозок, стоящих в отрицательных вершинах.

Так как в каждой строке и каждом столбце транспортной таблицы 
количество положительных вершин равно количеству отрицательных 
вершин цикла, то при сдвиге на любое число h условия (5.2) и (5.3) 
не нарушаются. Чтобы не нарушалось условие (5.4), величина сдвига 
не должна превышать минимальной перевозки, стоящей в отрицательной 
вершине цикла.