11779

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

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

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

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

Русский

2013-04-11

256 KB

75 чел.

ТЕМА 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


 

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

80565. Оцінка ефективності інвестицій 180 KB
  Ефективність дохідність довготермінових облігацій може бути виміряна у вигляді: купонної дохідності норма відсотка облігації; ставки розміщення річної ставки складних відсотків. Ставка розміщення найбільш точно характеризує реальну фінансову ефективність облігації враховуючи всі види доходів від неї. Отже завдання вимірювання фінансової ефективності облігації зводиться до обчислення ставки розміщення у вигляді річної ставки складних відсотків. Нарахування відсотків за цією ставкою на ціну придбання облігації яка може відрізнятись від...
80566. Особливості фінансів малого бізнесу 232 KB
  Малий бізнес є найбільш поширеним сектором економіки. Відмінності між цими трьома видами бізнесу обумовлені різним рівнем суспільного поділу праці, характером спеціалізації га усуспільнення виробництва, а також вибором технологічного типу виробничого процесу.
80568. Направления совершенствования расчетного и кассового обслуживания клиентуры в Новоуренгойском отделении Сберегательного банка №8369 707.5 KB
  Сберегательный Банк Российской Федерации – старейший банк страны. Созданный в 1841 году как финансовый институт для малоимущих слоёв населения, он и по сегодняшний день остаётся единственным банком, который обслуживает наименее обеспеченные группы физических лиц.
80569. Процесс перевозки грузов автомобильным транспортом на примере ОО УМ «Газпромдорстрой» 718 KB
  Автомобильный транспорт состоит на пороге больших перемен. Меняются требования к его работе. Необходимо поднять использование автомобилей на новый более качественный уровень развития...
80570. РАЗРАБОТКА СТРАТЕГИЙ РАЗВИТИЯ ПРЕДПРИЯТИЯ (НА ПРИМЕРЕ ИП «СОРОЧИНСКАЯ Л.В.») 482 KB
  Цель работы охарактеризовать деятельность работы магазина розничной торговли и выявить перспективы развития данного предприятия. В первой части содержатся теоретические аспекты разработки стратегии развития организации.
80571. Анализ финансового состояния ООО «Транстехсервис» 191.37 KB
  Целью данной выпускной квалификационной работы является выявление и обоснование основных направлений совершенствования финансового состояния ООО «Транстехсервис» Исходя из цели исследования данного дипломного проекта, в работе поставлены следующие задачи: рассмотреть теоретические основы анализа финансового...
80572. Электрооборудование и электроснабжение электромеханического цеха 370.94 KB
  Организация проверки и наладки электрооборудования после монтажа или ремонта. Спецификация электрооборудования. Избыток тепла от электрооборудования и освещения. Для безопасного обслуживания электрооборудования находящегося на ферме моста устанавливают блокировочные контакты на люке и двери кабины.
80573. Розробка автономного недорогого універсального охоронного пристрою 1.1 MB
  Види систем охоронної сигналізації: охоронна система, яка у випадку спрацьовування будь-якого датчика активує сирену або строб-спалах; система сигналізації з підключенням до телефонної лінії. При появі сигналу тривоги по телефонній лінії передається заздалегідь записане голосове повідомлення...