РОЗРАХУНКОВЕ ЗАВДАННЯ 1. ТРАНСПОРТНА ЗАДАЧА ЛІНІЙНОГО ПРОГРАМУВАННЯ

Короткі теоретичні відомості

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

Пусть в p пунктах отправления находятся соответственно a1 , a2 , …, a p

i 1

L c11x11 c12 x12 ... cpq xpq . Классическая транспортная задача является сбалан-

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

виям и минимизирующих целевую функцию L . Решение такой задачи разбивается на два этапа:

1)определение исходного опорного решения;

2)построение последовательных итераций, т.е. приближение к оптимальному решению.

1. Определение исходного опорного решения.

Пусть мы имеем таблицу исходных данных задачи. Исходное решение будем строить по так называемому правилу “северо-западного угла”.

9

Заполнение начнем с ячейки (1, 1): x11 min{150,60} 60 , первый столбец закрыт. Переходим к ячейке (1, 2): x12 min{150 60,70} 70 , второй столбец закрыт; далее, переходим к клетке (1, 3): x13 min{150 60 70,110} 20 . Так как в

третьем столбце оказался остаток, равный 90, то переходим к заполнению клетки (2, 3), куда заносим x23 min{90,90} 90 . Поскольку остатки по строке и

столбцу равны нулю, опорное исходное решение построено. Этому плану соответствуют затраты в количестве L 6 60 10 70 4 20 8 90 1860 ден. ед.

В правиле “северо-западного угла” не учитывается величина затрат cik , а

поэтому исходное опорное решение часто может быть далеким от оптимального.

Применяют также прием “минимального элемента”, в котором учитывается величина cik . В этом случае построение исходного опорного решения начи-

нают с клетки с наименьшей величиной cik , в данном примере – с клетки (2, 2),

1. Построение последовательных итераций.

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

Итак, после построения исходного опорного решения все переменные разбиты на две группы: xkl базисные и x pq свободные; линейные функции сто-

имости перевозок выразятся через свободные переменные так: L pq x pq 0 .

pq

11

Для нахождения коэффициентов pq при свободных переменных сопоставим каждому пункту отправления Ai некоторую величину ui (i 1,2,..., m) , которую назовем потенциалом пункта Ai , и каждому пункту назначения B j величину v j потенциал пункта B j . Свяжем эти величины равенством uk vl ckl , где ckl стоимость перевозки одной тонны груза из пункта Ak в пункт Bl . Доказывается, что совокупность уравнений uk vl ckl , составленных для всех базис-

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

u p vq c/pq , и назовем ее косвенной стоимостью (в отличие от данной стоимости c pq ). Тогда коэффициенты при свободных переменных в соотношении

L pq x pq 0 определяются с помощью равенства pq c pq c/pq .

pq

Если все величины pq неотрицательны, то исходное решение является оп-

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

Воспользуемся изложенными общими понятиями и продолжим решение нашей задачи. Мы получили исходное опорное решение (следуя правилу “ми-

L 1020 12x12 2x21 . Среди коэффициентов при переменных в правой части нет отрицательных. Значит, исходное опорное решение является оптимальным.

Решим теперь эту же задачу при условии, что исходное решение получено

L 1860 2x21 12x22 . Среди коэффициентов при переменных в правой части есть отрицательный при x22 , следовательно, можно попытаться уменьшить L , уве-

12

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

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

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

3.Для выбранной в п.2 переменной находят соответствующий ей цикл пересчета и производят сдвиг по этому циклу. Этот сдвиг приводит к новому допустимому решению.

4.Вышеуказанные операции 1-3 повторяют до тех пор, пока не получат оптимальный базис, т.е. неотрицательные коэффициенты при свободных переменных в правой части линейной функции L .

13