11779

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

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

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

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

Русский

2013-04-11

256 KB

76 чел.

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


 

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

80969. Особливості пізнавального інтересу учнів до історії 35.74 KB
  Метою розвитку мотиваційної сфери учнів у навчанні історії виступає формування стійкого інтересу до предмета що передбачає активне емоційнопізнавальне ставлення школярів до досліджуваних історичних подій до зясування їхніх причин і наслідків а також до оволодіння вміннями необхідними для всебічного вивчення минулоі о і сучасності на основі різноманітних джерел. Отже одним із важливих завдань навчання в умовах цілісної методичної системи є підвищення рівня розвитку інтересу. У числі загальних зовнішніх причин падіння інтересу...
80970. Організація самостійної роботи учнів при вивченні теми: «Виникнення та розвиток Київської Русі » (7 клас) 39.16 KB
  Проблема диференційованого підходу до учнів у навчанні історії. Диференційоване навчання організація навчальновиховного процесу з урахуванням типових індивідуальних особливостей учнів. Складнішим і ефективнішим видом диференційованого навчання є здійснення його в умовах поділу класу на групи залежно від рівня навчальних можливостей учнів.
80971. Планування роботи із контурною картою при вивченні теми: «Великі географічні відкриття: зустріч цивілізацій» (8 клас) 37.85 KB
  Розглядаючи тему: Великі географічні відкриття доба відкриттів європейськими мореплавцями невідомих раніше морів та океанів островів і континентів здійснення першої навколосвітньої морської подорожі колонізації заморських територій кінець XVсеред. Нові географічні відкриття зумовлювалися насамперед бурхливим розвитком продуктивних сил прагненням європейців задовольнити зрослі потреби в дорогоцінних металах і прянощах відповідно пошуками морських шляхів до Китаю та Індії. Великі географічні відкриття стали можливими завдяки значному...
80972. Способи вивчення пізнавального інтересу учнів до історії 38.89 KB
  В учнівських диктантах було відтворено від 8 до 21 інформаційних одиниць. Діагностуючий диктант допомагає вчителю вчасно звернути увагу на труднощі в сприйнятті й осмисленні історичного матеріалу що є в учнів даного класу 9віку0. Якщо взяти за основу зміни особистісних особливостей учнів то в своїй роботі у напрямку посилення пізнавального інтересу учнів до історії перш за все беру до уваги що учні основної школи та старшої школи мають зовсім різну підготовки виходячи з їх віку.
80973. Дайте оцінку сучасним вимогам до уроків історії 39.52 KB
  Розуміння і виконання вчителем сучасних вимог до уроку які визначаються соціальним замовленням. Оптимального балансу в змісті уроку компонентів світової національної регіональної та локальної історії. Творчою емоційної атмосфери заснованої на інтерес учнів до змісту уроку та видами навчальної роботи...
80974. Визначення рівня розвитку пізнавальних здібностей школярів до вивчення історії 32.33 KB
  Наприклад: 1 Складіть максимальну кількість речень з одними і тими самими словами але різних за смислом: лицаріхрестоносці кривава битва князівські дружини діагностика вербальної уяви.Порівняйте два зображення на історичну тему і знайдіть відмінності діагностика довільної уваги. По деталі здогадайтеся що це за споруда і назвіть її діагностика образної уяви. На основі аналітичного опису намалюйте предмет про який іде мова діагностика репродуктивної та творчої уяви.
80975. Права та обов’язки вчителя історії 36.39 KB
  Мають право на: захист професійної честі гідності; участь в обговоренні та вирішенні питань організації навчальновиховного процесу; проведення науководослідної експериментальної пошукової роботи відповідно до діючих нормативних документів; вільний вибір форм методів засобів навчання виявлення педагогічної ініціативи; дострокову атестацію на отримання відповідної категорії і педагогічного звання; соціальне і матеріальне забезпечення відповідно до законодавства; підвищення кваліфікації перепідготовку вільний вибір змісту...
80976. Проблема методів навчання історії та їх класифікація 36.03 KB
  Провідні поняття повязані з процесом навчання історії стали предметом наукового інтересу в дискусіях радянських методистів у 5070ті pp. В обговоренні проблеми свої варіанти класифікації методів навчання історії в різні роки запропонували всі провідні вчені однак вони так і не прийшли до єдиної думки. Тому в сучасній методичній літературі збереглася різноманітність підходів до визначення понять методи прийоми способи навчання різні підстави їх систематизації і деяка суперечливість у вживанні методичних термінів у спеціальній...
80977. Дайте загальну характеристику історичних карт 37.4 KB
  Історичні карти карти що відображують історичні явища і події взаємозвязки суспільних явищ минулого з географічними чинниками показують розміщення древніх культур держав соціальні рухи торгівельні дороги пересування людей військові удари на карті показують стрілками місця боїв схрещеними мечами райони повстань крапками або вогнищами. Історичні карти створюються на географічній основі і є математично визначеним зменшеним узагальненим образнознаковим зображенням історичних подій явищ процесів чи періодів...