Головна
Банківська справа  |  БЖД  |  Біографії  |  Біологія  |  Біохімія  |  Ботаніка та с/г  |  Будівництво  |  Військова кафедра  |  Географія  |  Геологія  |  Екологія  |  Економіка  |  Етика  |  Журналістика  |  Історія техніки  |  Історія  |  Комунікації  |  Кулінарія  |  Культурологія  |  Література  |  Маркетинг  |  Математика  |  Медицина  |  Менеджмент  |  Мистецтво  |  Моделювання  |  Музика  |  Наука і техніка  |  Педагогіка  |  Підприємництво  |  Політекономія  |  Промисловість  |  Психологія, педагогіка  |  Психологія  |  Радіоелектроніка  |  Реклама  |  Релігія  |  Різне  |  Сексологія  |  Соціологія  |  Спорт  |  Технологія  |  Транспорт  |  Фізика  |  Філософія  |  Фінанси  |  Фінансові науки  |  Хімія

Транспортна задача - Економіко-математичне моделювання

Недержавні освітні установи

СЕРЕДНЬОГО ОСВІТИ

"ЕКОНОМІКО-КОМП'ЮТЕРНИЙ ТЕХНІКУМ"

ГРАФІЧНА Курсова робота

з дисципліни: "Математичні методи"

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

Виконав:

студент 4-го курсу групи 08-1 (п)

Лагутін Р.І.

Керівник: Ходаковська Т.Ю.

Курськ - 2010

Завдання

Цілі роботи: вивчити методи вирішення транспортної задачі та їх реалізацію при вирішенні практичного завдання.

Завдання:

1. Розглянути поняття транспортної задачі, її типи.

2. Розглянути різні методи вирішення транспортної задачі.

3. Побудувати перший опорний план даної транспортної задачі двома різними методами.

4. Знайти оптимальний план перевезень даної задачі методом потенціалів.

5. Вирішити дану задачу з використанням MS Excel (привести опис рішення).

6. Складіть комп'ютерну програму з вирішення завдань даного типу (привести опис програми, прикласти програму в електронному вигляді).

Варіант 4.1.

На чотирьох складах фірми знаходиться 70, 30, 40 і 60 холодильників відповідно, які слід доставити в чотири магазини фірми в кількості 50, 70, 40 і 40 холодильників в кожен з магазинів. Вартості перевезення одного холодильника з першого складу в кожен з магазинів складають 6, 4, 9 і 7 грошових одиниць відповідно, з другого складу - 7, 2, 5 і 6 грошових одиниць, з третього складу - 2, 6, 3 і 3 грошових одиниць , з четвертого складу - 3, 3, 6 і 5 грошових одиниць відповідно. Визначити план перевезень холодильників зі складів в магазини, при якому загальні витрати на перевезення були б найменшими.

Зміст

Завдання

Введення

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

Математична модель

Опорний план

Розподільний метод оптимального плану

Рішення транспортної задачі методом потенціалів

Всякий потенційний план є оптимальним

Висновок

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

Введення

Кожна людина щодня, не завжди усвідомлюючи це, вирішує проблему: як отримати найбільший ефект, володіючи обмеженими засобами. Наші засоби і ресурси завжди обмежені. Життя було б менш цікавою, якби це було не так. Не важко виграти бій, маючи армію в 10 разів більшу, ніж у супротивника. Щоб досягти найбільшого ефекту, маючи обмежені кошти, треба скласти план, або програму дій. Раніше план в таких випадках складався "на око". У середині XX століття був створений спеціальний математичний апарат, що допомагає це робити "по науці". Відповідний розділ математики називається математичним програмуванням. Слово "програмування" тут і в аналогічних термінах ("лінійне програмування, динамічне програмування" тощо) зобов'язане почасти історичного непорозуміння, почасти неточному перекладу з англійської. По-русски краще було б вжити слово "планування". З програмуванням для ЕОМ математичне програмування має лише те загальне, що більшість виникаючих на практиці задач математичного програмування занадто громіздкі для ручного рахунку, вирішити їх можна тільки за допомогою ЕОМ, попередньо склавши програму. Часом народження лінійного програмування прийнято вважати 1939, коли була надрукована брошура Леоніда Віталійовича Канторовича "Математичні методи організації і планування виробництва".

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

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

