Транспортные задачи (на примере КПУП "Хойникский сыродельный комбинат")

 

Содержание

Введение                                                                                                3. 

Глава 1.  Понятие транспортной задачи.                                            4.

1.1 Понятие  транспортной задачи.                                                        4.

1.2  Закрытая и открытая модели транспортной задачи.                    6.

Глава 2.  Способы решения транспортных задач.                                         8.

                      2.1. Правило «северо-западного угла».                                         8.

                  2.2. Правило «минимального элемента».                                     9.

                  2.3. Метод потенциалов.                                                             10.

                       2.4. Постановка транспортной задачи на сети.                      11.

Глава 3. Постановка и решение транспортной задачи

 средствами  Excel на примере КПУП "Хойникский сыродельный комбинат"                                                                                             13.

Выводы                                                                                                  20.

Список  литературы                                                                              21. 
 
 
 
 
 
 
 
 
 
 
 
 

Введение. 

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

   Решение данного типа задач возможно при  помощи пакета Exсel, с использованием инструмента «Поиск решения». Данный способ  решения транспортных задач достаточно эффективен и рационален.

   В курсовой работе  содержится краткое  описание экономико-математического моделирования, краткое описание транспортных задач и способов их решения, расписан механизм решения транспортной задачи при помощи пакета Exсel, c приведением примеров решения на примере предприятия.

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

1.Понятие транспортной задачи. 

1. . Понятие транспортной задачи.

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

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

      Простейшая формулировка транспортной задачи по критерию стоимости следующая: в т пунктах отправления (Ai, ..., Am) находится соответственно единиц однородного груза (ресурсы), который должен быть доставлен п потребителям (B1,..., Вп) в количествах единиц (потребности). Известны транспортные издержки перевозок единицы груза из i-го пункта отправления в j-й пункт потребления.

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

      Для наглядности условия транспортной  задачи представим в виде таблицы, которая называется распределительной (табл. 1.). Здесь количество груза, перевозимого из i-го пункта отправления в j-й пункт назначения, равно , запас груза в i-м пункте отправления определяется величиной , а потребность j-го пункта назначения в грузе равна . Предполагается, что все .

  Матрица |Cij| m x n называется матрицей тарифов (издержек или транспортных расходов).

Планом  транспортной задачи называется матрица т x п, где каждое число обозначает количество единиц груза, которое надо доставить из i-го пункта отправления в j-й пункт назначения. Матрицу , называют матрицей перевозок. Общие суммарные затраты, связанные с реализацией плана перевозок, можно представить целевой функцией

                              

Таблица №1.

Поставщик	Потребитель			Запас груза
	В1	...	Bn
А1	с11	...	c1n	a1
	x11		x1n
...	...	...	...	...
Аm	cm1	...	cmn	am
	xm1		xmn
Потребность в грузе	b1	…	bn

      

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

                             (1).

                            (2).

                         .   (3).

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

   Система ограничений задачи содержит т+п уравнений с тп переменными. Предполагается, что суммарные запасы равны суммарным потребностям, т. е.

                       

                                                                  

2. Закрытая  и открытая модели транспортной задачи.

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

                                                             

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

                                 или  .

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

     

,

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

     Если  же , то вводится фиктивный (m+1)-й пункт отправления, которому приписывают запас груза, равный

     

.

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

     Для транспортной задачи важное значение имеет следующая теорема: ранг матрицы транспортной задачи на единицу меньше числа уравнений, т.е. r(A)=m+n-1.

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

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

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

     Этот  набор, или совокупность, клеток можно  представить так:

      (i1,j1)       (i1,j2)      (i2,j2)     ...        (is,js)      (is,j1).

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

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

Глава 2.   Способы решения транспортных задач. 

2.1. Правило «северо-западного угла»

         Для составления исходного плана  перевозок удобно пользоваться  правилом «северо-западного угла»,  которое состоит в следующем. 

   Будем заполнять таблицу, начиная с левого верхнего, условно называемого «северо-западным углом», двигаясь далее по строке вправо или по столбцу вниз. Занесем в клетку (1; 1) меньшее из чисел а1 и b1, т. е. x11=min(a1, b1). Если а1>b1, то х11=b11 и первый столбец «закрыт», т. е. спрос первого потребителя удовлетворен полностью. Это означает, что для всех остальных клеток первого столбца количество груза xi1=0 для i=2, ..., т.

  Двигаясь  дальше по первой строке таблицы, записываем в соседнюю клетку (1, 2) меньшее из чисел a1-b1 и b2, т. е. х12= =min(a1—b1, b2). Если b1>a1 то аналогично «закрывается» первая строка, т. е. x1k=0, для k=2..., п. Переходим к заполнению соседней клетки (2; 1), в которую заносим x2i=min(a2, b1— a1).

Заполнив  вторую клетку (1; 2) или (2; 1), переходим  к заполнению следующей третьей клетки по второй строке либо по второму столбцу. Будем продолжать этот процесс до тех пор, пока на каком-то этапе не исчерпаются ресурсы am и потребности bп. Последняя заполненная клетка окажется лежащей в последнем n-м столбце и в последней m-й строке.