• Геометрично область допустимих рішень такого завдання можна представити як багатогранник в n мірному просторі
  • 1. Формулювання проблеми в практичній області
  • Формальна (математична постановка задач)
  • Аналіз постановки завдань і обґрунтування методу вирішення
  • 2. Побудова моделей транспортної задачі


  • Дата конвертації14.04.2017
    Розмір17.45 Kb.
    Типкурсова робота

    Скачати 17.45 Kb.

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

    зміст

    Вступ

    1. Формулювання проблеми в практичній області

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

    3. Реалізація алгоритму програми

    Інструкція користувача

    висновок

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

    Вступ

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

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

    Всі завдання лінійного програмування можна розділити на наступні групи:

    · Завдання про використання ресурсів, сировини, планування виробництва;

    · Завдання складання раціону

    · Завдання про використання потужностей, завантаженні обладнання

    · Завдання про розкрої матеріалів

    · Транспортні завдання

    Їх розгляд тут не наведено, тому що не є необхідним для даного проекту.

    Але треба представляти загальну задачу лінійного програмування (ОЗЛП), так як для складання алгоритму необхідно розуміти математичний сенс рішення задачі. Нижче, наведено математичний опис загального вигляду задачі лінійного програмування.

    Геометрично область допустимих рішень такого завдання можна представити як багатогранник в n мірному просторі

    Приклад геометричного уявлення області допустимих рішень задачі, де F - лінія цільової функції, F = 0 початкове положення функції, F = F max оптимальне положення функції, A, B, C, D, E - вершини багатокутника.

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

    Розглянуто основна теореми лінійного програмування, з якої випливає, що якщо задача лінійного програмування має оптимальне рішення, то воно відповідає хоча б одній кутовій точці багатогранника рішень і збігається, по крайней мере, з одним з допустимих базисних рішень системи обмежень. Там же був вказаний шлях вирішення будь-якої задачі лінійного програмування: перебрати кінцеве число допустимих базисних рішень системи обмежень і вибрати серед них той, на якому функція мети приймає оптимальне рішення. Геометрично це відповідає перебору всіх кутових точок багатогранника рішень. Такий перебір врешті-решт призведе до оптимального рішення (якщо воно існує), проте його практичне здійснення пов'язане з величезними труднощами, так як для реальних завдань число допустимих базисних рішень хоча і звичайно, але може бути надзвичайно велике.

    Число перебираються допустимих базисних рішень можна скоротити, якщо проводити перебір не безладно, а з урахуванням змін лінійної функції, тобто домагаючись того, щоб кожне наступне рішення було "краще" (або, принаймні, "не гірше"), ніж попереднє, за значеннями лінійної функції (збільшення її при знаходженні максимуму F -> max, зменшення - при знаходженні мінімуму F-> min).

    1. Формулювання проблеми в практичній області

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

    Мета роботи - визначення методу розрахунку плану перевезення продукції з

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

    Формальна (математична постановка задач)

    Завдання про розміщення (транспортна задача) Це завдання, в якій роботи і ресурси вимірюються в одних і тих же одиницях. У таких завданнях ресурси можуть бути розділені між роботами, і окремі роботи можуть бути виконані за допомогою різних комбінацій ресурсів. Прикладом типової транспортної задачі (ТЗ) є розподіл (транспортування) продукції, що знаходиться на складах, по підприємствам-споживачам. Дана система з m лінійних рівнянь і нерівностей з n змінними:

    a 11 x 1 + a 12 x 2 + ... + a 1n x n ≤ b 1

    a 21 x 1 + a 22 x 2 + ... + a 2n x n ≤ b 2

    a k1 x 1 + a k2 x 2 + ... + a kn x n ≤ b k

    a m1 x 1 + a m2 x 2 + ... + a mn x n ≤ b m1

    і лінійна функція

    F = c 1 x 1 + c 2 x 2 + ... + c n x n (2)

    Необхідно знайти таке рішення (план) системи


    X = (x 1, x 2...., X j...., X n) (3)

    де

    x j <0 (j = 1,2, ..., l, l ≤ n) (4)

    при якому лінійна функція F (2) приймає оптимальне), є максимальне або мінімальне в залежності від завдання) значення. При цьому система (1) - система обмежень, а функція F (2) - цільова функція (функція мети).

    Аналіз постановки завдань і обґрунтування методу вирішення

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

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

    задача програма модель

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

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

    Особливості економіко-математичної моделі транспортної задачі:

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

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

    · Ламана повинна бути зв'язковою, тобто з будь-якої її вершини можна потрапити в будь-яку іншу вершину по ланках ламаної;

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

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

    Вихідні параметри моделі транспортної задачі

    1) n- кількість пунктів відправлення, m - кількість пунктів призначення.

    2) a i - запас продукції в пункті відправлення A i (i = 1, n) [од. прод.].

    3) b j - попит на продукцію в пункті призначення B j (j = 1, m) [од. прод.].

    4) c ij - тариф (вартість) перевезення одиниці продукції з пункту відправлення a i в пункт призначення b j [руб. / Од. прод.].

    Шукані параметри моделі транспортної задачі

    1) x ij - кількість продукції, що перевозиться з пункту відправлення a i в пункт призначення b j [од. прод.].

    2) L (x) - транспортні витрати на перевезення всієї продукції [руб.].

    Етапи побудови моделі

    I. Визначення змінних.

    II. Перевірка збалансованості завдання.

    III. Побудова збалансованої транспортної матриці.

    IV Завдання цільової функції.

    V Завдання обмежень.

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

    Таблиця 4.1Общій вид транспортної матриці

    пункти

    відправлення, A 1

    Пункти споживання, B j

    запаси,

    од. прод.

    B 1 B 2 ... Bm
    A 1 c 11, [руб. / од. прод.] c 12 ... c 1m a 1
    A 2 c 21 c 22 ... C 2m a 2
    ... ... ... ... ... ...
    A n C n1 C n2 ... C nm a n

    потреба

    од. прод.

    b 1 b 2 ... b m

    З моделі (4.1) випливає, що сума запасів продукції в усіх пунктах відправлення повинна дорівнювати сумарній потреби у всіх пунктах споживання, тобто

    . (

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

    .

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

    .

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

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

    Змінні задачі про призначення визначаються наступним чином

    3. Реалізація алгоритму програми

    Програма написана в програмному середовищі C ++ Builder 6.0. Для реалізації всіх методів програми використовуються наступні бібліотеки:

    h> - бібліотека візуальних компонентів (зовнішнє оформлення програми)

    У програмі визначено і ініціалізовані наступні змінні і масиви:

    massiv 1 [5] [5] - масив потужностей постачальників і споживачів

    massiv 2 [5] [5] - масив поставок

    massiv 3 [5] [5] - масив значень матриці оцінок

    massiv 4 [5] [5], massiv 5 [5] [5] - додаткові масиви

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


    Інструкція користувача

    Про програму. Програма дозволяє перевірити правильність рішення транспортних завдань або ж зробити за вас всю рутинну роботу при вирішенні цих завдань. Програма дозволяє завантажувати таблиці з файлу (* .dat) або створювати нову таблицю, шляхом створення осередків таблиці. Програма працює на будь-який IBM сумісної машині при 32 Мб ОЗУ і 1 Мб вільного місця на диску, на будь-якому процесорі старше 486 і ОС Windows 98 \ 2000 \ XP.

    Опис програми. Програма має зручний і зрозумілий інтерфейс, завдяки якому швидко освоюється користувачем. При запуску програми відкрито вікно введення значень.

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

    Після перегляду результатів необхідно очищати елементи інтерфейсу натисканням на кнопку меню «Скинути». Після кожного рішення потрібно очищати введені дані, в іншому випадку програма неправильно порахує поставлену задачу.

    Опис роботи програми. Для початку роботи потрібно завантажити файл за допомогою команди Файл> Відкрити.

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

    Збереження значень оуществляется меню Файл => Зберегти.

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

    Коли розподіл поставок буде оптимальним алгоритм програми закінчує своє рішення. Функція мети () і кількість кроків підраховується автоматично.

    Після цього необхідно натиснути кнопку "скидання" для відновлення вихідних параметрів програми.

    Для виходу з програми потрібно скористатися меню Файл => Вихід.


    висновок

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


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

    1. Економіко-математичні методи і прикладні моделі. Фінстатінформ М., 1997.

    2. Абчук В.А., Економіко-математичні методи. Санкт-Петербург Союз, 1999.

    3. Рад Б.Я, Яковлєв С.А., Моделювання систем. Практикум. М. Вища школа, 1999.

    4. Замків О.О., Толстопятенко А.В., Черемних Ю.Н., Математичні методи в економіці. М.ДІС, 1997..


    Головна сторінка


        Головна сторінка



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

    Скачати 17.45 Kb.