Учебное пособие по курсу «Математика»

ТЕМА 3.2. Транспортная задача
3.2.1. Общая постановка транспортной задачи
Транспортная задача – одна из распространенных задач линейного программирования. Ее цель – разработка наиболее рациональных путей и способов транспортировки товаров, устранение чрезмерно дальних, встречных и повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением снабжения сырьем, материалами, топливом и т.д.

В классической постановке транспортную задачу можно представить следующим образом.

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

В зависимости от соотношения между суммарными запасами и суммарными потребностями груза различают закрытые и открытые транспортные задачи.

Транспортная задача называется закрытой (сбалансированной), если суммарные запасы груза равны суммарному спросу на него, т.е.: , и открытой (несбалансированной), если это равенство нарушено, т.е.: .

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


при ограничениях:
.

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

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

• 
  отыскание исходного опорного решения;
  
• 
  проверка этого решения на оптимальность;
  
• 
  переход от одного опорного решения к другому.
  

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

Существует несколько способов отыскания опорного решения. Рассмотрим наиболее часто употребляемый метод минимального элемента (тарифа). Согласно этому методу, грузы распределяются в первую очередь в те клетки, в которых указан минимальный тариф c_ij. Далее грузы распределяются в незанятые клетки с наименьшими тарифами с учетом оставшихся запасов поставщиков и неудовлетворенных потребностей потребителей. Процесс распределения продолжают до тех пор, пока запасы поставщиков будут исчерпаны полностью, а нужды потребителей – полностью удовлетворены.

При распределении грузов может оказаться, что количество занятых клеток меньше, чем . В этом случае полученное опорное решение называется вырожденным, и для решения такой задачи применяются методы подраздела 3.2.5.
ПРИМЕР: На складах имеются запасы продукции в количествах 90, 400 и 110 соответственно. Потребители нуждаются в этой продукции в количествах 140, 300 и 160 соответственно. Найти план перевозок, обеспечивающий минимум суммарных затрат на них, если тарифы перевозок заданы матрицей:

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

	1	2	3
1	2 90	5	2	90
2	4	1 300	5 100	400
3	3 50	6	8 60	110
	140	300	160	600

В табл. 3.1 число занятых клеток равно 5, т.е. условие не вырожденности опорного решения выполнено. Исходное решение можно записать в виде матрицы:


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

Теперь можно переходить к следующему шагу алгоритма решения транспортной задачи – проверке полученного исходного опорного решения на оптимальность.
3.2.3. Проверка опорного решения на оптимальность
Исходное опорное решение, как и любое другое решение, проверяется на оптимальность методом потенциалов по следующему критерию: если решение транспортной задачи является оптимальным, то ему соответствует система (m + n) действительных чисел u_i и v_j, называющихся потенциалами и удовлетворяющих условиям: для занятых клеток распределительной таблицы и для свободных клеток.

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

Введем обозначение: . Эту оценку называют оценкой свободных клеток. Если , то решение является оптимальным, если же хотя бы одна из оценок , то решение оптимальным не является и его можно улучшить, перейдя к другому опорному плану.
ПРИМЕР: Проверить на оптимальность опорное решение, полученное в примере подраздела 3.2.2.

Добавим в распределительную таблицу 3.1 столбец и строку , заменив ими столбец и строку соответственно:

Таблица 3.2.

	1	2	3
1	2 90	5	2	0
2	4	1 300	5 100	–2
3	3 50	6	8 60	1
	2	3	7

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

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

Вычислим оценки свободных клеток:


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

Для свободной клетки с положительной оценкой строится цикл (многоугольник), все вершины которого кроме одной находятся в занятых клетках. В этом многоугольнике все углы прямые, а число вершин четное. В свободной клетке цикла (внизу слева) ставится знак (+), а затем в занятых клетках цикла поочередно проставляются знаки (–) и (+). У вершин со знаком (–) выбирают минимальный груз, его прибавляют к грузам, стоящим в вершинах со знаком (+), и отнимают от грузов у вершин со знаком (–). В результате такого перераспределения грузов получают новое опорное решение, которое проверяют на оптимальность и т.д.
ПРИМЕР: Осуществить переход к новому опорному решению для опорного решения, записанного в таблице 3.2 подраздела 3.2.3.

Для решения поставленной задачи в таблице 3.2 образуем цикл для клетки (1, 3). Кроме нее вершинами цикла будут клетки (1, 1), (3, 1) и (3, 3), как показано в таблице 3.3.
Таблица 3.3.

	1	2	3
1	2 90 (–)	5	2 (+)	0
2	4	1 300	5 100	–2
3	3 50 (+)	6	8 60 (–)	1
	2	3	7

Для вершин со знаком (–) выбираем минимальный груз, он равен 60, вычитаем его из грузов, стоящих в отрицательных вершинах, и прибавляем его к грузам, стоящим в положительных вершинах. В результате получаем новое опорное решение, которое представлено в таблице 3.4.