Мета транспортної діяльності вважається досягнутою при виконанні шести умов:

1. потрібний товар;

2. необхідної якості;

3. в необхідній кількості доставлений;

4. в потрібний час;

5. в потрібне місце;

6. з мінімальними витратами.

Об'єктом вивчення є матеріальні і відповідні їм фінансові, інформаційні потоки, які супроводжують виробничо-комерційну діяльність.

У цій роботі будуть розглянуті поняття транспортної задачі, її типи, різні методи вирішення. Розв'язана задача за завданням 4.1 за допомогою MS Excel і прикладена комп'ютерна програма за рішенням завдання даного типу.

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

Лінійні транспортні завдання становлять особливий клас задач лінійного програмування. Завдання полягає в знаходженні такого плану перевезень продукції з m складів у пункт призначення n який, зажадав б мінімальних витрат. Якщо споживач j одержує одиницю продукції (по прямій дорозі) зі складу i, то виникають витрати Сij. Передбачається, що транспортні витрати пропорційні перевозиться кількості продукції, тобто перевезення k одиниць продукції викликає витрати k Сij.

Далі,

де aiесть кількість продукції, що знаходиться на складі i, і bj- потреба споживача j.

Зауваження.

1. Якщо сума запасів у пунктах відправлення перевищує суму поданих заявокто кількість продукції, равноеостается на складах. У цьому випадку ми введемо "фіктивного" споживача n +1 з потребностьюі покладемо транспортні витрати pi, n + 1равнимі 0 для всіх i.

2. Якщо сума поданих заявок перевищує готівкові запасито потреба не може бути покрита. Це завдання можна звести до звичайної транспортної задачі з правильним балансом, якщо ввести фіктивний пункт відправлення m + 1 з запасомі вартість перевезень з фіктивного пункту відправлення в усі пункти призначення прийняти рівним нулю.

 Математична модель

де xijколічество продукції, що поставляється зі складу i споживачеві j, а Сijіздержкі (вартість перевезень зі складу i споживачеві j).

 Опорний план

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

Умови транспортної задачі задані транспортної таблицею.

Таблиця № 1

 ПН

 ПО

 В 1

 У 2

 У 3

 В 4

 У 5

 Запаси

 а i

 А 1 10 8 5 6 9 48

 А 2 6 7 8 6 5 30

 А 3 8 7 10 8 7 27

 А 4 7 5 4 6 8 20

 Заявки

 b j 18 27 42 12 26 125

Будемо заповнювати таблицю перевезеннями поступово починаючи з лівої верхньої комірки ("північно-західного кута" таблиці). Будемо міркувати при цьому наступним чином. Пункт В1подал заявку на 18 одиниць вантажу. Задовольнимо цю заявку за рахунок запасу 48, наявного в пункті А1, і запишемо перевезення 18 в клітці (1,1). Після цього заявка пункту В1удовлетворена, а в пункті А1осталось ще 30 одиниць вантажу. Задовольнимо за рахунок них заявку пункту В2 (27 одиниць), запишемо 27 в клітці (1,2); решту 3 одиниці пункту А1назначім пункту В3. У складі заявки пункту В3осталісь незадоволеними 39 одиниць. З них 30 покриємо за рахунок пункту А2, ніж його запас буде вичерпаний, і ще 9 візьмемо з пункту А3. З решти 18 одиниць пункту А312 виділимо пункту В4; залишилися 6 одиниць призначимо пункту В5, що разом з усіма 20 одиницями пункту А4покроет його заявку. На цьому розподіл запасів закінчено; кожен пункт призначення отримав вантаж, відповідно до своєї заявки. Це виражається в тому, що сума перевезень в кожному рядку дорівнює відповідному запасу, а в стовпці - заявці.

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

