Курсова робота: Транспортна задача і її розв’язування засобами Microsoft Excel

План

Вступ     3

1. Поява транспортної задачі     4

2. Транспортна задача    8

3. Транспортна задача за критерієм вартості    10

3.1. Закрита модель транспортної задачі    10

3.2. Відкрита модель транспортної задачі    14

4. Транспортна задача за критерієм часу    11

5. Приклад розв’язування транспортної задачі    18

5.1. Аналітичне розв’язування задачі    18

5.2. Розв’язування задачі за допомогою Excel    21

Висновки    27

Література    29

Вступ

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

Зараз слово “Оптимізація” на вустах у багатьох користувачів персональних комп’ютерів. Ми оптимізуємо все що можна: від графічних файлів до операційних систем. Але мало хто замислюється над тим що проблема пошуку найкращого рішення не менш гостро поставлена й в економіці.

Першу в історії оптимізаційну задачу сформулював Леонардо Фібоначчі, італійський математик XIII століття. Його задача “Про гирі” присвячена проблемі зважування за допомогою важільних ваг і створення оптимальної системи гир для цієї мети. У Новий Час у зв’язку зі зміцненням позицій капіталізму, зародженням банківської системи, ростом міст і мануфактур проблема пошуку оптимальних рішень стала дуже актуальною. І вже в XVIII столітті були закладені математичні основи оптимізації: варіаційне числення, чисельні методи й ін. Однак багато з розроблених алгоритмів було дуже складно реалізувати на практиці, і тільки з появою ЕОМ, що володіють великою обчислювальною потужністю, вдалося вирішити великий комплекс оптимізаційних завдань. До теперішнього часу накопичений величезний досвід рішення подібного класу завдань як для конкретних додатків, так й в узагальненому виді.

Дана робота присвячена знайомству з однією з найбільш популярних економіко-математичних моделей – транспортній задачі.

1. Поява транспортної задачі

Перші задачі геометричного змісту, пов’язані з відшуканням найменших і найбільших величин, з’явились ще в древні часи. Розвиток промисловості в 17-18 століттях призвів до необхідності дослідження більш складних задач на екстремум і до появи варіаційного числення. Однак лише в 20 столітті при величезному розмаху виробництва й усвідомленню обмеженості ресурсів Землі постала задача оптимального використання енергії, матеріалів, робочого часу. Великої актуальності набули питання найкращого в тому чи іншому змісті керування різними процесами фізики, техніки, економіки й ін. Сюди відносяться, наприклад, задача організації виробництва з метою одержання максимального прибутку при заданих витратах ресурсів, задача керування системою гідростанцій і водоймищ з метою одержання максимальної кількості електроенергії, задача про найшвидше нагрівання, або охолодження металу до заданого температурного режиму, задача про найкраще гасіння вібрацій і багато інших задач.

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

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

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

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

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

Важливий внесок щодо розв’язання цих проблем зробив видатний математик академік Л.В.Канторович. У своїй роботі “Математичні методи організації і планування виробництва”, яка була опублікована в 1939 році, він розробив метод для розв’язання транспортної задачі, яка на сьогодні є однією з основних, а також тою, що потребує розв’язування чи не щодня в різних галузях народного господарства.

Вивчення транспортних задач має виключно практичне значення, так, як, по-перше, дозволяє знизити транспортні витрати конкретного підприємства на 10-30 %, а по-друге, велику кількість інших прикладних задач можна описати математичними моделями, що є подібні до моделей транспортних задач.

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

