Реферати українською » Экономико-математическое моделирование » Математична постановка транспортної завдання лінійного програмування


Реферат Математична постановка транспортної завдання лінійного програмування

Зміст

 

Запровадження 2

1. Постановка завдання й її математична модель 3

2. Моделі транспортної завдання 7

2.1. Закрита модель транспортної завдання 7

2.2. Відкрита модель транспортної завдання 8

3. Визначення оптимального і опорного плану транспортної завдання 10

4. Методи визначення початкового опорного плану 12

4.1. Метод мінімального елемента 12

4.2. Метод апроксимації Фогеля 14

5. Методи визначення оптимального плану 16

5.1. Угорський метод 16

5.2. Метод потенціалів 17

Список використаної літератури 19

 


Запровадження

 

Транспортна завдання лінійного програмування отримало час стала вельми поширеною в теоретичних обробках і практичне застосування на транспорті, і у промисловості. Особливо важливого значення вона не має у справі раціоналізації постановок найважливіших видів промислової та сільськогосподарської продукції, і навіть оптимального планування вантажопотоків й досвід роботи різних видів транспорту.

З іншого боку, до завдань транспортного типу зводяться багатьох інших завдання лінійного програмування - завдання про призначення, мережні, календарного планування.

         Мета заданої роботи - освоїти математичну постановку транспортної завдання лінійного програмування.

 

1. Постановка завдання й її математична модель

Транспортна завдання є приватною типом завдання лінійного програмування і формулюється так. Є m пунктів відправлення (чи пунктів виробництва) Аі …, Аm, у яких зосереджені запаси однорідних продуктів у кількості a1, ..., аm одиниць. Є n пунктів призначення (чи пунктів споживання) У1, ..., Уm, потреба що у зазначених продуктах становить b1, ..., bn одиниць. Відомі також транспортні витрати Зij, пов'язані в перевезенні одиниці продукту із Aі до пункту Уj, і 1, …, m; j 1, ..., n. Припустимо, що

          

т. е. загальний обсяги виробництва дорівнює загального обсягу споживання. Потрібна скласти такий план перевезень (звідки, куди й скільки одиниць продукту везти), щоб задовольнити попит всіх пунктів споживання з допомогою реалізації всього продукту, виробленого усіма пунктами виробництва, при мінімальної загальної вартості всіх перевезень. Наведена формулювання транспортної завдання називається замкнутої транспортної моделлю. Формализуем це завдання.

Нехай xij - кількість одиниць продукту, поставленого із Аі до пункту Уj. Подлежащие мінімізації сумарні видатки перевезення продуктів із всіх пунктів виробництва в усі пункти споживання виражаються формулою:

             (1)

Сумарна кількість продукту, спрямовуваного з кожного пункту відправлення в усі пункти призначення, має бути одно запасу продукту даному пункті. Формально це, що

, і 1, …, m (2)

Сумарна кількість вантажу, доставляемого у кожний пункт призначення із усіх пунктів відправлення, має бути одно потреби. Це умова задоволення попиту:

, j 1, …, n (3)

Обсяги перевезень - неотрицательные числа, оскільки перевезення з пунктів споживання пункти виробництва виключені:

xij 0, і 1, ..., m; j 1, ..., n (4)

Транспортна завдання зводиться, в такий спосіб, до мінімізації сумарних витрат і під час умов задоволення від попиту й рівності вывозимого кількості продукту запасам їх у пунктах відправлення.

Визначення 1.

Будь-яке ненегативне рішення системи лінійних рівнянь

, j 1, …, n і , і 1, …, m,

обумовлений матрицею X=(xij)(і 1, …, m; j 1, ..., n), називається планом транспортної завдання.

 

Визначення 2.

План X*=(x*ij)(і 1, …, m; j 1, ..., n), у якому функція

 

приймає своє мінімальне значення, називається оптимальним планом транспортної завдання.

Зазвичай вихідні дані записуються як таблиці 1.

Таблиця 1.

Пункти відправлення Пункти призначення Запаси

У1

Bj

Bn

А1

A1

З11

X11

З1j

X1j

З1n

X1n

a1

Aі

Зi1

Xi1

Зij

Xij

Зin

Xin

aі

Am

Зm1

Xm1

Зmj

Xmj

Зmn

Xmn

am

Потреби

b1

bj

bn

Вочевидь, загальне наявність вантажу в постачальників одно , а загальна потреба у вантаж в пунктах призначення дорівнює одиниці. Якщо загальна потреба у вантаж в пунктах призначення дорівнює запасу вантажу на пунктах відправлення, тобто.

,          (5)

то модель такою транспортною завдання називається закритою.

Нерідко непотрібен, щоб весь вироблений продукт у кожному пункті виробництва реалізували. У разі баланс виробництва та споживання може бути порушений:

, і 1, ..., m.

Запровадження його запровадження призводить до відкритої транспортної моделі.

Теорему 1.

Будь-яка транспортна завдання, що має сумарний обсяг запасів збігаються з сумарним обсягом потреб, має рішення.


2. Моделі транспортної завдання

2.1. Закрита модель транспортної завдання

 

Аби довести теореми необхідно показати, що з заданих умовах існує хоча б тільки план завдання й лінійна функція на безлічі планів обмежена.

Доказ. Нехай   = M > 0. 

Тоді величини  xij = aіbj /M (і = 1,2,3, ... m; j = 1,2,3, ..., n) є планом, оскільки вони задовольняють системі обмежень

 ( 2 ) і ( 3 ) .

 Справді, підставляючи значення (2) і (3) , знаходимо

     = aі ,

     = bj .

Выберем з значень  Зij  найбільше C

Схожі реферати:

Навігація