Таблиця № 2

 ПН

 ПО

 В 1

 У 2

 У 3

 В 4

 У 5

 Запаси

 а i

 А 1

 10

 18

8

 27

5

 3 6 9 48

 А2 7 червня

8

 30 червня 30 травня

 А 3. 8 липня

 10

9

8

 12

7

 27 червня

 А 4 липня 5 4 6

8

 20 20

 Заявки

 b j 18 27 42 12 26 125

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

Інший спосіб - спосіб мінімальної вартості по рядку - заснований на тому, що ми розподіляємо продукцію від пункту Aiне в будь-який з пунктів Bj, а в той, до якого вартість перевезення мінімальна. Якщо в цьому пункті заявка повністю задоволена, то ми прибираємо його з розрахунків і знаходимо мінімальну вартість перевезення з решти пунктів Bj.Во всьому іншому цей метод схожий з методом північно-західного кута. В результаті, опорний план, складений способом мінімальної вартості по рядку виглядає, так як показано в таблиці № 3. При цьому методі може вийти, що вартості перевезень Cijі Cikот пункту Aiк пунктам Bj

і Bkравни. У цьому випадку, з економічної точки зору, вигідніше розподілити продукцію в той пункт, в якому заявка більше. Так, наприклад, у рядку 2: C21 = C24, але заявка b1больше заявки b4, тому 4 одиниці продукції ми розподілимо в клітину (2,1).

Таблиця № 3

 ПН

 ПО

 В 1

 У 2

 У 3

 В 4

 У 5

 Запаси

 а i

 А1 10 серпня

5

 42

6

 9 червня 48

 А 2

6

 4 Липень 8 червень

5

 26 30

 А 8 Березень

7

 27 10 Серпня

7

 0 27

 А 4

7

 14 5 квітень

6

 6 20 серпня

 Заявки

 b j 18 27 42 12 26 125

Спосіб мінімальної вартості по стовпцю аналогічний попередньому способу. Їх відмінність полягає в тому, що в другому способі ми розподіляємо продукцію від пунктів Biк пунктам Ajпо мінімальної вартості Cji.

Опорний план, складений способами мінімальних вартостей, зазвичай більш близький до оптимального рішення. Так у нашому прикладі загальні витрати на транспортування за планом, складеним першим способом F0 = 1039, а по друге F0 = 723. Клітини таблиці, в яких стоять ненульові перевезення, є базисними. Їх кількість має дорівнювати m + n - 1. Необхідно відзначити також, що зустрічаються такі ситуації, коли кількість базисних клітин менше ніж m + n - 1. У цьому випадку розподільна завдання називається виродженої. І слід в одній з вільних клітин поставити кількість перевезень рівне нулю. Так, наприклад, в таблиці № 3:

m + n - 1 = 4 + 5 - 1 = 8,

а базисних клітин 7, тому потрібно в одну з клітин рядки 3 або колонки 2 поставити значення "0". Наприклад в клітину (3,5). Складаючи план по способам мінімальних вартостей на відміну від плану за способом північно-західного кута ми враховуємо вартості перевезень Cij, але все ж не можемо стверджувати, що складений нами план є оптимальним.

 Розподільний метод оптимального плану

Тепер спробуємо поліпшити план, складений способом північно-західного кута. Перенесемо, наприклад, 18 одиниць з клітки (1,1) в клітину (2,1) і щоб не порушити балансу перенесемо ті ж 18 одиниць з клітки (2,3) в клітину (1,3). Отримаємо новий план. Підрахувавши вартість опорного плану (вона дорівнює 1039) і вартість нового плану (вона дорівнює 913) неважко переконатися, що вартість нового плану на 126 одиниць менше. Таким чином, за рахунок циклічної перестановки 18 одиниць вантажу з одних клітин в інші нам вдалося знизити вартість плану:

