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

Постановка транспортної задачі по критерію вартості перевозом.

Критерій роз рішимості транспортної задачі.

Властивості матриці умов транспортної задачі.

Нехай ми маємо 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.

Для нашого конкретного прикладу ми візьмемо всі рядки крім m+1 і за стовпці.

ранг цієї матриці .

Властивість 3.

Будь-який мінор матриці А завжди рівний 0;.

Доведемо це твердження методом мат. індукцій. Допустимо, що дане твердження вірне для ???

.

Структура матриці умов транспортної задачі такою, що будь-який мінор к-того порядку буде включати в себе: а) хоча б один стовпець, що складається з самих нулів; б) хоча б один стовпець, що всі 0 і одна 1; в) хоча б один стовпець, що містить рівно 2 одинички.

а) – у цьому випадку виходячи з властивостей визначників мінор k-того порядку рівні 0.

б) – у цьому випадку ми розкладаємо мінор k-того порядку по елементах стовпця, що містить рівно одну 1. , i+j – місце, де стоїть 1.

в) – виходячи із структури матриці А одна одиничка буде належати до однієї частини матриці, а інша – до другої.

Зафіксуємо тоді рядки, в яких стоїть 1 і в І і ІІ частинах матриці, і до них додамо всі решта рядки відповідно І і ІІ частини матриці. Внаслідок цього ми одержимо мінор k-того порядку, в якому буде 2 однакові рядки, а тоді .

Властивість доведена.

Використовуючи властивості умов транспортної задачі, можемо показати, що розв’язки задачі є завжди цілочисельні.

Область умов транспортної задачі Ах=В.

х – матриці розв’язків.

В – стовпець вільних членів.

Розв’яжемо Ах=В методом Крамера, тоді розв’язки системи можемо записати так

Тепер розкладемо по елементах стовпця ij.

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

Методи побудови початкового базисного плану