Таблица 3.4.

	1	2	3
1	2 30 (–)	5	2 60 (+)	0
2	4 (+)	1 300	5 100 (–)	3
3	3 110	6	8	2
	2	–2	2

Проверим полученное решение на оптимальность, для чего найдем потенциалы и оценки свободных клеток. В результате получим (убедитесь в этом сами):


Построим цикл для клетки с положительной оценкой (2, 1), как показано в таблице 3.4, и произведем перераспределение грузов. В результате получим новое решение, которое занесем в таблицу 3.5.
Таблица 3.5.

	1	2	3
1	2	5	2 90	0
2	4 30	1 300	5 70	3
3	3 110	6	8	2
	1	–2	2

Проверим новое решение на оптимальность и получим (убедитесь в этом сами):

Все полученные оценки свободных клеток отрицательные, следовательно, найденное решение оптимальное. Итак:
,

а суммарная стоимость транспортных расходов по этому плану составит:


3.2.5. Вырожденность в транспортных задачах
При решении транспортной задачи может оказаться, что число занятых клеток в исходном опорном решении меньше, чем . В этом случае транспортная задача называется вырожденной или имеющей вырожденное решение. Для возможного исключения вырожденного решения целесообразно поменять местами поставщиков и потребителей или ввести в свободную клетку с наименьшим тарифом нулевую поставку. Нулевую поставку следует помещать в такую клетку таблицы, чтобы в каждой строке и каждом столбце было не менее одной занятой клетки. При этом клетка с нулевой поставкой не может служить вершиной цикла при перераспределении продукции.
ПРИМЕР: Фирма осуществляет поставку бутылок на четыре завода, занимающихся производством прохладительных напитков. Она имеет 3 склада, на которых имеется 6000, 3000 и 4000 бутылок соответственно. Потребность заводов составляет 4000, 5000, 1000 и 3000 бутылок соответственно. Тарифы перевозки 1 бутылки от каждого склада до каждого завода заданы матрицей:


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

Запишем исходные данные в распределительную таблицу 3.6, найдем исходное опорное решение методом минимального тарифа и занесем это решение в эту же таблицу.
Таблица 3.6.

	1	2	3	4
1	6	4 3000	9	8 3000	6000	0
2	5	3 2000	2 1000	8	3000	–1
3	2 4000	3 0	6	8	4000	–1
	4000	5000	1000	3000	13000	-
	3	4	3	8	-	-

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

Для исключения вырожденности необходимо в какую-то свободную клетку таблицы ввести нулевую поставку. Такая клетка становится условно занятой и должна иметь минимальный тариф по сравнению с другими клетками, которые могут быть условно занятыми. Поэтому для обеспечения возможности нахождения потенциала поместим нулевую поставку в клетку (3, 2), тогда появится возможность обычным порядком найти значения всех потенциалов, которые занесем в таблицу.

При этом оценки свободных клеток получатся следующие:


Все полученные оценки отрицательны, следовательно, получено оптимальное решение:

и минимальная стоимость транспортных расходов составит 28000.

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

Пусть суммарное предложение больше суммарного спроса, т.е. . В этом случае все потребители будут удовлетворены полностью, а часть запасов окажется невостребованной. Для решения задачи вводят фиктивного (n + 1)-го потребителя с потребностями, равными .

Если же суммарный спрос превышает суммарное предложение, т.е. , то часть потребностей окажется неудовлетворенной. Для решения такой задачи вводят фиктивного (m + 1)-го поставщика с запасом, равным .

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

Рекомендуемая литература по теме 3.2: [3, 5 ÷ 8].
ВОПРОСЫ:

1. 
   Что является критерием закрытости транспортной задачи?
   

2. 
   В чем состоит основная идея метода минимального элемента?
   

3. 
   Каков критерий оптимальности решения транспортной задачи при использовании метода потенциалов?
   

4. 
   Что должно быть минимальным в оптимальном решении транспортной задачи?
   

5. 
   В чем состоит основной принцип преобразования открытой транспортной задачи в закрытую задачу?
   

6. 
   Какими способами можно избавиться от вырожденности решения транспортной задачи?
   

ТЕМА 3.3. Целочисленное программирование
Если управляющие переменные в задаче линейного программирования определяют количество единиц неделимой продукции, то оптимальное решение должно быть получено в целых числах. К задачам такого типа относится довольно большое количество экономических задач: распределение производственных заказов между предприятиями, оптимальный раскрой материалов, определение загрузки оборудования, распределение транспортных средств по рейсам, а также задачи производства и реализации неделимой продукции (станков, телевизоров, автомобилей и т.п.).

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

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