Таблиця №4

 ПН

 ПО

 В 1

 У 2

 У 3

 В 4

 У 5

 Запаси

 а i

 А 10 січня

8

 27

5

 21 9 червня 48

 А 2

6

 18 липня

8

 6 грудня 30 травня

 А 3. 8 липня

 10

9

8

 12

7

 27 червня

 А 4 липня 5 4 6

8

 20 20

 Заявки

 b j 18 27 42 12 26 125

На цьому способі зменшення вартості в подальшому і буде заснований алгоритм оптимізації плану перевезень. Циклом в транспортній задачі ми будемо називати кілька зайнятих клітин, з'єднаних замкнутою, ламаної лінією, яка в кожній клітині робить поворот на 90 °. Існує кілька варіантів циклу:

1.) 2.) 3.)

Неважко переконатися, що кожен цикл має парне число вершин і виходить, парне число ланок (стрілок). Домовимося відзначати знаком + ті вершини циклу, в яких перевезення необхідно збільшити, а знаком -, ті вершини, в яких перевезення необхідно зменшити. Цикл із зазначеними вершинами будемо називати зазначеним. Перенести якусь кількість одиниць вантажу по зазначеному циклу, це означає збільшити перевезення, що стоять в позитивних вершинах циклу, на це кількість одиниць, а перевезення, що стоять в негативних вершинах зменшити на ту ж кількість. Очевидно, при переносі будь-якого числа одиниць по циклу рівновагу між запасами і заявками не змінюється: по колишньому сума перевезень в кожному рядку дорівнює запасам цього рядка, а сума перевезень в кожному стовпці - заявці цього стовпця. Таким чином, при будь-якому циклічному перенесення, який полишає перевезення невід'ємними допустимий план залишається допустимим.

Вартість же плану при цьому може змінюватися: збільшуватися або зменшуватися. Назвемо ціною циклу збільшення вартості перевезень при переміщенні однієї одиниці вантажу по зазначеному циклу. Очевидно, ціна циклу рівна алгебраїчній сумі вартостей, які стоять у вершинах циклу, причому стоять в позитивних вершинах беруться зі знаком +, а в негативних зі знаком -. Позначимо ціну циклу через g.

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

Якщо циклів з негативною ціною в таблиці більше не залишилося, це означає, що подальше поліпшення плану неможливо, тобто оптимальний план досягнутий. Метод послідовного поліпшення плану перевезень і полягає в тому, що в таблиці відшукуються цикли з негативною ціною, за ним переміщуються перевезення, і план поліпшується до тих пір, поки циклів з негативною ціною вже не залишиться. При поліпшенні плану циклічними переносами, як правило, користуються прийомом, запозиченим з симплекс-методу: при кожному кроці (циклі) замінюють одну вільну змінну на базисну, тобто заповнюють одну вільну клітину і взамін того звільняють одну з базисних клітин. При цьому загальне число базисних клітин залишається незмінним і рівним m + n - 1. Цей метод зручний тим, що для нього легше знаходити відповідні цикли. Можна довести, що для будь-якої вільної клітці транспортної таблиці завжди існує цикл і притому єдиний, одна з вершин якого лежить в цій вільній клітці, а всі інші в базисних клітинах. Якщо ціна такого циклу, з плюсом у вільній клітці, негативна, то план можна поліпшити переміщенням перевезень за даним циклу. Кількість одиниць вантажу k, яке можна перемістити, визначається мінімальним значенням перевезень, що стоять в негативних вершинах циклу (якщо перемістити більше число одиниць вантажу, виникнуть негативні перевезення).

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

Розподільний метод вирішення транспортної задачі, з яким ми познайомилися, володіє одним недоліком: потрібно відшукувати цикли для всіх вільних клітин і знаходити їх ціни. Від цієї трудомісткої роботи нас позбавляє спеціальний метод вирішення транспортної задачі, який називається методом потенціалів.

 Рішення транспортної задачі методом потенціалів

