Зміст
Введення
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. Побудова моделей транспортної завдання
завдання програма модель
Теоретичне введення . Задача про розміщення (транспортна задача) - це завдання, в якій роботи і ресурси вимірюються в одних і тих же одиницях. В таких завданнях ресурси можуть бути розділені між роботами, і окремі роботи можуть бути виконані за допомогою різних комбінацій ресурсів. Прикладом типової транспортної задачі (ТЗ) є розподіл (транспортування) продукції, що знаходиться на складах, по підприємствам-споживачам.
Стандартна транспортна задача визначається як задача розробки найбільш економічного плану перевезення продукції одного виду з декількох пунктів відправлення в пункти призначення. При цьому величина транспортних витрат прямо пропорційна обсягом перевезеної продукції і задається за допомогою тарифів на перевезення одиниці продукції
Особливості економіко-математичної моделі транспортної задачі:
- система обмежень Тобто система рівнянь (тобто транспортна задача задана в канонічній формі); - коефіцієнти при змінних системи обмежень дорівнюють одиниці або нулю; - кожна змінна входить в систему обмежень два рази.
Критерій оптимальності формулюється наступним чином: базисне розподіл поставок оптимально тоді і тільки тоді, коли оцінки всіх вільних клітин ненегативні. Циклом в матриці називається ламана з вершинами в клітинах та ланками, що лежать уздовж рядків і стовпців матриці, задовольняє умовам:
В· ламана повинна бути зв'язковою, тобто з будь-якої її вершини можна потрапити в будь-яку іншу вершину по ланкам ламаної;
В· в кожній вершині ламаної зустрічаються дві ланки, одне з яких розташ...