при ограничениях:
3.3.1. Графический метод решения задач целочисленного программирования
Если в задаче целочисленного программирования количество управляющих переменных равно двум, а ограничения имеют вид неравенств, то ее можно решить графическим методом. При этом процесс решения состоит из двух этапов.
Этап 1. Решение исходной задачи обычным графическим методом. Если найденное оптимальное решение является целочисленным, то решение прекращают. Если же найденное оптимальное решение содержит хотя бы одно дробное значение, то переходят к этапу 2.

Этап 2. В непосредственной близости от границ ОДР задачи со стороны, где расположена вершина оптимального решения нецелочисленной задачи (т.е. вблизи тех границ ОДР, куда указывает вектор градиента целевой функции), строят точки, координатами которых являются целые числа. Дальнейшее решение в точности повторяет графическое решение обычной задачи линейного программирования, с тем лишь отличием, что, продвигая в направлении вектора градиента линию уровня целевой функции, находят последнюю из целочисленных точек на пути продвижения. Именно ее координаты и будут являться оптимальным целочисленным решением исходной задачи.
ПРИМЕР: Найдите графическим методом оптимальное решение целочисленной задачи линейного программирования, заданной моделью вида:

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

Как следует из рассмотрения рис. 3.4, ОДР задачи есть трапеция ОАВС, а оптимальным решением задачи будут являться координаты точки В, т.е. получено нецелочисленное оптимальное решение задачи в виде: .

Построим внутри ОДР целочисленную сетку и примем во внимание точки D, E и F, имеющие целые значения координат. Очевидно, что наиболее близкой к точке В оказывается точка Е, координаты которой и будут являться искомым целочисленным решением: и при этом .
3.3.2. Метод Гомори решения задач целочисленного

программирования
Для решения задач целочисленного программирования с любым количеством управляющих переменных может быть успешно применен метод Гомори. Алгоритм решения задачи этим методом содержит два этапа.
Этап 1. Решение задачи линейного программирования без условия целочисленности управляющих переменных обычным симплекс – методом. Если все значения управляющих переменных оптимального плана – целые числа, то решение заканчивают. Если же полученное оптимальное решение содержит хотя бы одно дробное значение управляющих переменных, то переходят к этапу 2.
Этап 2. Составление дополнительного ограничения (сечения) и решение расширенной задачи обычным симплекс – методом. При этом дополнительное ограничение (сечение) отсекает нецелочисленные решения, оставляя только целочисленные.
Целой частью [r] рационального числа r называется наибольшее целое число, не превосходящее числа r. Дробной частью числа r называется правильная дробь {r}, определяемая соотношением: {r} = r – [r].

Пример 1. Для числа 5 имеем: [5] = 5 и {5} = 0.

Пример 2. Для числа 4/5 имеем: [4/5] = 0 и {4/5} = 4/5.

Пример 3. Для числа 8/3 имеем: [8/3] = 2 и {8/3} = 2/3.

Пример 4. Для числа – 4/5 имеем: [- 4/5] = - 1 и {- 4/5} = 1/5.

Пример 5. Для числа – 8/3 имеем: [- 8/3] = - 3 и {- 8/3} = 1/3.

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

и пусть некоторое - дробное число. Рассмотрим i-ое ограничение задачи:


С учетом обозначений: и дополнительное ограничение (сечение) для переменной можно записать в виде:

, где .

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

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

ПРИМЕР: Найдите методом Гомори целочисленное решение задачи примера подраздела 3.3.1.

Решив поставленную задачу симплекс-методом, получим последнюю симплекс-таблицу, содержащую оптимальное (не целочисленное) решение, (убедитесь в этом сами) в виде:

БП					СЧ
	1	0	1	–1/2	3/2
	0	1	0	1/2	5/2
L	0	0	1	1/2	13/2

Поскольку оба свободных члена имеют одинаковую дробную часть, равную 1/2, для определенности будем составлять сечение по Гомори для переменной . Его можно записать в виде:
.

Введя это ограничение и дополнительную базисную переменную в приведенную симплекс-таблицу, получим новую симплекс-таблицу, из которой в одну итерацию получим искомое целочисленное решение поставленной задачи.

БП						СЧ
	1	0	1	–1/2	0	3/2
	0	1	0	1/2	0	5/2
	0	0	0	1/2	–1	1/2
L	0	0	1	1/2	0	13/2
	1	0	1	0	–1	2
	0	1	0	0	1	2
	0	0	0	1	–2	1
L	0	0	1	0	1	6

Из последней симплекс-таблицы следует и при этом: .
Рекомендуемая литература по теме 3.3: [3, 5, 7, 8].
ВОПРОСЫ:

1. 
   Чем отличаются целочисленные задачи от обычных задач линейного программирования?
   

2. 
   В чем суть графического метода решения задач целочисленного программирования?
   

3. 
   В чем суть метода Гомори решения задач целочисленного программирования?
   

4. 
   Для какой управляющей переменной составляется дополнительное ограничение по Гомори?