Цей метод дозволяє автоматично виділяти цикли з негативною ціною і визначати їх ціни. Нехай є транспортна задача з балансовими умовами

Вартість перевезення одиниці вантажу з Aiв Bjравна Cij; таблиця вартостей задана. Потрібно знайти план перевезень xij, який удовлетворялби балансовим умов і при цьому вартість всіх перевезень биламінімальна.

Ідея методу потенціалів для вирішення транспортної задачі зводитися до наступного. Уявімо собі що кожен з пунктів відправлення Aiвносіт за перевезення одиниці вантажу (все одно куди) якусь суму ai; в свою чергу кожен з пунктів призначення Bjтакже вносить за перевезення вантажу (куди завгодно) суму bj. Ці платежі передаються деякого третій особі ("перевізнику"). Позначимо ai + bj = cij (i = 1. M; j = 1. N) і будемо називати величину cij "псевдостоімость" перевезення одиниці вантажу з Aiв Bj. Зауважимо, що платежі aiі bjне обов'язково повинні бути позитивними; не виключено, що "перевізник" сам платить того чи іншого пункту якусь премію за перевезення.

Також треба відзначити, що сумарна псевдостоімость будь-якого допустимого плану перевезень при заданих платежах (aiі bj) одна і та ж і від плану до плану не змінюється. До цих пір ми ніяк не пов'язували платежі (aiі bj) і псевдостоімость cijс істинними вартостями перевезень Cij. Тепер ми встановимо між ними зв'язок. Припустимо, що план xijневирожденний (число базисних клітин в таблиці перевезень рівно m + n - 1). Для всіх цих клітин xij> 0. Визначимо платежі (aiі bj) так, щоб у всіх базисних клітинах псевдостоімость були Рівне Вартість:

cij = ai + bj = сij, при xij> 0.

Що стосується вільних клітин (де xij = 0), то в них співвідношення між псевдостоімость і вартостями може бути, яке завгодно. Виявляється співвідношення між псевдостоімость і вартостями у вільних клітинах показує, чи є план оптимальним або ж він може бути поліпшений. Існує спеціальна теорема: Якщо для всіх базисних клітин плану xij> 0, ai + bj = cij = сij, а для всіх вільних клітин xij = 0, ai + bj = cij? сij, то план є оптимальним і ніякими способами поліпшений бути не може. Неважко показати, що це теорема справедлива також для виродженого плану, і деякі з базисних змінних дорівнюють нулю. План володіє властивістю:

cij = сij (для всіх базисних клітин) (1)

cij? сij (для всіх вільних клітин) (2)

називається потенційним планом, а відповідні йому платежі (aiі bj) - потенціалами пунктів Aiі Bj (i = 1,., m; j = 1,., n).

Користуючись цією термінологією вищезгадану теорему можна сформулювати так:

 Всякий потенційний план є оптимальним

Отже, для вирішення транспортної задачі нам потрібно одне - побудувати потенційний план. Виявляється його можна побудувати методом послідовних наближень, задаючись спочатку якийсь довільній системою платежів, що задовольняє умові (1). При цьому в кожній базисної клітці вийти сума платежів, рівна вартості перевезень в даній клітині; потім, поліпшуючи план слід одночасно змінювати систему платежів. Так, що вони наближаються до потенціалом. При поліпшенні плану нам допомагає наступне властивість платежів і псевдостоімость: яка б не була система платежів (aiі bj) задовольняє умові (1), для кожної вільної клітини ціна циклу перерахунку дорівнює різниці між вартістю і псевдостоімость в даній клітині: gi, j = сi, j- ci, j.

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

