Содержание
Введение 2
1. Постановка задачи и ее математическая модель 3
2. Модели транспортной задачи 7
2.1. Закрытаямодель транспортной задачи 7
2.2. Открытаямодель транспортной задачи 8
3. Определение оптимального и опорного плана транспортнойзадачи 10
4. Методы определения первоначального опорного плана 12
4.1. Методминимального элемента 12
4.2. Методаппроксимации Фогеля 14
5. Методы определения оптимального плана 16
5.1. Венгерскийметод 16
5.2. Методпотенциалов 17
Списокиспользованной литературы 19
Введение
Транспортная задачалинейного программирования получила в настоящее время широкое распространение втеоретических обработках и практическом применении на транспорте и в промышленности.Особенно важное значение она имеет в деле рационализации постановок важнейшихвидов промышленной и сельскохозяйственной продукции, а также оптимальногопланирования грузопотоков и работы различных видов транспорта.
Кроме того, к задачам транспортноготипа сводятся многие другие задачи линейного программирования — задачи оназначениях, сетевые, календарного планирования.
Цель заданной работы — освоить математическую постановку транспортной задачи линейногопрограммирования.
1. Постановка задачи и ее математическаямодель
Транспортнаязадача является частным типом задачи линейного программирования и формулируетсяследующим образом. Имеется m пунктов отправления (или пунктов производства) Аi…, Аm, в которых сосредоточены запасы однородных продуктов вколичестве a1, ..., аm единиц. Имеется n пунктовназначения (или пунктов потребления) В1, ..., Вm,потребность которых в указанных продуктах составляет b1, ..., bnединиц. Известны также транспортные расходы Сij, связанные сперевозкой единицы продукта из пункта Ai в пункт Вj, i />1, …, m; j />1, ..., n.Предположим, что
/>
т. е. общий объемпроизводства равен общему объему потребления. Требуется составить такой планперевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворитьспрос всех пунктов потребления за счет реализации всего продукта,произведенного всеми пунктами производства, при минимальной общей стоимостивсех перевозок. Приведенная формулировка транспортной задачи называется замкнутойтранспортной моделью. Формализуем эту задачу.
Пустьхij — количество единиц продукта, поставляемого из пункта Аiв пункт Вj. Подлежащие минимизации суммарные затраты на перевозкупродуктов из всех пунктов производства во все пункты потребления выражаютсяформулой:
/> (1)
Суммарное количествопродукта, направляемого из каждого пункта отправления во все пункты назначения,должно быть равно запасу продукта в данном пункте. Формально это означает, что
/>, i />1, …, m (2)
Суммарное количество груза,доставляемого в каждый пункт назначения из всех пунктов отправления, должнобыть равно потребности. Это условие полного удовлетворения спроса:
/>, j />1, …, n (3)
Объемы перевозок — неотрицательные числа, так как перевозки из пунктов потребления в пунктыпроизводства исключены:
xij/>0, i />1, ..., m; j />1, ..., n (4)
Транспортнаязадача сводится, таким образом, к минимизации суммарных затрат при выполненииусловий полного удовлетворения спроса и равенства вывозимого количествапродукта запасам его в пунктах отправления.
Определение 1.
Всякое неотрицательноерешение системы линейных уравнений
/>, j />1, …, n и />, i />1, …, m,
определяемое матрицей X=(xij)(i/>1,…, m; j />1,..., n), называется планом транспортной задачи.
Определение 2.
/>/>ПланX*=(x*ij)(i/>1,…, m; j/>1,..., n), при котором функция
/>
принимает свое минимальноезначение, называется оптимальным планом транспортной задачи.
Обычно исходные данныезаписываются в виде таблицы 1.
Таблица 1.Пункты отправления Пункты назначения Запасы
В1 …
Bj …
Bn
А1
A1
C11
X11 …
C1j
X1j …
C1n
X1n
a1 … … … … … … …
Ai
Ci1
Xi1 …
Cij
Xij …
Cin
Xin
ai … … … … … … …
Am
Cm1
Xm1 …
Cmj
Xmj …
Cmn
Xmn
am Потребности
b1 …
bj …
bn
Очевидно, общее наличиегруза у поставщиков равно />, а общая потребность в грузе впунктах назначения равна единице. Если общая потребность в грузе в пунктахназначения равна запасу груза в пунктах отправления, т.е.
/>, (5)
то модель такойтранспортной задачи называется закрытой.
В ряде случаев нетребуется, чтобы весь произведенный продукт в каждом пункте производства былреализован. В таких случаях баланс производства и потребления может бытьнарушен:
/>, i />1, ..., m.
Введение этого условияприводит к открытой транспортной модели.
Теорема1.
Любая транспортная задача, у которойсуммарный объем запасов совпадает с суммарным объемом потребностей, имеетрешение.
2.Модели транспортной задачи
2.1. Закрытаямодель транспортной задачи
Для доказательстватеоремы необходимо показать, что при заданных условиях существует хотя бы одинплан задачи и линейная функция на множестве планов ограничена.
Доказательство. Пусть />= M > 0/>.
Тогда величины xij= aibj/M (i= 1,2,3,… m; j= 1,2,3, ..., n) являются планом, таккак они удовлетворяют системе ограничений
( 2 ) и ( 3 ) .
Действительно, подставляя значения в (2) и (3), находим
/>= ai ,
/> = bj .
Выберем из значений Cij наибольшее C¢= maxCij и заменим в линейной функции ( 1 )все коэффициенты на C¢ тогда, учитывая ( 2 ), получим
/>,
Выберем из значений Cij наименьшее C¢¢=minCij и заменим в линейной функции всекоэффициенты на C¢¢; тогда, учитывая ( 2 ) имеем
/>
Объединяя два последних неравенства водно двойное, окончательно получаем
C¢¢M? Z? C¢M,
т. е. линейная функция ограничена намножестве планов транспортной задачи.
2.2. Открытаямодель транспортной задачи
Транспортная задача,в которой суммарные запасы и потребности не совпадают, т. е. не выполняетсяусловие />, называется открытой. Дляоткрытой модели может быть два случая:
a) суммарныезапасы превышают суммарные потребности />;
b) суммарныепотребности превышают суммарные запасы />.
Линейная функция одинакова в обоихслучаях, изменяется только вид системы ограничений.
Найти минимальное значение линейнойфункции
/> при ограничениях
/>, i = 1, 2, ..., m, (случай а)
/>, j = 1, 2, ..., n;
/>, i = 1, 2, ..., m, (случай б)
/>, j = 1, 2, ..., n,
xij³0 (i = 1, 2, ..., m; j = 1, 2, ..., n).
Открытая модель решается приведениемк закрытой модели.
В случае (а), когда суммарные запасыпревышают суммарные потребности, вводится фиктивный потребитель Bn+1, потребности которого bn+1 = />. В случае (б), когда суммарныепотребности превышают суммарные запасы, вводится фиктивный поставщик Am+1, запасы которого am+1 = />.
Стоимость перевозки единицы груза какфиктивного потребителя, так и стоимость перевозки единицы груза от фиктивногопоставщика полагают равными нулю, так как груз в обоих случаях не перевозится.
После преобразований задача принимаетвид закрытой модели и решается обычном способом. При равных стоимостяхперевозки единицы груза от поставщиков к фиктивному потребителю затраты наперевозку груза реальным потребителям минимальны, а фиктивному потребителюбудет направлен груз от наименее выгодных поставщиков. То же самое получаем и вотношении фиктивного поставщика.
Прежде чем решатькакую-нибудь транспортную задачу, необходимо сначала проверить, к какой моделиона принадлежит, и только после этого составить таблицу для ее решения./>
3.Определение оптимального и опорного плана транспортной задачи
Как и при решении задачилинейного программирования, симплексным методом, определение оптимального планатранспортной задачи начинают с нахождения какого-нибудь ее опорного плана.
Число переменных Xijв транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах (2) и (3) равно n+m. Так как мы предполагаем, чтовыполняется условие (5), то число линейно независимых уравнений равно n+m-1 отличных от нуля неизвестных.
Если в опорном плане числоотличных от нуля компонентов равно в точности n+m-1, то план является не выраженным, аесли меньше — то выраженным.
Для определения опорного планасуществует несколько методов. Три из них — метод северно-западного угла, методминимального элемента и метод аппроксимации Фогеля — рассмотрены ниже.
При составлении первоначальногоопорного плана методом северо-западного угла стоимость перевозки единицы неучитывается, поэтому построенный план далек от оптимального, получение которогосвязано с большим объемом вычислительных работ. Обычно рассмотренный методиспользуется при вычислениях с помощью ЭВМ.
Как и для всякой задачилинейного программирования, оптимальный план транспортной задачи является иопорным планом.
Для определения оптимальногоплана транспортной задачи можно использовать изложенные выше методы. Однаковвиду исключительной практической важности этой задачи и специфики ееограничений [каждое неизвестное входит лишь в два уравнения системы (2) и (3) икоэффициенты при неизвестных равны единице] для определения оптимального планатранспортной задачи разработаны специальные методы. Два из них — методпотенциалов и Венгерский метод — рассматриваются ниже.
4. Методыопределения первоначального опорного плана
4.1. Методминимального элемента
Суть методазаключается в том, что из всей таблицы стоимостей выбирают наименьшую и вклетку, которая ей соответствует, помещают меньшее из чисел />и />. Затем из рассмотренияисключают либо строку, соответствующую поставщику, запасы которого полностьюизрасходованы, либо столбец, соответствующий потребителю, потребности которогополностью удовлетворены, либо и строку и столбец, если израсходованы запасыпоставщика и удовлетворены потребности потребителя. Из оставшейся части таблицыстоимостей снова выбирают наименьшую стоимость, и процесс распределения запасовпродолжают, пока все запасы не будут распределены, а потребности удовлетворены.
/>Пример
Составитьпервоначальный опорный план методом минимального элемента для транспортнойзадачи вида:2 3 4 15 11 6 10 1 8 9 3 3 4 1 2 21 10 20 10
Решение:
Задача сбалансирована.
Строим первоначальныйопорный план методом минимального элемента.Выясним минимальную стоимость перевозок. />Первая перевозка будет осуществляться с пункта производства />в пункт потребления />и она составит максимально возможное число единиц продукта />:. В этом случае, потребности пункта потребления />будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки />.Выясним минимальную стоимость перевозок (без учета столбца № 2).
/>Вторая и третья перевозки будут осуществляться с пункта производства />и />в пункт потребления />и />соответственно и составят максимально возможное число единиц продукта: />, />; /> Четвертая перевозка осуществляется с пункта />в пункт потребления />, т.к. />(без учета первого, второго столбца и четвертой строки). />. Пятая перевозка осуществляется с пункта />в пункт потребления />, т.к. />(без учета первого, второго столбца, третьей и четвертой строки). />.
6. Шестаяперевозка осуществляется с пункта />в пункт потребления />т.к. />(без учета первого,второго столбца, первой, третьей и четвертой строки).
/>
Опорный план имеет вид;10 5 1 3 11 10
4.2. Метод аппроксимации Фогеля
При определении опорногоплана транспортной задачи методом аппроксимации Фогеля находят разность по всемстолбцам и по всем строкам между двумя записанными в них минимальными тарифами.Эти разности записывают в специально отведенных для этого строке и столбце втаблице условий задачи. Среди указанных разностей выбирают минимальную. Встроке (или в столбце), которой данная разность соответствует, определяютминимальная стоимость.
Если минимальнаястоимость одинакова для нескольких клеток столбца (строки), то для заполнениявыбирают ту клетку, которая расположена в столбце (строке), соответствующемнаибольшей разности между двумя минимальными стоимостями, находящимися в данномстолбце (строке).
Пример
Найти методомаппроксимации Фогеля первоначальный опорный план транспортной задачи:
(Здесь мы перенеслипотребности в верхнюю строку для удобства построения плана). Рассмотрим задачу,приведенную для методов северо-западного угла и минимального элемента
Решение:10 20 10
2
7
3
0
4
8 15 1 1 1
11
0
6
1
10
0 1 4 4 -
8
3
9
0
3
0 3 5 - -
4
0
1
19
2
2 21 1 1 - 2 2 1 2 2 2 2 2 2 2 - 2 - - 2 - - -
Опорный план имеет вид:7 8 1 3 19 2
5. Методыопределения оптимального плана
5.1. Венгерскийметод
Идея метода была высказана венгерскимматематиком Эгервари и состоит в следующем. Строится начальный план перевозок,не удовлетворяющий в общем случае всем условиям задачи (из некоторых пунктовпроизводства не весь продукт вывозится, потребность части пунктов потребленияне полностью удовлетворена). Далее осуществляется переход к новому плану, болееблизкому к оптимальному. Последовательное применение этого приема за конечноечисло итераций приводит к решению задачи.
Алгоритм венгерского метода состоитиз подготовительного этапа и из конечного числа итераций. На подготовительномэтапе строится матрица X0 (xij[0])m,n, элементы которой неотрицательны иудовлетворяют неравенствам:
, i 1, …, m;
, j 1, …, m.
Если эти условия являютсяравенствами, то матрица Хo — решение транспортной задачи. Если среди условийимеются неравенства, то осуществляется переход к первой итерации. На k-йитерации строится матрица Хk (xij[0])m,n. Близость этой матрицы к решениюзадачи характеризует число Dk — суммарная невязка матрицы Хk:
.
В результате первой итерации строитсяматрица Хl, состоящая из неотрицательных элементов. При этом Dl D0. Если Dl 0, то Хl — оптимальное решение задачи. Если Dl 0, то переходят к следующейитерации. Они проводятся до тех пор, пока Dk при некотором k не станет равнымнулю. Соответствующая матрица Хk является решением транспортной задачи.
Венгерский метод наиболее эффективенпри решении транспортных задач с целочисленными объемами производства ипотребления. В этом случае число итераций не превышает величины D0/2 (D0 — суммарная невязка подготовительного этапа).
Достоинством венгерского методаявляется возможность оценивать близость результата каждой из итераций коптимальному плану перевозок. Это позволяет контролировать процесс вычислений ипрекратить его при достижении определенных точностных показателей. Данноесвойство существенно для задач большой размерности.
5.2. Методпотенциалов
Метод потенциалов являетсямодификацией симплекс-метода решения задачи линейного программированияприменительно к транспортной задаче. Он позволяет, отправляясь от некоторогодопустимого решения, получить оптимальное решение за конечное число итераций.Общая схема отдельной итерации такова. По допустимому решению каждому пунктузадачи сопоставляется число, называемое его предварительным потенциалом.Пунктам Аi соответствуют числа ui, пунктам Bj — числа vj. Они выбираются такимобразом, чтобы их разность на k-й итерации была равна Сij — стоимости перевозкиединицы продукции между пунктами Аi и Вj:
vj[k] – ui[k] Cij, i 1,..., m; j 1, …, п.
Если разность предварительныхпотенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученныйплан перевозок является решением задачи. В противном случае указывается способполучения нового допустимого плана, связанного с меньшими транспортнымииздержками. За конечное число итераций находится оптимальный план задачи.
Списокиспользованной литературыЕ. Г. Гольштейн, Д. Б. Юдин «Задачи линейного программирования транспортного типа», Москва, 1993. И. Л. Акулич, В. Ф. Стрельчонок «Математические методы и компьютерные технологии решения оптимизационных задач», Рига, 2000. www.fmi.asf.ru