Решение открытой транспортной задачи

 Решение  открытой транспортной задачи

Содержание

     Введение                                                                                                              2 

  1. Транспортная  задача и методы её решения                                                   4

  1.1. Экономико-математическая  модель транспортной задачи                       4

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

  1.3. Методы  составления начального опорного  плана                                     9

  1.4. Понятие  потенциала и цикла                                                                     12

  1.5. Критерий  оптимальности базисного решения  транспортной задачи    15

  1.6. Распределительный  метод решения транспортной задачи                    16

  2. Разработка  и описание алгоритма решения  задачи                                   18

  2.1. Содержательная  постановка задачи                                                         18

  2.2. Построение  математической модели задачи                                           18 

  2.3. Решение  задачи вручную                                                                          18

  2.4. Решение  задачи с помощью Excel                                                            23 
 
 
 
 
 

                                                                                               

Введение

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

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

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

      

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

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

     1.Транспортная  задача  и методы  её решения

     1.1. Экономико-математическая  модель транспортной  задачи

Некоторый однородный продукт, сосредоточенный  у m поставщиков A_i  в количестве a_i (i=1,2,3,...,m) единиц соответственно, необходимо доставить n потребителям B_j в количестве b_j (j=1,2,3,...,n) единиц. Известна стоимость C_ij  перевозки единицы груза от i-го поставщика к j-му потребителю.

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

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

Таблица №1

Составим  математическую модель задачи. Так  как от i-го поставщика к j-му потребителю запланировано к перевозке x_ij единиц груза, то стоимость перевозки составит C_ijx_ij.

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

Z = .

Систему ограничений получаем из следующих  условий задачи:

А) все  грузы должны быть вывезены, т.е. 

(i  = 1,2,3,..., m) (эти уравнения получаются из строк таблицы    1);

Б) все  потребности должны быть удовлетворены, т.е. 

(j = 1,2,3,...,n)  (уравнения получаются из столбцов таблицы 1).

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

Найти наименьшее значение линейной функции:

Z =                                    ( 1)

При ограничениях

  ,     i = 1, 2, ..., m,              ( 2 )

,    j = 1,2,3,...,n ,                 ( 3 )

X_ij ³ 0 ( j = 1,2,3, ..., m;    i = 1,2,3, ..., n).

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

      ( 4 )

Такая модель называется закрытой. 

Теорема 1. Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение.

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

Доказательство. Пусть   = M > 0 .

Тогда   величины  x_ij = a_ib_j /M (i = 1,2,3, ... M ; j = 1,2,3, ..., n)                                являются планом, так как они удовлетворяют системе ограничений

( 2 ) и  ( 3 ) .

Действительно, подставляя значения  в  ( 2 ) и ( 3 ) , находим

= a_i ,

= b_j .

Выберем из значений  C_ij  наибольшее  C¢ = max C_ij и заменим в линейной функции ( 1 ) все коэффициенты  на C¢  тогда, учитывая ( 2 ) , получим

,

Выберем из значений C_ij  наименьшее C¢¢=min C_ij и заменим в линейной функции все коэффициенты на C¢¢ ; тогда, учитывая ( 2 ) имеем

Т. Е.  Линейная функция ограничена на множестве планов транспортной задачи. 
 
 

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

Транспортная  задача,  в  которой  суммарные  запасы и потребности совпадают, т. е. выполняется условие  , называется закрытой моделью;  в противном случае ¾ открытой. Для открытой модели может быть два случая:

1. суммарные запасы превышают суммарные потребности ;
2. суммарные потребности превышают суммарные запасы .

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

   Найти минимальное значение линейной  функции

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

,    i = 1, 2, ..., m,                           (случай  а)

,    j = 1, 2, ..., n;

,    i = 1, 2, ..., m,                           (случай б)

,   j = 1, 2, ..., n,

x_ij ³ 0   (i = 1, 2, ..., m;    j = 1, 2, ..., n).

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

   В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель B_n+1, потребности которого  b_n+1 = . В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик A_m+1, запасы которого a_m+1 = .