Процедура побудови потенційного (оптимального) плану полягає в наступному. В якості першого наближення до оптимального плану береться будь допустимий план (наприклад, побудований способом мінімальної вартості по рядку). У цьому плані m + n - 1 базисних клітин, де m - число рядків, n - число стовпців транспортної таблиці. Для цього плану можна визначити платежі (aiі bj), так, щоб у кожній базисної клітці виконувалася умова: ai + bj = сij (3)

Рівнянь всього m + n - 1, а число невідомих дорівнює m + n. Отже, одну з цих невідомих можна задати довільно (наприклад, рівною нулю). Після цього з m + n - 1 рівнянь можна знайти інші платежі ai, bj, а по них обчислити псевдостоімость, ci, j = ai + bjдля кожної вільної клітини.

Таблиця №5

 ПН / ПО

 В 1

 У 2

 У 3

 В 4

 У 5

 a i

 А 1

 10

 c = 7

8

 c = 6

5

 42

6

6

9

 c = 6

 a 1 = 0

 А 2

6

4

7

 c = 5

8

 c = 4

6

 c = 5

5

 26

 a 2 = - 1

 А 3

8

 c = 8

7

 27

 10

 c = 6

8

 c = 7

7

0

 a 3 = 1

 А 4

7

 14

5

 c = 6

4

 c = 5

6

6

8

 c = 6

 a 4 = 0

 b j

 b 1 = 7

 b 2 = 6

 b 3 = 5

 b 4 = 6

 b 5 = 6

a4 = 0, ®

b4 = 6, так як a4 + b4 = С44 = 6, ®

a1 = 0, так як a1 + b4 = С14 = 6, ®

b3 = 5, так як a1 + b3 = С13 = 5, ®

b1 = 7, так як a4 + b1 = С41 = 7, ®

a2 = - 1, так як a2 + b1 = С21 = 6, ®

b5 = 6, так як a2 + b5 = С25 = 5, ®

a3 = 1, так як a3 + b5 = С35 = 7, ®

b2 = 6, так як a3 + b2 = С25 = 7.

Якщо виявилося, що всі ці псевдостоімость не перевищують вартостей cij ? сij, ? ? то план потенціалом і, значить, оптимальний. Якщо ж хоча б в одній вільній клітці псевдостоімость більше вартості (як у нашому прикладі), то план не є оптимальним і може бути поліпшений переносом перевезень по циклу, відповідному даної вільної клітині. Ціна цього циклу рівна різниці між вартістю і псевдостоімость в цій вільній клітці. У таблиці № 5 ми отримали в двох клітках cij? сij, тепер можна побудувати цикл в будь-який з цих двох клітин. Найвигідніше будувати цикл в тій клітці, в якій різниця cij- сijмаксімальна. У нашому випадку в обох клітинах різниця однакова (дорівнює 1), тому, для побудови циклу виберемо, наприклад, клітину (4,2):

Таблиця №6

 ПН

 ПО

 В 1

 У 2

 У 3

 В 4

 У 5

 a i

 А1 10 серпня

5

 42

6

 9 червня 0

 А 2

 6 +

 4 Липень 8 6

 5 -

 26 -1

 А 8 Березень

 7 -

 27 10 Серпня

 7 +

 0 1

 А 4

 7 -

 14

 5 +

 u 4

6

 8 червні 0

 b j 7 6 5 6 червня

Тепер будемо переміщати по циклу число 14, так як воно є мінімальним з чисел, що стоять в клітинах, позначених знаком -. При переміщенні ми будемо віднімати 14 з клітин зі знаком - і додавати до клітин зі знаком +. Після цього необхідно підрахувати потенціали aiі bjі цикл розрахунків повторюється.

Отже, ми приходимо до наступного алгоритму вирішення транспортної задачі методом потенціалів.

1. Взяти будь опорний план перевезень, в якому відзначені m + n - 1 базисних клітин (інші клітини вільні).

