Головна Головна -> Інше українською -> Інше -> Транспортна задача

Транспортна задача

Назва:
Транспортна задача
Тип:
Інше
Мова:
Українська
Розмiр:
10,65 KB
Завантажень:
131
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7 
Транспортна задача
Постановка транспортної задачі по критерію вартості перевозом.
Критерій роз рішимості транспортної задачі.
Властивості матриці умов транспортної задачі.
Нехай ми маємо m – пунктів в-ва , в яких зосереджено відповідно однорідного продукту. Цей продукт потрібно перевезти в n пунктів споживання , потреби яких відповідно рівні значимо через - в-ть перевезення одиниці товару з і пункту виробництва в j пункт споживання.
Через - товару, яку ми ??? з і пункту в-ва в j пункт споживання.
Постановимо задачу.
Організ. перевозу таким чином, щоб:
весь товар із пунктів в-ва був вивезений;
потреби всіх пунктів споживання були задоволені ;
вартість перевезення з усіх пунктів в-ва в усі пункти споживання були мінімальними.
Це є транспортна задача по критерію вартості перевезення.
Модель задачі.
Пункти спожив.
і їх по-Пун- треби
кти в-
ва і їх
спожи-
вачі | ... | ...
... | ...
|
| ...
... |
| ...
... |
|
| ...
... |
| ...
... |
... | ... | ...
... | ...
... | ...
... | ...
... | ...
... | ...
...
|
| ...
... |
| ...
... |
... | ... | ...
... | ...
... | ...
... | ...
... | ...
... | ...
...
|
| ...
... |
| ...
... |
... | ... | ...
... | ...
... | ...
... | ...
... | ...
... | ...
...
1-3 – це модель транспортної задачі по критерію вартості перевозок.
Умова 2’ означає, що весь товар із кожного з пунктів виробництва повинен бути вивезений, 2’ґ- що потреби кожного з пунктів споживання повинні бути задоволені.
Доведемо тепер критерій роз рішимості задачі покажемо, що необхідною і достатньою умовою для роз рішеності транспортної задачі є виконання умови 2
(2)
Умова 2 носить назву балансу мас.
Необхідність.
Нехай транспортна задача є розрішима. Покажемо, що для неї має місце баланс мас. Раз транспортна є розрішима, то по крайній мірі для неї існує набір , який задовольняє обмеження 1-3.
Просумуємо умови (2’) по всіх і, а умову (2’’) по всіх j
З рівності лівих частин слідує рівність правих частин, а це і є умова 2. Тим самим необхідність доведена.
Достатність.
Нехай для транспортної задачі виконується умова 2. Покажемо, що транспортна задача є розрішима.
область умов не є пуста;
ЛФ є обмеженою на множині своїх планів.
Покладемо , яка задовольняє .
умові 2’’ задовольняє.
умові 2’ задовольняє.
Отже 1) ми довели.
Покажемо, що ЛФ є обмеженою на ??? на множині своїх планів.
Тим самим ми показали, що умова 2 є достатньою умовою для того, щоб транспортна задача була розрішима.
Однак на практиці при роз взуванні реальних виробничих задач умова 2 рідко виконується. Ті транспортні задачі, для яких умова 2 виконується, називаються транспортними задачами з замкнутими моделями.
А ті транспортні задачі, для яких баланс мас не виконується називаються задачами з відкритими моделями.
Покажемо, що ??? можна перейти від одної моделі, для якої баланс мас виконується.
а)
б)
У випадку а) вводять неіснуючий пункт споживання.
а вартість перевозки з усіх пункті виробництва у пункт споживання рівний 0.
У випадку б) вводять неіснуючі пункти виробництва m+1, запаси якого рівні , а вартість перевозки з даного пункту виробництва у пункт споживання .
В-ті матриці умов транспортної задачі.
Покладемо m=3, n=4.
(2’)
(2’’)
Тоді матриця прийме вигляд
Ранг матриці умов транспортної задачі ніколи не може бути рівний m+n.
Нам треба показати, що є залежні лінійні стрічки.
Щоб довести цю властивість зафіксуємо m+1 рядок матриці умов, і всі решта умови другої частини матриці додамо до нього.
Від одержаного таким чином рядка віднімемо всі рядки першої частини матриці крім першого. Ми одержимо матрицю, в якої 1 і m+1 рядки будуть однакові. елементарні перетворення матриці не міняють ранг матриці, а так як ранг одержаної внаслідок елементарних перетворень матриці не буде рівний m+1, то і ранг вихідної матриці не дорівнює m+1.
Щоб довести другу властивість достатньо серед елементів матриці А знайти хоча б один визначник (m+n) – 1 порядку, який не дорівнює 0.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7 



Інше на тему: Транспортна задача

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок