11779

ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ТЗЛП)

Домашняя работа

Информатика, кибернетика и программирование

ТЕМА 1 ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ТЗЛП 1. Содержательная постановка и формальная модель ТЗЛП. 2. Условие существования решения ТЗЛП. Построение формальной модели ТЗЛП при нарушении усло...

Русский

2013-04-11

256 KB

73 чел.

ТЕМА 1

ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ (ТЗЛП)

1. Содержательная постановка и формальная модель ТЗЛП.................................

2. Условие существования  решения ТЗЛП............................................................

3. Построение формальной модели ТЗЛП при нарушении условия баланса в

    содержательной постановке ТЗЛП......................................................................

4 Примеры сведения ЗЛП к ТЗЛП

5. Свойства ТЗЛП............................................................................

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

 6.1. Методы построения начального ДБР...................................................

  6.1.1. Метод северо-западного угла................................................

  6.1.2. Метод наименьшей стоимости.............................................

  6.1.3. Приближенный метод Фогеля...............................................

 6.2. Вырожденность в ТЗЛП........................................................................

 6.3. Этапы метода потенциалов...................................................................

  6.3.1.  Выбор переменной, вводимой в базис................................

  6.3.2.  Выбор переменной, выводимой из базиса..........................

  6.3.3.  Переход к новому БДР..........................................................

 6.4.  Схема алгоритма метода потенциалов................................................

7. Транспортная модель с промежуточными пунктами.........................................

1. СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА И ФОРМАЛЬНАЯ МОДЕЛЬ ТЗЛП

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

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

Представим транспортную модель в виде сети. В ней:

вершины соответствуют пунктам производства и потребления,

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

вес дуги – расстояние между соотв. пунктами.

 


                                 
Пункты производства    Пункты потребления

                                                                               

                                                                                   

                                                                                        

                                                                                    

                                                                           

                                                                                         

                                                                   

Математическая модель задачи такова:    

Z из (1) представляет собой суммарные транспортные издержки.

Задача (1)-(4) является задачей линейного программирования и называется транспортной задачей. Такое название связано со структурой данной задачи, а не с содержательной постановкой. К модели вида (1)-(4) может привести задача , по своему содержанию никак не связанная с транспортом  и планированием перевозок. В таких случаях говорят, что данная задача может быть сформулирована в терминах транспортной задачи.

2. УСЛОВИЕ СУЩЕСТВОВАНИЯ РЕШЕНИЯ  ТЗЛП

Для того, чтобы решение задачи (1)-(4) существовало, необходимо, чтобы  

                                                                                    

т.е. суммарный объем производства был не меньше суммарного спроса.

Если                                            ,                                    (5)     (не вытирать)

то говорят, что имеют сбалансированную транспортную модель, а условие (5) называется условием баланса.

Сбалансированная транспортная модель имеет вид:

    

ТЕОРЕМА 1.

   Для того, чтобы задача (6)-(9) имела  допустимое решение, необходимо и достаточно,  чтобы выполнялось условие баланса.

Доказательство.

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

Пусть  - допустимое решение (ДР) задачи (6)-(9).  Это значит, что оно удовлетворяет ограничениям (7)-(9):