2. Визначити для цього плану платежі (aiі bj) виходячи з умови, щоб у будь базисної клеткепсевдостоімості були рівні вартостям. Один з платежів можна назначітьпроізвольно, наприклад, покласти рівним нулю.

3. Підрахувати псевдостоімость ci, j = ai + bjдля всіх вільних клітин. Якщо виявиться, що всі вони не перевищують вартостей, то план оптимальний.

4. Якщо хоча б в одній вільній клітці псевдостоімость перевищує вартість, слід приступити до поліпшення плану шляхом перекидання перевезень по циклу, відповідному будь-якої вільної клітці з негативною ціною (для якої псевдостоімость більше вартості).

5. Після цього заново підраховуються платежі і псевдостоімость, і, якщо план ще не оптимальний, процедура поліпшення продовжується до тих пір, поки не буде знайдений оптимальний план. Так у нашому прикладі після 2 циклів розрахунків отримаємо оптимальний план. При цьому вартість всього перевезення змінювалася наступним чином: F0 = 723, F1 = 709, F2 = Fmin = 703.

Слід відзначити також, що оптимальний план може мати й інший вигляд, але його вартість залишиться такою ж Fmin = 703.

Складіть оптимальний план перевезення вугілля з мінімальними транспортними витратами з шахт Варгашорская (В), Західна (З) і Комсомольська (К), щотижня видобувних відповідно 26,32 і 17тис. т. Покупці вугілля розташовані в різних містах В, В, С і D, заявки яких становлять 28, 19, 12 і 16 тис. т між постачальниками і споживачами представлені транспортної таблицею.

 Шахти Споживачі

 Видобуток вугілля,

 тис. тонн в тиждень

 A B C D

 Західна 70 76 72 68 32

 Варгашорская 80 84 82 77 26

 Комсомольська 80 83 82 76 17

 Заявки, тис. Тонн 28 19 16 грудня

Рішення:

Математична модель даної задачі має вигляд:

F = 70х11 + 76х12 + 72х13 + 68х14 + 80х21 + 84х22 + 82х23 + 77х24 + 80х9 + 83х10 + 82х11 + 76х12 > min

Екранна форма для введення умов завдання разом з введеними в неї вихідними даними представлена на малюнку:

При введенні залежностей лист MS Excel в режимі перегляду формул має вигляд:

Після відбиття закономірностей екранна форма приймає вигляд:

Вікно "Пошук рішення" після введення всіх необхідних даних завдання має наступний вигляд:

Оптимальне рішення задачі в екранній формі має вигляд:

Мінімальні транспортні витрати на перевезення вугілля дорівнюють 5715.

Висновок

У курсовій роботі викладені основні підходи та методи вирішення транспортної задачі, що є однією з найбільш поширених задач лінійного програмування. Рішення даної задачі дозволяє розробити найбільш раціональні шляхи і способи транспортування товарів, усунути надмірно далекі, зустрічні, повторні перевезення. Все це скорочує час просування товарів, зменшує витрати підприємств і фірм, пов'язані зі здійсненням процесів постачання сировиною, матеріалами, паливом, обладнанням і т.д.

Алгоритм і методи вирішення транспортної задачі можуть бути використані при вирішенні деяких економічних завдань, які не мають нічого спільного з транспортуванням вантажу. У цьому випадку величини тарифів cij мають різний зміст залежно від конкретної економічної задачі. До таких завдань належать такі: оптимальне закріплення за верстатами операцій з обробки деталей. У них cij є таким економічним показником, як продуктивність. Завдання дозволяє визначити, скільки часу і на якій операції потрібно використовувати кожен з верстатів, щоб обробити максимальну кількість деталей. Так як транспортна задача вимагає знаходження мінімуму, то значення cij беруться з негативним знаком; оптимальні призначення, або проблема вибору. Мається m механізмів, які можуть виконувати m різних робіт з продуктивністю cij. Завдання дозволяє визначити, який механізм і на яку роботу треба призначити, щоб домогтися максимальної продуктивності; задача про скорочення виробництва з урахуванням сумарних витрат на виготовлення і транспортування продукції; збільшення продуктивності автомобільного транспорту за рахунок мінімізації порожнього пробігу. Зменшення порожнього пробігу скоротить кількість автомобілів для перевезень, збільшивши їх продуктивність; рішення задач за допомогою методу заборони перевезень. Використовується в тому випадку, якщо вантаж від деякого постачальника з якихось причин не може бути відправлений одному із споживачів. Дане обмеження можна врахувати, присвоївши відповідній клітині достатньо велике значення вартості, тим самим в цю клітку не будуть робитися перевезення. Таким чином, важливість вирішення даного завдання для економіки безсумнівна. Приємно усвідомлювати, що у витоків створення теорії лінійного програмування і рішення, в тому числі і транспортної задачі, стояв російський учений - Леонід Віталійович Канторович.

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

