11779

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

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

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

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

Русский

2013-04-11

256 KB

77 чел.

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


 

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

68831. Формальні мови 88.5 KB
  Форма уявлення інформації визначається мовою тому у поданій дисципліні розглядаються питання повязані з переходом від однієї мови до іншої при представленні деякої інформації. Формальні мови Природні мови англійська російська українська та ін. Позбавитись цих недоліків природних мов дозволило...
68832. Загальна форма означення мови 123.5 KB
  Задати синтаксис це означає задати алфавіт та множину форм усіх речень мови семантика визначає смислове значення усіх цих речень. Існує декілька формальних засобів опису синтаксису мови. Оскільки синтаксис мови пов’язаний з множиною речень рядків символів необхідно домовитись про позначення...
68833. Особливості класифікації формальних мов 117 KB
  Наприклад контекстновільна граматика G1 розглянута у попередній лекції нерегулярна а мова L1 що нею генерується регулярна тому що її можна одержати за допомогою регулярної граматики G2. Граматики типу 3 а також регулярні граматики мають істотні переваги перед іншими типами граматик тому...
68834. Алгоритми 95 KB
  Частковий алгоритм зупиняється на даному вході якщо існує таке натуральне число t що після виконання t необовязково різних команд цього алгоритму або не виявиться жодної команди яку можна виконати або остання команда є зупинитись.
68835. Скінчені автомати 106.5 KB
  На вхід автомату надходять рядки символів вхідного алфавіту. Кожний черговий символ призводить до того що стан автомату змінюється згідно з функцією а на виході зявляється символ що відповідає функції. Приклад умовного зображення автомату для обчислення суми двох двійкових чисел наведено...
68836. Скінчені автомати, що приймають регулярні вирази 155 KB
  Побудова М7. Для побудови цього автомату використовується ідея приєднання виходу М1 до входу М2. Беремо Q7 = Q1  Q2, вважаючи, що Q1  Q2 =  , тобто усі стани автомату М1 відрізняються від станів автомату М2 незалежно від позначень. Множина заключних станів означається як...
68837. Лексичний аналіз 101.5 KB
  На даному етапі у вхідній програмі виділяються лексеми і формуються таблиці різних класів лексем. Типові класи лексем - це ідентифікатори, константи, ключові слова мови програмування. У результаті роботи лексичного аналізатора програма перетворюється у послідовність лексем.
68838. Контекстно-вільні граматики 85 KB
  Традиційною основою для синтаксичного аналізу є контекстновільні граматики. Коли якунебудь мову програмування не можна генерувати за допомогою контекстновільної граматики завжди можна знайти таку контекстновільну граматику що генерує супермову у якій міститься подана. З наведених раніше означень...
68839. Автомати з магазинною пам’яттю 132 KB
  Але на відміну від МНПмашини память МПавтомата побудована за принципом організації стека. Елементи інформації зберігаються та використовуються як патрони у автоматичній зброї тобто у кожний момент доступний тільки верхній елемент магазину.