Для   просуммируем по i ограничения (7'):

затем просуммируем по  j  ограничения  (8'):

Так как левые части (10) и (11) отличаются лишь порядком суммирования, то из  (10) и (11) следует справедливость (5).

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

Обозначим через  d  суммарное количество продукта :

и определим     c  помощью следующих соотношений:

                           

Покажем, что набор  является ДР задачи (6)-(9):

Во-первых:  0  (выполняются условия (9)).

Во-вторых: , i=1,..,m   выполняются условия (7).

В-третьих:  , j=,..,n     выполняются условия (8).

Достаточность доказана. Таким образом, теорема доказана.

Любая транспортная модель может быть сбалансирована. Стремление сбалансировать транспортную задачу (т.е. превратить все ее ограничения в равенства) обусловлено возможностью применить в этом случае эффективный вычислительный метод.

3. ПОСТРОЕНИЕ  ФОРМАЛЬНОЙ  МОДЕЛИ  ТЗЛП  ПРИ  НАРУШЕНИИ УСЛОВИЙ  БАЛАНСА   В СОДЕРЖАТЕЛЬНОЙ  ПОСТАНОВКЕ

3.1. Пусть в содержательной постановке имеет место следующее соотношение:

                                                

Введем фиктивный пункт потребления   c объемом потребления

                       

и положим

. Строим задачу (6)-(9),  для которой выполняется условие баланса. В этой задаче количество переменных составляет уже .

Тогда  - неперевезенная (избыточная) продукция пункта .

Если же мы положим, что    -  штраф за за хранение избыточной продукции в пункте , то целевая функция задачи (6)-(9) будет соответствовать сумме затрат на перевозку продукции и затрат на хранение избыточной продукции.

3.2. Пусть в содержательной постановке задачи   .

Введем фиктивный пункт производства  c объемом  производства :

Тогда   это объемы недостающей продукции в пунктах .

Если мы положим, что  - штраф за недопоставку продукции в пункт  , то целевая функция задачи (6)-(9) будет соответствовать сумме затрат на перевозку продукции и штрафов за ее недопоставку.

4 Примеры сведения ЗЛП к ТЗЛП

В ряде случаев дополнительные мощности у одного или нескольких производителей удается ввести за счет сверхурочных работ. Покажем на конкретном примере, как в этом случае данную задачу можно свести к задаче (6)-(9).

Пусть имеется три предприятия (пункты производства) и четыре потребителя продукции (пункты назначения).

Предприятия

Потребители продукции

Мощности

1

2

3

4

1

25

17

25

14

300

2

15

10

18

24

500

3

16

20

8

13

600

1400

Потребности

300

300

500

500

1600

И пусть мощность каждого предприятия можно увеличить на 50%, введя сверхурочные работы, однако удельные издержки производства возрастают при этом соответственно на 10, 15 и 20 ед.стоимости. Сверхурочные работы можно учесть в задаче, добавив три "сверхурочных" предприятия, как это показано в следующей таблице. Если бы использовалась вся дополнительная мощность, полученная за счет сверхурочных работ, то образовался бы излишек равный 2100-1600=500 ед. Поэтому необходимо ввести фиктивного потребителя с этой потребностью.

Предприятия

Потребители продукции

Мощности

1

2

3

4

Фиктивн

1

25

17

25

14

0

300

2

15

10

18

24

0

500

3

16

20

8

13

600

1 сверхур.

35

27

35

24

0

150

2 сверхур.

30

25

33

39

0

250

3 сверхур.

36

40

28

33

0

300

Потребности

300

300

500

500

500

2100

 

Самостоятельно.№1  Доказать, что решение этой задачи автоматически дает гарантию того, что ни на одном предприятии не будут введены сверхурочные работы, пока не будет полностью использована его номинальная мощность.

4. СВОЙСТВА   ТЗЛП       

 

Выпишем ограничения для случая m=2, n=3.

Построим для общего случая вектора  , соответствующие переменным    i=1..m, j=1..n, и вектор правых частей ограничений p0 :

                      

Если переменные     упорядочены следующим образом:

                         ,

то матрица  Р коэффициентов левой части системы (2) примет следующий вид:

 Особенности системы ограничений (13) определяют возможность использования при решении задачи (12)-(14) более простого вычислительного алгоритма, чем С-М. Эти особенности исходной системы уравнений заключаются в следующем:

1. Коэффициенты при неизвестных во всех уравнениях равны 0 и 1.

2. Каждая переменная встречается в двух и только двух уравнениях.

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

Матрица  Р имеет  размерность  (m+n) (mn).  Очевидно, что ранг матрицы Р  не может превышать   m+n, (Почему?) т.к.  ТЗЛП  имеет смысл, если   m>1 и  n>1, и в этом случае     m+n   mn.

Легко заметить, что если из суммы первых  m строк вычесть сумму последних n строк, то получим нулевую строку. Следовательно, ранг матрицы Р  r(Р)  m+n-1  и каждая из строк матрицы Р может быть выражена как линейная комбинация остальных строк.

ТЕОРЕМА 2

Ранг матрицы  Р  равен  m+n - 1.

Доказательство. 1 способ.

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

 Представим себе, что мы умножили

вторую строку матрицы Р  на некоторое число    

третью       строку                на                                 

m-ю           строку                на                                 

(m+1)-ю  строку                на                                  

(m+2)-ю  строку                на                                 

......

(m+n)-ю   строку                 на                                

и, сложив после этого поэлементно все эти строки, получили нулевую строку (у нее mn координат). Тогда для первых n  координат этой нулевой строки получим последовательно равенства:

Отсюда следует, что  .

Далее для  (n+1)-й, (2n+1)-й, (3n+1)-й, ... ((m-1)n+1)-й  координат получаем:  

Отсюда, учитывая, что , получаем, что , что и требовалось доказать.

Аналогично можно показать, что вообще любые (m+n-1)  строк матрицы  Р  линейно независимы. Таким образом   r(P)=m+n-1.

Доказанное выше свойство ТЗЛП говорит о том, что при решении задачи (12)-(14) симплекс-методом следует отбросить одно (любое)  из ее ограничений-уравнений.

ТЕОРЕМА 3.

Любой минор матрицы Р транспортной задачи принимает одно из трех   числовых значений  0,  1 или  -1.

Доказательство [2].

Выделим следующие свойства матрицы p транспортной задачи

1. Каждый элемент матрицы Р равен либо 0 либо 1.

2. Каждый столбец содержит не более двух ненулевых элементов.

3. Множество всех строк матрицы Р можно разбить на два множества Р1 и Р2, где Р1  состоит из m первых строк (соответствующих ограничениям по производителям), а Р2 - из n последних (соответствующих ограничениям по потребителям). При этом, если 

если два ненулевых элемента лежат в одном столбце матрицы Р , то строки, содержащие эти элементы, принадлежат разным множествам Р1 и Р2 .

Покажем теперь, что значение каждого минора матрицы Р равно 0, 1, -1.

Очевидно, что любая подматрица Р' матрицы Р обладает свойствами 1-3. Поэтому достаточно показать, что любая матрица Р', обладающая этими свойствами, имеет определитель, равный 0, 1, -1. Проведем доказательство индукцией по порядку k квадратной (kk)-матрицы Р'.

Для k=1 справедливость теоремы следует из свойства 1.

Пусть утверждение верно для матриц порядка k-1 и пусть Р' - квадратная матрица порядка k.  Возможны 3 следующих случая:

(1) Каждый столбец матрицы Р' имеет ровно два ненулевых элемента. Тогда из свойства 3 следует, что сумма всех строк из множества Р1 равна сумме всех строк из множества Р2. Следовательно, в этом случае строки матрицы Р' линейно зависимы, и Р' = 0.

(2) В некотором столбце все элементы равны нулю, значит Р' = 0.  

(3) Не все столбцы содержат ровно 2 ненулевых элемента и нет нулевых столбцов, т.е. в каком-либо столбце матрицы Р' имеется ровно один ненулевой элемент. Разложим определитель матрицы Р' по этому столбцу. Тогда Р'=Р'' , где Р'' - подматрица, получаемая вычеркиванием в матрице Р' выделенного столбца и строки, содержащей ненулевой элемент этого столбца. Порядок квадратной матрицы Р'' равен k-1, и по индуктивному предположению Р'' = 0, 1, -1, откуда имеем Р' = 0, 1, -1.  Что и требовалось доказать.

ТЕОРЕМА 4.

если все  и   в ТЗ - целые, то все  в любом ДБР ( в т.ч. и  оптимальном) также будут целыми числами.

Доказательство [2].

Пусть x =  , i=1..m, j=1..n  - ДБР задачи (12)-(14), т.е

                                        Р x = p0 ,     x  0 .

Пусть B - матрица, составленная из базисных вектор-столбцов матрицы Р ,  xB -   вектор базисных переменных ДБР x . Тогда  B xB = p0 . Решая эту квадратную систему уравнений по правилу Крамера, получаем, что

                                              =  B ij      B ,

 где B ij - матрица, полученная из B заменой столбца на вектор p0 . Поскольку все элементы матрицы B ij - целые числа, то и определитель   B ij  - целое число.  С учетом того, что   B = 1 (по теореме 3), получаем справедливость утверждения.

PAGE  3


 

А также другие работы, которые могут Вас заинтересовать

52611. Действия с десятичными дробями (запись, округление, сложение, вычитание) 27 KB
  Предметом усвоения являются общие способы действия способы решения класса задач. В дальнейшем общий способ действия конкретизируется применительно к частным случаям. На каждом последующем уроке конкретизируется и развивается уже освоенный способ действия.