1. Єрьомін І.І., Астаф'єв М.М. Введення в теорію лінійного і опуклого програмування М .; Наука, 1976

2. Карманов В.Г. Математичне програмування. - М .; Наука, 1986р.

3. Моїсеєв Н.Н., Іванов Ю.П., Столярова Е.М. Методи оптимізації. - М .; Наука, 1978р.

4. Іванов Ю.П., Лотів А.В. Математичні моделі в економіці. - М .; Наука, 1979р.

5. Бронштейн І.М., Семендяев К.А. Довідник з математики. - М .; Наука, 1986р
Методика обробки експериментальних даних
Завдання на курсову роботу 1. Побудувати варіаційний ряд 2. Розрахувати числові характеристики статистичного ряду: а) Розмах варіювання. б) Середнє арифметичне значення. в) Оцінки дисперсії. г) Оцінки середньоквадратичного відхилення. д) Мода. е) Медіана. ж) Коефіцієнт варіації. 3. Побудувати

Початок руху і зміна його напряму
Дніпропетровський державний університет внутрішніх справ Кафедра «Тактіко-спеціальної підготовки» Реферат по дисципліні Автомобільна підготовка" на тему: «Початок руху і зміна його напряму» Виконав: курсант 303 у.г. рядової міліції Мартиненко Д.О. Перевірив: викладач «Автомобільної

Лікувальна фізична культура в третьому триместре вагітності
Міністерство освіти Російської Федерації Іркутський Державний Технічний Університет Кафедра фізичної культури Реферат «ЛФК в третьому триместре вагітності» Іркутськ 2007 Зміст 1. Лікувальна фізкультура для вагітних 2. Свідчення і протипоказання по виконанню вправ 3. Основні принципи заняття

Взаємозамінність зубчастих коліс і передач
Взаємозамінність зубчастих коліс і передач ВСТУП Зубчасті передачі широко застосовують в машинах, пристроях, механізмах, приладах і т.д. З експлуатаційного призначенням та зубчасті передачі ділять на кілька основних груп: відлікові, швидкісні, силові та загального призначення. До відліковим

Рульове управління автомобіля КамАЗ-5320 і трактора МТЗ-80 з гідропідсилювачем
Зміст Введення 1.Призначення і загальна характеристика рульового керування автомобіля КамАЗ - 5320 і колісного трактора МТЗ - 80 з гідропідсилювачем 2.Устройство і робота рульового керування автомобіля КамАЗ - 5320 і колісного трактора МТЗ - 80 3.Основні регулювання рульового управління 4.Возможность

Технологічний процес роботи дільничної станції
КУРСОВИЙ ПРОЕКТ по предмету: Організація руху на тему: Технологічний процес роботи дільничної станції Студентка Сурміна Ганна Олексіївна ГруппаД - 511 ШіфрД-05-11 / М-29 РуководітельІванова Л. І. ЗМІСТ Введення 1. Загальні питання роботи станції 2. Оперативне керівництво і планування роботи

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

© 2014-2022  8ref.com - українські реферати