Спеціальні методи застосовуються для розв’язування окремих класів задач лінійного програмування. Вони, як правило, простіші ніж універсальні, але застосовуються не для всіх задач. До спеціальних методів відносяться методи розв’язування транспортної задачі, що враховують специфіку її обмежень:

  • всі обмеження задані у вигляді рівнянь;
  • кожна змінна входить лише в два рівняння;
  • коефіцієнти при змінних – одиниці.

    Серед цих методів найбільш відомі наступні:

  1. Розподільчий метод;
  2. Модифікований розподільчий метод (він же метод потенціалів), запропонований Л.В.Канторовичем та М.К.Гавуріним, а згодом, незалежно від них, Дж. Данцігом;
  3. Венгерський метод, запропонований Е. Егерварі і удосконалений Х. Куном для розв’язування окремого випадку транспортної задачі: задачі про призначення (або про вибір), а пізніше узагальнений Дж. Манкресом на транспортну задачу загального виду;
  4. Метод диференціальних рент А. Л. Брудно;

    Для розв’язання питань спеціалізації виробництва часто доводиться розв’язувати таку задачу:

  • є ряд різноманітних підприємств або цехів;
  • відома виробнича потужність кожного з цих підприємств або цехів;
  • є ряд інших підприємств або цехів, що споживають продукцію перших підприємств (цехів), тобто є споживачі.

    Треба визначити:

  • скільки продукції та якої номенклатури необхідно виготовляти на кожному підприємстві-виробнику, щоб найефективніше задовольнити попит споживачів?
  • скільки продукції кожного підприємства або цеху необхідно доставити кожному підприємству-споживачеві, щоб дістати найкращий економічний ефект?

    Аналогічна задача:

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

    Визначити скільки з кожного пункту відправника необхідно направити вантажу в кожний пункт призначення, щоб транспортні витрати були найменшими (Транспортна задача за критерієм вартості).

    За наявності товарів, що швидко псуються, або виходячи з деяких інших міркувань (наприклад під час війни), треба всі вантажі з пунктів відправлення доставити в пункти призначення за мінімально короткий термін, не враховуючи транспортні витрати (Транспортна задача за критерієм часу).

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

     

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

    Найпростіше формулювання транспортної задачі за критерієм вартості звучить наступним чином:

    В m пунктах відправлення знаходиться, відповідно, a1, a2,…am одиниць однорідного вантажу, який повинен бути доставлений в n заданих пунктів призначення (споживання), відповідно, в кількостях b1, b2,… bn одиниць. Нехай вартість перевезення одиниці вантажу з і – го пункту відправлення в j -й пункт призначення рівна Gij, а відповідна кількість одиниць перевезеного вантажу рівна xij (i=1, …m ; j = 1, … n).

    Потрібно спроектувати такий план перевезень, при якому їх загальна вартість буде мінімальна, тобто треба вказати, скільки одиниць вантажу повинно бути відправлено з довільного і – го пункту відправлення в будь-який j – тий пункт призначення – так, щоб максимально задовольнити потреби і щоб сумарні затрати на перевезення були мінімальні.

    Матриці, утворені значеннями змінних хij і коефіцієнтами Gij, називаються, відповідно, планом перевезень і матрицею транспортних затрат.

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

    ,                       (1)

    а в відкритій моделі порушений баланс між сумарними ресурсами і потребами:

       ;    (2)

      .     (3)

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

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

  1. Рівність (1) являється необхідною і достатньою умовою сумісності транспортної задачі;
  2. Будь-яка транспортна задача має оптимальний план;
  3. Якщо величини аі і bj є цілими числами, то і всі значення змінних хіj в оптимальному плані будуть цілими величинами.

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

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

    Для розв’язування транспортної задачі були створені спеціальні методи, зокрема розподільний метод, метод потенціалів або модифікований розподільний метод (скорочено “Моді”). За допомогою цих методів можна розв’язувати також інші задачі, такі як планування матеріально-технічного постачання, визначення оптимального варіанта завантаження верстатів тощо.

    3. Транспортна задача за критерієм вартості

    Розглянемо транспортну задачу, яку називають транспортною задачею за критерієм вартості. Формулюють її так:

    У даних m пунктах-відправниках А1, А2, …, Аm є відповідно a1, a2,…am одиниць однорідного вантажу. Цей вантаж треба перевезти в n пунктів призначення В1, В2,…, Вn. При цьому в кожний пункт призначення необхідно доставити відповідно b1, b2,… bn одиниць вантажу.

    3.1. Закрита модель транспортної задачі

    Передбачається, що обов’язково виконується умова: загальна кількість вантажів у всіх пунктах-відправниках повинна дорівнювати загальній сумі вантажів у пунктах призначення, тобто виконується рівність (1).

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

    Позначимо через xij (i=1, …m ; j = 1, … n) кількість одиниць вантажу, що відправляється з і-го пункту в j-й пункт. У подальшому іноді будемо називати пункти відправлення постачальниками, кількості вантажів, що є в кожному з них – їхніми потужностями, а пункти призначення та кількості одиниць вантажів, які необхідно в них доставити, споживачами та їхнім попитом.

    Запишемо умови задачі у вигляді таблиці

    Постачальник і його запаси Споживач і його попит B1 B2 … Bj … Bn b1 b2 … bj … bn A1 a1 c11 x11 c12 x12 … c1j x1j … cmn xmn А2 a2 c21 x21 c22 x22 … c2j x2j … c2n x2n … … … … … … … … Аі ai ci1 xi1 ci2 xi2 … cij xij … cin xin … … … … … … … … Аm am cm1 xm1 cm2 xm2 … cmj xmj … cmn xmn

    Як бачимо, дана таблиця є подвійною матрицею, складеною з матриці ||xij||m,n, яку називають матрицею перевезень, та матриці ||cij||m,n, яку називають матрицею витрат. Елементи цих матриць невід’ємні, тобто xij>=0, cij>=0, (i=1, … m; j = 1, … n), оскільки вартості перевезень (відстані) і розміри постачань не можуть бути від’ємними числами. З умови задачі випливає, що повинні виконуватися такі умови:

    , (i=1,…,m)           (4)

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

    , (j=1,…,n)       (5)

    Отже, потреби кожного пункту призначення Вj повинні бути повністю задоволені.

    Вартість перевезень з і-го пункту відправлення в усі пункти призначення дорівнює

    , (i=1,…,m)

    Загальна вартість перевезень вантажів з усіх пунктів відправлення в усі пункти призначення

           (6)

    Математично транспортну задачу формулюють так: серед невід’ємних розв’язків системи обмежень

    , (i=1,…,m) та , (j=1,…,n)   (7)

    знайти такий, який перетворює лінійну функцію (6) на мінімум.

    З’ясуємо питання про сумісність системи рівнянь (6). Рівняння (4) здобуті в результаті додавання елементів рядків таблиці, яка задає умову задачі, а рівняння (5) – в результаті додавання елементів стовпців цієї самої таблиці. Якщо скласти всі рівняння системи (4) і окремо всі рівняння системи (5), то складені при цьому суми і є одним і тим самим числом, що є сумою всіх елементів вищезгаданої таблиці. Крім того,

    і

    Отже, умова є необхідною для сумісності системи рівнянь (7).

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

    хij = ai*bj / А (i=1, …m ; j = 1, … n), де

    Числа xij>=0 і cij>=0 задовольняють систему (7).

    Справді, підставивши ці вирази в систему (7), одержимо:



    Отже, числа хij = ai*bj / А утворюють план задачі (6) і (7).

    Визначимо ранг матриці системи рівнянь (7). Додавши перші m рівнянь і останні n рівнянь та взявши до уваги рівність , робимо висновок, що між рівняннями системи (7) існує лінійна залежність. Отже, ранг матричної системи менший за m + n (m+n-кількість рівнянь).

    Покажемо, що ранг матриці системи дорівнює m+n-1. Для цього досить показати, що систему (7) можна розв’язати відносно деяких m+n-1 невідомих. За такі невідомі візьмемо невідомі х11, х12,…, х1n, х21, х31, …, хm1, що містяться в першому рядку і першому стовпці таблиці де вказана умова задачі. Цих невідомих m+n-1.

    З рівнянь системи (4), починаючи з другого, знайдемо невідомі хі1(і=2,3,…, m):

    хі1 = аі – хі2 – хі3 – …- хіn (і=2,3,…, m)   (13)

    Аналогічно, використавши всі рівняння системи (5), крім першого, знайдемо невідомі х1j (j=2,3,…,n):

    x1j =bj – x2j – x3j – …- xmj (j=2,3,…,n).   (14)

    Щоб знайти невідоме х11, використаємо, наприклад, перше рівняння системи (4), підставивши в нього знайдені вже вирази невідомих х1j (j=2,3,…,n) з (14). Дістанемо

    х11 = а1 – х12 – х13 – …- х1n = a1 – (b2 – x22 – x32 -…- xm2) – (b3 – x23 – x33 – …-xm3) – …- (bn – x2n – x3n – …- xmn).

    Таким чином, m + n – 1 невідомих системи (7) виражено через решту m*n – (m + n – 1) невідомих цієї системи, а це означає, що ранг матриці системи дорівнює m + n – 1.

    Отже, якщо складено не вироджений опорний план транспортної задачі, то в матриці ||xij||m,n значень його компонентів (таблиці з умовою) додатними є тільки m + n – 1, а решта дорівнюють нулю.

    Клітинки, в яких містяться відмінні від нуля перевезення, називають завантаженими, а решту – не завантаженими. Завантажені клітинки відповідають базисним невідомим. Для не виродженості опорного плану кількість цих клітинок повинна дорівнювати m + n – 1.

    Транспортну задачу в постановці (4), (5) можна розв’язати симплексним методом, але навіть при невеликих значеннях m і n застосування цього методу призводить до громіздких обчислень.

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

    3.2. Відкрита модель транспортної задачі

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

    На практиці часто рівність (1) не виконується, тобто або запас вантажів у пунктах відправлення перевищує попит у пунктах призначення (2), або попит у пунктах призначення перевищує запас вантажів у пунктах відправлення (3). Для цих випадків також можна поставити задачі про побудову плану перевезень з мінімальними транспортними витратами. Такі задачі називають відкритими моделями транспортних задач.

    Відкриті моделі транспортних задач розв’язують зведенням їх до закритих моделей. Так, щоб знайти оптимальний план перевезень, коли запаси перевищують попит (7 ) вводять фіктивного споживача Вn+1 і вважають, що його попит дорівнює різниці між запасами вантажів у пунктах відправлення і реальним попитом у пунктах призначення, тобто


    Вважають, що вартості перевезень вантажів з усіх пунктів відправлення у пункт призначення рівні:

    c1(n+1)= c2(n+1) = … = cm(n+1) = c*.

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


    Величини c1(n+1) (i=1, …m) можуть бути якими завгодно, важливо тільки, щоб усі вони були рівні між собою. При цьому вартості перевезень за планом вихідної задачі ||xij||m,n відрізняються від вартостей перевезень за планами нової задачі ||xij||m(n+1) на сталу величину, що дорівнює с*. Тому план вихідної задачі, який дістали з оптимального плану нової задачі, є також оптимальним. Справді, якби для вихідної задачі був ліпший план, то, додавши вираз для с*, мали б для нової задачі план, ліпший за оптимальний, що неможливо.

    На практиці, звичайно, вважають, що вартості перевезень у фіктивний пункт призначення дорівнюють нулю: c1(n+1) =0 (i=1, …m), оскільки вантажі в цей пункт реально не перевозяться.

     

    4. Транспортна задача за критерієм часу

    Розглянемо транспортну задачу за критерієм часу.

    Нехай задано матрицю ||tij ||, де tij – час на перевезення вантажу з і-го пункту відправлення в j-й пункт призначення.

    Нехай, як і раніше, хij – кількість одиниць вантажу, який планується перевезти з і-го пункту відправлення в j-й пункт призначення. Припустимо, що виконується умова


    Задача полягає у визначенні m*n невід’ємних змінних хij , тобто плану перевезень ||хij||mn, за яким весь вантаж буде доставлено споживачам у найкоротший термін. Така постановка задачі доцільна тоді, коли йдеться про перевезення термінових вантажів, або таких, що швидко псуються.

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

    Позначимо через t*ij елементи матриці ||tij||, що відповідають завантаженим клітинкам у розв’язку Х =||хij||, тобто для яких хij > 0.

    Серед усіх цих tij існує найбільше, яке позначимо через Т. Отже, Т = max{t*ij}. Величина Т визначатиме час, протягом якого здійснюється даний план перевезень Х =||хij||. Кожному плану перевезень Х =||хij|| відповідає певне значення Т, отже Т = Т(Х). Необхідно визначити такий план перевезень Х, для якого величина Т буде найменшою.

    Для розв’язування транспортних задач за критерієм часу скористаємось таким методом:

    Починаючи з вихідного опорного плану, будуватимемо наступні плани, визначаючи на кожній ітерації досягнуте значення Т = max{ tik }.

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

    У таблиці, що залишилася, клітинку (s,t), для якої tik = T треба звільнити. Для цього побудуємо так званий “розвантажувальний” цикл, який може складатися як з завантажених, так і з вільних клітинок, але за умови, що всім клітинкам з непарними номерами відповідатимуть хik , а з парними номерами відповідатимуть клітинки, для яких tik < T. Таких циклів у загальному випадку можна побудувати кілька.

    Визначивши для побудованого циклу значення λ =min {хik}, переміщатимемо його вздовж циклу, віднімаючи від хik >0, розміщених у непарних клітинках та додаючи до чисел, розміщених у парних клітинках.

    Якщо виявиться, що λ =хst, то клітинка (s,t) повністю звільнюється і в подальшому не розглядається. Якщо ж λ < хst, то вантаж у даній клітинці зменшується: х*stst – λ. У цьому випадку будуватимемо новий “розвантажувальний” цикл і т.д., поки не дістанемо х*st=0. На цьому одна ітерація закінчується. Далі знову визначатимемо нове значення Т*<Т, закреслюючи клітинки зі значеннями tik > T*. Продовжуємо цей процес доти, поки на якісь ітерації буде вже неможливо перетворити на нуль вантаж, якому відповідає час Т. Це означатиме, що досягнуто оптимальне значення.

     

    5. Приклад розв’язування транспортної задачі

    На 3 аптечних складах є в наявності відповідно 80, 75 і 90 упаковок хіміопрепаратів, які повинні бути доставлені в 4 аптеки, відповідно, в кількостях 10, 80, 70 і 55 упаковок. Вартість доставки однієї упаковки хіміопрепарату з аптечного складу до аптеки (в копійках) вказана у таблиці:

    Аптечні склади

    Споживачі

    1

    2

    3

    4

    A

    40

    50

    70

    10

    B

    50

    10

    40

    30

    C

    30

    70

    10

    50

    5.1. Аналітичне розв’язування задачі

    Застосуємо вище вказану теорію до поставленої перед нами задачі. Попередньо було теоретично обґрунтовано розв’язок поставленої задачі. Поставлена перед нами задача відноситься до відкритого типу, оскільки сумарні ресурси (245) є меншими від сумарних потреб (215) , тобто виконується нерівність (3):

            

    Вводимо фіктивний склад D з запасами:


    а також вартість перевезень з фіктивного складу D до аптек:

    G41=0, G42 =0, G43=0, G44=0

    позначивши через х41, х42, х43, х44 кількості упаковок хіміопрепарату, які перевозяться з фіктивного складу D до відповідних аптек.

    Після таких дій відкрита модель транспортної задачі перетворюється в закриту модель, так як


    Тепер:

  • матриця, що визначає план перевезень:


  • матриця транспортних витрат:


  • вектор ресурсів складів А, В, С, D:

    а={80 75 90 20}

  • вектор потреб аптек 1,2,3,4:

    b={10 80 70 55}

    Сформулюємо математичну модель задачі.

  1. Цільова функція, що відповідає сумарним затратам на перевезення хіміопрепарату зі складів аптекам, має вигляд:


  2. При цьому обмеження будуть наступними:
  • обмеження по ресурсах :


  • обмеження по потребах:


  • умови невід’ємності:

    хij і 0 (i = 1,…,4; j = 1,…,1);

  • умови цілочисельності:

    хij – цілі (i = 1,…,4; j = 1,…,1).

    Подальші розрахунки наведені не будуть у зв’язку з їх громіздким характером.

    5.2. Розв’язування задачі за допомогою Excel

    Для розв’язування транспортної задачі програмний пакет містить надстройку “Поиск решения”. Дана надстройка запускається командою меню “Сервис”,”Поиск решения”, при цьому виводиться діалогове вікно (мал. 1).

    Вихідна таблиця, що містить всю необхідну інформацію для розв’язування задачі має вигляд, представлений на мал. 4.

    В діапазон F3:F5 записані запаси хіміопрепаратів, розміщених, відповідно, на реальних складах А, В, С.

    У діапазон В8:E8- потреби в хіміопрепаратах аптек 1-4.

    У комірку F7 занесена контрольна сума хіміопрепаратів розміщених на складах, тобто сума комірок F3:F5. У комірку F8 заносимо контрольну суму потреб у хіміопрепаратах всіх аптек, тобто суму комірок В8:E8.

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

    =F8-F7

    У діапазоні комірок В12:E15 формуємо матрицю вартості перевезень одного хіміопрепарату з кожного складу в кожну аптеку.

    В якості початкових значень в діапазон В3:E1 введені нулі.


    Малюнок 1. Діалогове вікно “Поиск решения”


    Малюнок 2. Діалогове вікно “Параметры поиска решения”


    Малюнок 3. Діалогове вікно “Изменение ограничения”


    Малюнок 4. Вихідні дані задачі

    Далі в комірку C17 вводимо формулу для розрахунку цільової функції, яка має вигляд:

    =СУММПРОИЗВ(B12:E15;B3:E1).

    Обмеження задачі записуються в комірки С19:С21, куди вводяться функції, які відповідають вираженням обмежень (сформульовані в попередньому пункті).

    Для обмеження А заносимо в комірку С19 сумарну кількість хіміопрепаратів, які буде завезено зі складу А в усі аптеки:

    =СУММ(B3:E3)

    Для обмежень В, С, D, вміст комірки С19 копіюємо в комірки C20, C21, C22, при цьому одержуємо наступні функції:

    =СУММ(B4:E4)

    =СУММ(B5:E5)

    =СУММ(B1:E1)

    Для обмеження 1 заносимо в комірку C23 сумарну кількість хіміопрепаратів, які будуть доставлені першій аптеці зі всіх складів. Для цього в комірку C23 вводимо формулу яка має вигляд:

    =СУММ(B3:B1)

    Аналогічно заповнюються комірки C24:C21 для обмежень 2-4.

    =СУММ(C3:C1)

    =СУММ(D3:D1)

    =СУММ(E3:E1)

    Завершивши складання робочого листка (мал. 4), запускаємо з меню Сервис команду Поиск решения. З’являється діалогове вікно (мал. 1). В полі Установить целевую ячейку вказуємо адресу комірки, котра містить результати розрахунку цільової функції. В нашому випадку це комірка С17.

    В розділі Равной: вибираємо перемикач “минимальному значению”. В полі Изменяя ячейки вказуємо діапазон комірок $B$3:$E$1 – їх значення можуть змінюватися в процесі пошуку рішення.

    Щоб ввести обмеження задачі, в розділі “Ограничения” натиснемо кнопку Добавить. При цьому відкривається діалогове вікно Добавление ограничений (мал. 3). Вводимо обмеження згідно табл. 1.

    Таблиця 1. Обмеження до розрахунку задачі складання графіку доставки

    Формула

    Опис

    $C$19=$F$3

    загальна кількість перевезених зі складу А препаратів для всіх аптек рівна запасу препаратів на тому ж складі

    $C$20=$F$4

    те ж для складу B

    $C$21=$F$5

    те ж для складу C

    $C$22=$F$1

    те ж для складу D

    $C$23=$В$8

    сумарна кількість препаратів, що доставляються в аптеку №1 не повинна перевищувати потреб даної аптеки

    $C$24=$C$8

    те ж для аптеки №2

    $C$25=$D$8

    те ж для аптеки №3

    $C$21=$E$8

    те ж для аптеки №4

    $B$3:$E$7=цел

    неможна розділяти одну упаковку фармпрепарату між кількома аптеками

    Для реалізації умови невід’ємності значень в діалоговому вікні Поиск решения натискаємо кнопку Параметри. В вікні Параметры поиска решений (мал. 3) включаємо прапорець Неотрицательные значения та “Линейная модель”.

    При натисканні кнопки Выполнить діалогового вікна Поиск решения з’являється діалогове вікно Результаты поиска решений. Вибираємо тип звіту Результаты. Після натискання кнопки ОК на робочому листі з’являються результати розрахунків. Таблиця з результатами буде мати вигляд, як на мал. 5.


    Малюнок 5. Результати пошуку рішення з мінімумом обмежень.

    Аналізуючи отримані дані, можна встановити недопустимість подібного графіку. Так, як склад D фіктивний, то аптека №3 недоотримає 20 упаковок препаратів з 70 замовлених, або ж 28%.

    Випливає цілком логічне рішення – раз сумарні потреби вищі, ніж наявні запаси препаратів, рівномірно розподілити їх між аптеками, пропорційно до замовленої кількості. Здійснити це можна, накладаючи додаткові обмеження у вікні надстройки Поиск решения. Ці обмеження – кількість упаковок препаратів, які доставлятимуться з фіктивного складу D до кожної з аптек, інакше кажучи, кількість недоодержаних препаратів (мал. 1).


    Малюнок 1. Результати пошуку рішення після накладання додаткових обмежень.

     

    Висновки

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

    Дана задача полягає в тому, що потрібно спроектувати такий план перевезень, при якому їх загальна вартість буде мінімальна, тобто треба вказати, скільки одиниць вантажу повинно бути відправлено з довільного і – го пункту відправлення в будь-який j – тий пункт призначення – так, щоб максимально задовольнити потреби і щоб сумарні затрати на перевезення були мінімальні.

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

    Серед цих методів найбільш відомі наступні:

    1. Розподільчий метод;

    2. Модифікований розподільчий метод (він же метод потенціалів), запропонований Л.В.Канторовичем та М.К.Гавуріним, а згодом, незалежно від них, Дж. Данцігом;

    3. Венгерський метод, запропонований Е. Егерварі і удосконалений Х. Куном для розв’язування окремого випадку транспортної задачі: задачі про призначення (або про вибір), а пізніше узагальнений Дж. Манкресом на транспортну задачу загального виду;

    4. Метод диференціальних рент А. Л. Брудно;

    Самостійно розв’язав слідуючу задачу.

    На 3 аптечних складах є в наявності відповідно 80, 75 і 90 упаковок хіміопрепаратів, які повинні бути доставлені в 4 аптеки, відповідно, в кількостях 10, 80, 70 і 55 упаковок. Вартість доставки однієї упаковки хіміопрепарату з аптечного складу до аптеки (в копійках) вказана у таблиці:

    Аптечні склади

    Споживачі

    1

    2

    3

    4

    A

    40

    50

    70

    10

    B

    50

    10

    40

    30

    C

    30

    70

    10

    50

    Виконавши курсову роботу я зробив такий висновок.

    Вивчення транспортних задач має виключно практичне значення, так, як, по-перше, дозволяє знизити транспортні витрати конкретного підприємства на 10-30 %, а по-друге, велику кількість інших прикладних задач можна описати математичними моделями, що є подібні до моделей транспортних задач.

    Якщо буде можливість займатись цими задачами я буду ними займатись адже це область задач які потребують розв’язку.

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Транспортна задача I її розвязування засобами Microsoft Excel (455.0 KiB, Завантажень: 16)

завантаження...
WordPress: 23.38MB | MySQL:26 | 0,380sec