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


 

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

42231. ТЕХНОЛОГИЧЕСКИЙ КОНТРОЛЬ ФОРМЫ ПОЛИРОВАННЫХ ПОВЕРХНОСТЕЙ 945 KB
  Если контролируемую поверхность детали совместить с измерительной поверхностью эталона то при несоответствии их формы образуется воздушный промежуток который можно рассматривать как пластинку толщиной h с показателем преломления n=1. Число колец любого но одного цвета характеризует разность стрелок прогиба поверхности детали и эталона. Форма интерференционных колец в сечении параллельном их направлению воспроизводит профиль воздушного зазора между поверхностями детали и эталона. Если кривизна поверхности детали меняется плавно кольца...
42232. ИССЛЕДОВАНИЕ НАГРЕВА КАТУШЕК ЭЛЕКТРИЧЕСКИХ АППАРАТОВ 44 KB
  Предмет исследования В лабораторной работе исследуются четыре катушки N1. На передней панели стенда расположены исследуемые катушки N1 N4. Каждая катушка включена в соответствующую схему выключателем а в цепи катушки N1 имеется амперметр P1 тип М381 класс точности 15 по которому контролируют значение протекающего через обмотку катушки тока. Катушки N1 и N2 подключаются выключателем SF2 к источнику постоянного напряжения 110 В а катушки N3 и N4 выключателем SF1 к источнику переменного напряжения 220 В.
42233. Методы проведения фотоэлектроколориметрии двухкомпонентных систем 2.19 MB
  Фотоколориметрия основана на измерении поглощения света окрашенными растворами. Отличается от колориметрии тем, что интенсивность поглощения света оценивается не глазом исследователя, а специальными приборами – фотоэлектроколориметрами.
42234. Побудова лінійної моделі з допомогою псевдообернених операторів 63.5 KB
  На виході системи спостерігається сигнал у вигляді вектора розмірності . Постановка задачі: Для послідовності вхідних сигналів та вихідних сигналів знайти оператор перетворення вхідного сигналу у вихідний. Систему 1 запишемо у матричній формі або 2 де – матриця вхідних сигналів розмірності – матриця вихідних сигналів розмірності . Варіанти вхідних на вихідних сигналів для яких потрібно побудувати лінійний оператор перетворення вхідного сигналу у вихідний: 1 Вхідний сигнал – x1.
42235. Методи реалізації на мові Асемблера основних виконавчих операторів мови Паскаль. Методика включення текстів програм на мові Асемблера в програми на мові Паскаль 136.5 KB
  Робота виконується на двох заняттях. На першому занятті на базі програми на мові Паскаль студенти створюють файл, що містить результати трансляції кожного оператора Паскаль-програми на мові Асемблера, вивчають методи реалізації на мові Асемблера найуживаніших операторів мови Паскаль. На другому занятті оформляють у Паскаль-програмі асемблерну вставку, що оптимізує, по можливості, Паскаль-програму в обсязі і/або швидкодії.
42236. ПЗО побудувати на Intel 8255 39 KB
  Для керування використовувати розряд 4 каналу РС для сигналу Redy розряд 0 каналу РС. Очікування сигналу “Redy†РС0=1. Ввімкнення сигналу “Control†РС4=1. Вимкнення сигналу “Control†РС4=0.
42237. Создание изображений с помощью Adobe Photoshop 941 KB
  Основное меню расположенное в верхней части окна позволяет выбирать все команды программы Photoshop. Пункт Параметры в меню Окно Window позволяет включить или отключить вывод панели активных инструментов на экран. Состав палитр отображаемых в рабочем окне указывается с помощью команды Окно Window основного меню программы Photoshop. Инструментальная панель PhotoShop Можно выбрать нужный инструмент либо щелкнув мышью на его значке в панели инструментов либо перетащив курсор мыши на его значок в значке в панели инструментов либо...
42238. Работа с векторной графикой в Adobe Photoshop 448.5 KB
  Кнопка для вывода оглавления Этапы создания кнопки: Создание нового рисунка размером 25090 пикселей с прозрачным фоном. Установка для инструмента Карандаш Pencil размера 9 пикселей. Зеркальный Линейный Зеркальный Зеркальный Линейный Зеркальный Зеркальный Угол 90 90 90 90 95 90 90 0 90 90 Масштаб 130 130 130 90 110 80 100 100 100 110 Дополнительные эффекты Обводка Размер: 2 пикс. Цвет: RGB255 0 0 Тень Цвет: RGB137 11 5 Смещение: 9 пикс.
42239. Создание анимационных изображений в Adobe Photoshop 781.5 KB
  На панели этого инструмента можно задать следующие опции: вид гарнитуру шрифта – ; стиль шрифта Regulr – обычный Itlic – курсив Bold – жирный Bold Itlic – жирный курсив – ; размер шрифта в пунктах – ; режим сглаживания для границ символов – ; режим выравнивания – выравнивание влево по центру или вправо; цвет текста – при щелчке по этому прямоугольнику открывается окно Палитра цветов в котором можно задать цвет текста ; деформация текста вывод текста по заданной кривой – ; включение выключение палитры символов...