Курсова робота
за курсом: Економіко-математичні методи і моделі
на тему: «Застосування лінійного програмування для вирішення економічних завдань (оптимізація прибутку)»
Тюмень, 2007
ЗМІСТ
Вступ 3
1. Теоретико-методичне опис методу лінійного програмування 5
2. Області застосування і обмеження використання лінійного програмування для вирішення економічних завдань 16
3. Оптимізація прибутку із застосуванням методу ЛП 23
3.1 Постановка завдання і формування оптимізаційної моделі 23
3.2 Розрахунок і аналіз результатів оптимізації прибутку 24
Висновок 27
Список літератури 29
Одним з необхідних умов подальшого розвитку економічної науки є застосування точних методів кількісного аналізу, широке використання математики. В даний час новітні досягнення математики і сучасної обчислювальної техніки знаходять все більш широке застосування в економічних дослідженнях і плануванні. Цьому сприяє розвиток таких розділів математики, як математичне програмування, теорія ігор, теорія масового обслуговування, а також бурхливий розвиток швидкодіючої електронно-обчислювальної техніки. Вже накопичений достатній досвід постановки та вирішення економічних завдань за допомогою математичних методів. Особливо успішно розвиваються методи оптимального планування, які й становлять сутність математичного програмування.
Однією з основних стає завдання створення єдиної системи оптимального планування та управління народним господарством на базі широкого застосування математичних методів і електронно-обчислювальної техніки в економіці.
Основною метою написання курсової роботи є всебічний аналіз застосування лінійного програмування для вирішення економічних завдань. Завданнями курсової роботи є:
1. Теоретико-методичне опис методу лінійного програмування;
2. Виявлення області застосування та обмеження використання лінійного програмування для вирішення економічних завдань;
3. Оптимізація прибутку із застосуванням методу лінійного програмування;
4. Постановка завдання і формування оптимізаційної моделі;
5. Розрахунок і аналіз результатів оптимізації прибутку.
Лінійне програмування - це наука про методи дослідження і відшукання найбільших і найменших значень лінійної функції, на невідомі якої накладено лінійні обмеження. Таким чином, завдання лінійного програмування відносяться до завдань на умовний екстремум функції. За типом розв'язуваних задач методи поділяються на універсальні і спеціальні. За допомогою універсальних методів можуть вирішуватися будь-які завдання лінійного програмування (ЗЛП). Спеціальні методи враховують особливості моделі задачі, її цільової функції і системи обмежень.
Особливістю завдань лінійного програмування є те, що екстремуму цільова функція досягає на кордоні області допустимих рішень. Класичні ж методи диференціального обчислення пов'язані з перебуванням екстремумів функції у внутрішній точці області допустимих значень. Звідси - необхідність розробки нових методів. [3, c.7]
Лінійне програмування є найбільш часто використовуваний метод оптимізації. До завдань лінійного програмування можна віднести завдання:
1. раціонального використання сировини та матеріалів;
2. задачі оптимального розкрою;
3. оптимізації виробничої програми підприємств;
4. оптимального розміщення і концентрації виробництва;
5. складання оптимального плану перевезень, роботи транспорту (транспортні завдання);
6. управління виробничими запасами;
7. і багато інших, що належать сфері оптимального планування.
Лінійне програмування є однією з основних частин того розділу сучасної математики, який отримав назву математичного програмування. У загальній постановці, завдання цього розділу виглядають наступним чином.
Потрібно знайти такі невід'ємні
... ... ... ... ... ... ... ... ... ...
У залежності від виду функції
Форми завдань лінійного програмування:
1. стандартна;
1.1 перша стандартна форма (формула 1.3);
1.2 другого стандартна форма (формула 1.4);
2. канонічна (формула 1.5).
... ... ... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ... ...
Завдання на мінімум (формула 1.6) можна вирішувати як завдання на максимум. Досить знаки цільової функції поміняти на протилежні (формула 1.7). У результаті необхідно знак цільової функції поміняти на протилежний.
Аналогічно можна змінити знак нерівності менше або дорівнює (формула 1.8) на більше або дорівнює (формула 1.9).
Цільова функція задачі лінійного програмування досягає свого екстремуму (мінімуму або максимуму) у вершині допустимої області. Якщо цільова функція досягає екстремального значення більш ніж на одній вершині, то вона досягає того ж значення в будь-якій точці, що є опуклою комбінацією цих вершин (альтернативний оптимум).
Ця теорема має найважливіші значення, так як вона вказує шлях вирішення задачі лінійного програмування. Зовсім не треба перебирати всі крапки допустимої області. Досить перебрати вершини допустимої області, адже їх кінцеве число. Крім того, не потрібно перебирати всі вершини, можна цей перебір істотно скоротити.
Будь-який набір чисел
Завдання лінійного програмування вирішуються декількома методами:
1. графічний метод;
2. симплексний метод;
3. двоїстість у ЛП;
4.двойственний симплексний метод.
Завдання лінійного програмування з двома змінними завжди можна вирішити графічно. Проте вже в тривимірному просторі таке рішення ускладнюється, а в просторах, розмірність яких більше трьох, графічне рішення неможливо.
Графічний метод досить простий і наочний. Він заснований на геометричному представленні допустимих рішень задачі. Кожне з нерівностей завдання ЛП визначає на координатній площині
деяку полуплоскость, а система нерівностей в цілому - перетин відповідних площин. Безліч точок перетину даних півплощин називається областю допустимих рішень (ОДР). ОДР завжди являє собою опуклу фігуру, тобто володіє наступною властивістю: якщо дві точки А і В належать цій особі, то і весь відрізок АВ належить їй. ОДР графічно може бути представлений опуклим багатокутником, необмеженим опуклої багатокутної областю, відрізком, променем і т.д. У разі несумісності системи обмежень задачі ОДР є порожнім безліччю.
При пошуку оптимального рішення задач лінійного програмування можливі наступні ситуації: існує єдине рішення задачі, існує нескінченна безліч рішень (альтернативний оптимум); ЦФ не обмежена; область допустимих рішень-єдина точка; завдання не має рішень. [3 c.55-57]
Будь-яка задача лінійного програмування, незалежно від виду запису, може бути приведена до стандартної і канонічній формі і вирішена симплексним методом, що у певному сенсі є універсальним методом ЛП. Алгоритм симплекс-методу носить ітераційний характер.
Симплекс-метод дозволяє переходити від одного допустимого базисного розв'язку до іншого, причому так, що значення цільової функції безперервно зростають. Алгоритми симплекс-методу дозволяють також встановити, чи є завдання ЛЗ розв'язною.
Перехід від одного базису до іншого дозволяє знаходити рішення майже всіх задач ЛП. Визначивши всі крайні точки, можна обчислити значення цільової функції і знайти оптимальне рішення. Проте для великих значень m і n це практично неможливо. [1 c.15]
Алгоритм розв'язання задачі ЛП табличним симплексом-методом складається з наступних етапів:
1. розраховують і заповнюють початкову симплекс-таблицю з допустимим одиничним базисом, включаючи індексний рядок.
2. знаходять дозволяє стовпець;
3. знаходять роздільну рядок;
4. розраховують методом Жордана-Гаусса всі параметри матриці;
5. аналізують отримані дані в індексному рядку.
Таблиці симплекс-методу необхідно будувати до тих пір, поки не буде отриманий оптимальний план. План буде вважатися оптимальним, якщо в останній індексному рядку симплекс-таблиці будуть лише нулі і позитивні числа. [1 c.20-22]
При побудові симплексного методу передбачалося, що всі опорні плани невироджені, що забезпечувало отримання оптимального плану за кінцеву кількість кроків. У випадку виродженого плану обчислення виробляють аналогічно, але в цьому випадку можливе повернення до старого базису, що приводь до так званого зациклення.
Метод штучного базису застосовується при наявності в обмеженні знаків "дорівнює", "більше або дорівнює", "менше або дорівнює" і є модифікацією табличного методу. Рішення системи виробляється шляхом введення штучних змінних зі знаком, що залежать від типу оптимуму, тобто для виключення з базису цих змінних останні вводяться в цільову функцію з великими негативними коефіцієнтами m, а в завдання мінімізації - з позитивними m. Таким чином, з вихідної виходить нова m - завдання.
Якщо в оптимальному вирішенні m - завдання немає штучних змінних, це рішення є оптимальне рішення вихідної задачі. Якщо ж в оптимальному вирішенні m - завдання хоч одна з штучних змінних буде відмінна від нуля, то система обмежень вихідної задачі несовместна і вихідна задача нерозв'язна.
В основу модифікованого симплекс - методу покладені такі особливості лінійної алгебри, які дозволяють у ході виконання завдання працювати з частиною матриці обмежень. Іноді метод називають методом зворотної матриці.
У процесі роботи алгоритму відбувається спонтанне звернення матриці обмежень по частинах, відповідними поточними базисним векторам. Зазначена здатність робить вельми привабливою машинну реалізацію обчислень внаслідок економії пам'яті під проміжні змінні і значного скорочення часу рахунку. Хороший для ситуацій, коли число змінних n значно перевищує число обмежень m.
У цілому, метод відображає традиційні риси загального підходу до вирішення завдань лінійного програмування, що включає в себе канонізацію умов завдання, розрахунок симплекс-різниць, перевірку умов оптимальності, прийняття рішень про корекцію базису і виключення Жордана-Гаусса.
Особливості полягають у наявності двох таблиць - основний і допоміжної, порядок їх заповнення та деякою специфічності розрахункових формул.
Кожній задачі лінійного програмування можна певним чином зіставити деяку іншу задачу, звану двоїстої або сполученої по відношенню до початкової або прямої задачі. Зіставляючи форми запису прямої і двоїстої задач, можна встановити між ними наступні взаємозв'язки:
1. якщо пряма задача є задачею максимізації, двоїста буде завданням мінімізації, і навпаки;
2. коефіцієнти цільової функції прямої задачі стають вільними членами обмежень двоїстої задачі;
3. вільні члени обмежень прямої задачі стають коефіцієнтами цільової функції двоїстої задачі;
4. матриця обмежень двоїстої задачі виходить шляхом транспортування матриці обмежень прямої задачі;
5. знаки нерівностей в обмеженнях змінюються на протилежні;
6. число обмежень прямої задачі дорівнює числу змінних двоїстої задачі, і навпаки.
Види математичних моделей двоїстих задач можуть бути представлені у таблиці (табл. 1.1).
Таблиця 1.1
Види математичних моделей двоїстих задач
Таким чином, перш ніж записати двоїсту задачу для даної вихідної, систему обмежень вихідної задачі необхідно привести до відповідного виду. [3, с.114-115]
Якщо з пари двоїстих завдань одну володіє оптимальним планом, то й інша має рішення, причому для екстремальних значень лінійних функцій виконується певне співвідношення (формула 1.10). Якщо лінійна функція одним із завдань не обмежена, то інша не має рішення.
Якщо пряма (а значить, і двоїста) завдання вирішити, то в кожній парі подвійних умов одне є вільним, а інше закріпленим. Будь-яке з умов називається вільним, якщо воно виконується як суворе нерівність хочаб для одного оптимального вектора. Умова називається закріпленим, якщо воно виконується як рівність для всіх оптимальних векторів.
Двоїсту задачу вигідніше вирішувати, ніж пряму, якщо в прямій задачі при малій кількості змінних є велика кількість обмежень. [2, c 70-71]
Симплексний метод дозволяє поряд з отриманням рішення прямої задачі отримувати і рішення двоїстої задачі. Цей результат і лежить в основі двоїстого симплексного методу розв'язання задачі. Суть методу полягає в такому послідовному переборі кутових точок допустимого безлічі Q 0 двоїстої задачі, при якому значення цільової функції зростає, тобто в застосуванні симплексного методу до вирішення двоїстої задачі. Будемо припускати, що завдання невироджений, тобто кожної кутової точці безлічі Q 0 відповідає квадратна невироджена система рівнянь розмірності m, матрицю яку і називають двоїстим базисом прямої задачі. Разом з тим двоїстий симплекс-метод можна застосовувати при вирішенні задачі лінійного програмування, вільні члени системи рівнянь якої можуть бути будь-якими числами (при розв'язанні задачі симплексним методом ці числа передбачалися невід'ємними).
Відшукування рішення задачі двоїстим симплекс-методом включає в себе наступні етапи:
1. Знаходять псевдоплан завдання.
2. Перевіряють цей псевдоплан на оптимальність. Якщо псевдоплан оптимальний, то знайдене рішення задачі. В іншому разі або встановлюють нерозв'язність завдання, або переходять до нового псевдоплану.
3. Вибирають роздільну рядок за допомогою визначення найбільшого за абсолютною величиною негативного числа стовпця вектора Р 0 і дозволяє стовпець з допомогою знаходження найменшого за абсолютною величиною відносини елементів (m +1)-й рядка до відповідних негативним елементам роздільної рядка.
4. Знаходять новий псевдоплан і повторюють всі дії починаючи з другого етапу.
Двоїстий симплексний метод називають також методом послідовного уточнення оцінок, оскільки кутові точки завдання, що виникають при ітераціях, можна розглядати як наближені значення точної оцінки у *, тобто як наближені оцінки впливу умов завдання на величину мінімуму цільової функції. [2, c.87-92] за курсом: Економіко-математичні методи і моделі
на тему: «Застосування лінійного програмування для вирішення економічних завдань (оптимізація прибутку)»
Тюмень, 2007
ЗМІСТ
Вступ 3
1. Теоретико-методичне опис методу лінійного програмування 5
2. Області застосування і обмеження використання лінійного програмування для вирішення економічних завдань 16
3. Оптимізація прибутку із застосуванням методу ЛП 23
3.1 Постановка завдання і формування оптимізаційної моделі 23
3.2 Розрахунок і аналіз результатів оптимізації прибутку 24
Висновок 27
Список літератури 29
Введення
Розвиток сучасного суспільства характеризується підвищенням технічного рівня, ускладненням організаційної структури виробництва, поглибленням суспільного поділу праці, пред'явленням високих вимог до методів планування і господарського керівництва. У цих умовах тільки науковий підхід до керівництва економічним життям суспільства дозволить забезпечити високі темпи розвитку народного господарства.Одним з необхідних умов подальшого розвитку економічної науки є застосування точних методів кількісного аналізу, широке використання математики. В даний час новітні досягнення математики і сучасної обчислювальної техніки знаходять все більш широке застосування в економічних дослідженнях і плануванні. Цьому сприяє розвиток таких розділів математики, як математичне програмування, теорія ігор, теорія масового обслуговування, а також бурхливий розвиток швидкодіючої електронно-обчислювальної техніки. Вже накопичений достатній досвід постановки та вирішення економічних завдань за допомогою математичних методів. Особливо успішно розвиваються методи оптимального планування, які й становлять сутність математичного програмування.
Однією з основних стає завдання створення єдиної системи оптимального планування та управління народним господарством на базі широкого застосування математичних методів і електронно-обчислювальної техніки в економіці.
Основною метою написання курсової роботи є всебічний аналіз застосування лінійного програмування для вирішення економічних завдань. Завданнями курсової роботи є:
1. Теоретико-методичне опис методу лінійного програмування;
2. Виявлення області застосування та обмеження використання лінійного програмування для вирішення економічних завдань;
3. Оптимізація прибутку із застосуванням методу лінійного програмування;
4. Постановка завдання і формування оптимізаційної моделі;
5. Розрахунок і аналіз результатів оптимізації прибутку.
1. Теоретико-методичне опис методу лінійного програмування
В даний час лінійне програмування є одним з найбільш вживаних апаратів математичної теорії оптимального прийняття рішень. Для вирішення завдань лінійного програмування розроблено складне програмне забезпечення, що дає можливість ефективно і надійно вирішувати практичні завдання великих обсягів. Володіння апаратом лінійного програмування необхідно кожному фахівцю в галузі прикладної математики.Лінійне програмування - це наука про методи дослідження і відшукання найбільших і найменших значень лінійної функції, на невідомі якої накладено лінійні обмеження. Таким чином, завдання лінійного програмування відносяться до завдань на умовний екстремум функції. За типом розв'язуваних задач методи поділяються на універсальні і спеціальні. За допомогою універсальних методів можуть вирішуватися будь-які завдання лінійного програмування (ЗЛП). Спеціальні методи враховують особливості моделі задачі, її цільової функції і системи обмежень.
Особливістю завдань лінійного програмування є те, що екстремуму цільова функція досягає на кордоні області допустимих рішень. Класичні ж методи диференціального обчислення пов'язані з перебуванням екстремумів функції у внутрішній точці області допустимих значень. Звідси - необхідність розробки нових методів. [3, c.7]
Лінійне програмування є найбільш часто використовуваний метод оптимізації. До завдань лінійного програмування можна віднести завдання:
1. раціонального використання сировини та матеріалів;
2. задачі оптимального розкрою;
3. оптимізації виробничої програми підприємств;
4. оптимального розміщення і концентрації виробництва;
5. складання оптимального плану перевезень, роботи транспорту (транспортні завдання);
6. управління виробничими запасами;
7. і багато інших, що належать сфері оптимального планування.
Лінійне програмування є однією з основних частин того розділу сучасної математики, який отримав назву математичного програмування. У загальній постановці, завдання цього розділу виглядають наступним чином.
Потрібно знайти такі невід'ємні
... ... ... ... ... ... ... ... ... ...
У залежності від виду функції
Форми завдань лінійного програмування:
1. стандартна;
1.1 перша стандартна форма (формула 1.3);
1.2 другого стандартна форма (формула 1.4);
2. канонічна (формула 1.5).
... ... ... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ... ...
Завдання на мінімум (формула 1.6) можна вирішувати як завдання на максимум. Досить знаки цільової функції поміняти на протилежні (формула 1.7). У результаті необхідно знак цільової функції поміняти на протилежний.
Аналогічно можна змінити знак нерівності менше або дорівнює (формула 1.8) на більше або дорівнює (формула 1.9).
Цільова функція задачі лінійного програмування досягає свого екстремуму (мінімуму або максимуму) у вершині допустимої області. Якщо цільова функція досягає екстремального значення більш ніж на одній вершині, то вона досягає того ж значення в будь-якій точці, що є опуклою комбінацією цих вершин (альтернативний оптимум).
Ця теорема має найважливіші значення, так як вона вказує шлях вирішення задачі лінійного програмування. Зовсім не треба перебирати всі крапки допустимої області. Досить перебрати вершини допустимої області, адже їх кінцеве число. Крім того, не потрібно перебирати всі вершини, можна цей перебір істотно скоротити.
Будь-який набір чисел
Завдання лінійного програмування вирішуються декількома методами:
1. графічний метод;
2. симплексний метод;
3. двоїстість у ЛП;
4.двойственний симплексний метод.
Завдання лінійного програмування з двома змінними завжди можна вирішити графічно. Проте вже в тривимірному просторі таке рішення ускладнюється, а в просторах, розмірність яких більше трьох, графічне рішення неможливо.
Графічний метод досить простий і наочний. Він заснований на геометричному представленні допустимих рішень задачі. Кожне з нерівностей завдання ЛП визначає на координатній площині
При пошуку оптимального рішення задач лінійного програмування можливі наступні ситуації: існує єдине рішення задачі, існує нескінченна безліч рішень (альтернативний оптимум); ЦФ не обмежена; область допустимих рішень-єдина точка; завдання не має рішень. [3 c.55-57]
Будь-яка задача лінійного програмування, незалежно від виду запису, може бути приведена до стандартної і канонічній формі і вирішена симплексним методом, що у певному сенсі є універсальним методом ЛП. Алгоритм симплекс-методу носить ітераційний характер.
Симплекс-метод дозволяє переходити від одного допустимого базисного розв'язку до іншого, причому так, що значення цільової функції безперервно зростають. Алгоритми симплекс-методу дозволяють також встановити, чи є завдання ЛЗ розв'язною.
Перехід від одного базису до іншого дозволяє знаходити рішення майже всіх задач ЛП. Визначивши всі крайні точки, можна обчислити значення цільової функції і знайти оптимальне рішення. Проте для великих значень m і n це практично неможливо. [1 c.15]
Алгоритм розв'язання задачі ЛП табличним симплексом-методом складається з наступних етапів:
1. розраховують і заповнюють початкову симплекс-таблицю з допустимим одиничним базисом, включаючи індексний рядок.
2. знаходять дозволяє стовпець;
3. знаходять роздільну рядок;
4. розраховують методом Жордана-Гаусса всі параметри матриці;
5. аналізують отримані дані в індексному рядку.
Таблиці симплекс-методу необхідно будувати до тих пір, поки не буде отриманий оптимальний план. План буде вважатися оптимальним, якщо в останній індексному рядку симплекс-таблиці будуть лише нулі і позитивні числа. [1 c.20-22]
При побудові симплексного методу передбачалося, що всі опорні плани невироджені, що забезпечувало отримання оптимального плану за кінцеву кількість кроків. У випадку виродженого плану обчислення виробляють аналогічно, але в цьому випадку можливе повернення до старого базису, що приводь до так званого зациклення.
Метод штучного базису застосовується при наявності в обмеженні знаків "дорівнює", "більше або дорівнює", "менше або дорівнює" і є модифікацією табличного методу. Рішення системи виробляється шляхом введення штучних змінних зі знаком, що залежать від типу оптимуму, тобто для виключення з базису цих змінних останні вводяться в цільову функцію з великими негативними коефіцієнтами m, а в завдання мінімізації - з позитивними m. Таким чином, з вихідної виходить нова m - завдання.
Якщо в оптимальному вирішенні m - завдання немає штучних змінних, це рішення є оптимальне рішення вихідної задачі. Якщо ж в оптимальному вирішенні m - завдання хоч одна з штучних змінних буде відмінна від нуля, то система обмежень вихідної задачі несовместна і вихідна задача нерозв'язна.
В основу модифікованого симплекс - методу покладені такі особливості лінійної алгебри, які дозволяють у ході виконання завдання працювати з частиною матриці обмежень. Іноді метод називають методом зворотної матриці.
У процесі роботи алгоритму відбувається спонтанне звернення матриці обмежень по частинах, відповідними поточними базисним векторам. Зазначена здатність робить вельми привабливою машинну реалізацію обчислень внаслідок економії пам'яті під проміжні змінні і значного скорочення часу рахунку. Хороший для ситуацій, коли число змінних n значно перевищує число обмежень m.
У цілому, метод відображає традиційні риси загального підходу до вирішення завдань лінійного програмування, що включає в себе канонізацію умов завдання, розрахунок симплекс-різниць, перевірку умов оптимальності, прийняття рішень про корекцію базису і виключення Жордана-Гаусса.
Особливості полягають у наявності двох таблиць - основний і допоміжної, порядок їх заповнення та деякою специфічності розрахункових формул.
Кожній задачі лінійного програмування можна певним чином зіставити деяку іншу задачу, звану двоїстої або сполученої по відношенню до початкової або прямої задачі. Зіставляючи форми запису прямої і двоїстої задач, можна встановити між ними наступні взаємозв'язки:
1. якщо пряма задача є задачею максимізації, двоїста буде завданням мінімізації, і навпаки;
2. коефіцієнти цільової функції прямої задачі стають вільними членами обмежень двоїстої задачі;
3. вільні члени обмежень прямої задачі стають коефіцієнтами цільової функції двоїстої задачі;
4. матриця обмежень двоїстої задачі виходить шляхом транспортування матриці обмежень прямої задачі;
5. знаки нерівностей в обмеженнях змінюються на протилежні;
6. число обмежень прямої задачі дорівнює числу змінних двоїстої задачі, і навпаки.
Види математичних моделей двоїстих задач можуть бути представлені у таблиці (табл. 1.1).
Таблиця 1.1
Види математичних моделей двоїстих задач
| Вихідна задача | Двоїста задача |
| Несиметричні завдання | |
| Симетричні завдання | |
Якщо з пари двоїстих завдань одну володіє оптимальним планом, то й інша має рішення, причому для екстремальних значень лінійних функцій виконується певне співвідношення (формула 1.10). Якщо лінійна функція одним із завдань не обмежена, то інша не має рішення.
Якщо пряма (а значить, і двоїста) завдання вирішити, то в кожній парі подвійних умов одне є вільним, а інше закріпленим. Будь-яке з умов називається вільним, якщо воно виконується як суворе нерівність хочаб для одного оптимального вектора. Умова називається закріпленим, якщо воно виконується як рівність для всіх оптимальних векторів.
Двоїсту задачу вигідніше вирішувати, ніж пряму, якщо в прямій задачі при малій кількості змінних є велика кількість обмежень. [2, c 70-71]
Симплексний метод дозволяє поряд з отриманням рішення прямої задачі отримувати і рішення двоїстої задачі. Цей результат і лежить в основі двоїстого симплексного методу розв'язання задачі. Суть методу полягає в такому послідовному переборі кутових точок допустимого безлічі Q 0 двоїстої задачі, при якому значення цільової функції зростає, тобто в застосуванні симплексного методу до вирішення двоїстої задачі. Будемо припускати, що завдання невироджений, тобто кожної кутової точці безлічі Q 0 відповідає квадратна невироджена система рівнянь розмірності m, матрицю яку і називають двоїстим базисом прямої задачі. Разом з тим двоїстий симплекс-метод можна застосовувати при вирішенні задачі лінійного програмування, вільні члени системи рівнянь якої можуть бути будь-якими числами (при розв'язанні задачі симплексним методом ці числа передбачалися невід'ємними).
Відшукування рішення задачі двоїстим симплекс-методом включає в себе наступні етапи:
1. Знаходять псевдоплан завдання.
2. Перевіряють цей псевдоплан на оптимальність. Якщо псевдоплан оптимальний, то знайдене рішення задачі. В іншому разі або встановлюють нерозв'язність завдання, або переходять до нового псевдоплану.
3. Вибирають роздільну рядок за допомогою визначення найбільшого за абсолютною величиною негативного числа стовпця вектора Р 0 і дозволяє стовпець з допомогою знаходження найменшого за абсолютною величиною відносини елементів (m +1)-й рядка до відповідних негативним елементам роздільної рядка.
4. Знаходять новий псевдоплан і повторюють всі дії починаючи з другого етапу.
Значна частина економічних задач, які відносяться до завдань лінійного програмування, вимагає цілочисельного рішення. До них належать завдання, у яких змінні величини означають кількість одиниць неподільної продукції, наприклад розподіл виробничих завдань між підприємствами, розкрій матеріалів, завантаження обладнання, розподіл судів по лініях, літаків по рейсах, а також завдання з виробництва неподільної продукції. Якщо одиниця становить малу частину всього обсягу виробництва, то оптимальне рішення знаходять звичайним симплексним методом, округляючи його до цілих одиниць, виходячи зі змісту завдання. В іншому випадку округлення може призвести до вирішення, далекому від оптимального цілочисельного рішення.
Завдання цілочисельного програмування формулюється так само, як і завдання лінійного програмування, але включається додаткова вимога, що полягає в тому, що значення змінних, складових оптимальне рішення, повинні бути цілими невід'ємними числами.
Метод вирішення таких завдань, запропонований Гоморі, заснований на симплексному методі і полягає в наступному. Симплексним методом знаходиться оптимальний план завдання без урахування умови целочисленности. Якщо оптимальний план цілочисельний, то обчислення закінчують; якщо ж оптимальний план містить хоча б одну дробову компоненту X i, то накладають додаткове обмеження, що враховує целочисленость компонент плану, і обчислення симплексним методом продовжують до тих пір, поки або буде знайдений цілочисельний оптимальний план, або доведено, що задача не має цілочисельних оптимальних планів. [3 c.122-123]
Особливо широке поширення лінійне програмування отримало в економіці, так як дослідження залежностей між величинами, зустрічаються у багатьох економічних задачах, призводить до лінійної функції з лінійними обмеженнями, накладеними на невідомі.
2. Області застосування і обмеження використання лінійного програмування для вирішення економічних завдань
Особливо широке застосування методи і моделі лінійного програмування отримали при вирішенні завдань економії ресурсів (вибір ресурсозберігаючих технологій, складання сумішей, розкрій матеріалів, виробничо-транспортних та інших завдань). [2, c.92]Розглянемо постановку задачі про найкращому використанні ресурсів. Нехай деяка виробнича одиниця (цех, завод, об'єднання і т. д.), виходячи з кон'юнктури ринку, технічних чи технологічних можливостей і наявних ресурсів, може випускати n різних видів продукції (товарів), відомих під номерами, що позначаються індексом j
Так як
Щоб шуканий план
У модель задачі про найкращому використанні ресурсів входять: цільова функція (формула 2.3), система обмежень (формула 2.4) та умови невід'ємності (формула 2.5)
Так як змінні
У різних галузях народного господарства виникає проблема складання таких робочих сумішей на основі вихідних матеріалів, які забезпечували б одержання кінцевого продукту, що володіє певними властивостями. До цієї групи завдань належать завдання про вибір дієти, складанні кормового раціону в тваринництві, шихт в металургії, горючих і мастильних сумішей в нафтопереробній промисловості, сумішей для отримання бетону в будівництві і т. д.. Високий рівень витрат на вихідні сировинні матеріали і необхідність підвищення ефективності виробництва висуває на перший план наступне завдання: одержати продукцію з заданими властивостями при найменших витратах на вихідні сировинні матеріали.
Сутність задачі про оптимальний розкрої полягає в розробці таких технологічно допустимих планів розкрою, при яких виходить необхідний комплект заготовок, а відходи (по довжині, площі, обсягом, масою або вартості) зводяться до мінімуму. Більш складні постановки ведуть до завдань цілочисельного програмування.
Загальна постановка транспортної задачі полягає у визначенні оптимального плану перевезень деякого однорідного вантажу з m пунктів відправлення
Зазвичай вихідні дані транспортної задачі записують у вигляді таблиці, яку називають матрицею планування. (Табл. 2.1).
Таблиця 2.1
Матриця планування ТЗ
| Постачальники | Споживачі | Запаси | |||
| B1 | B2 | ... | Bn | ||
| A1 | C11 | C12 | ... | C1n | a1 |
| A2 | C21 | C22 | ... | C2n | a2 |
| ... | ... | ... | ... | ... | ... |
| Am | Cm1 | Cm2 | ... | Cmn | am |
| b1 | b2 | ... | bn | ||
Якщо загальна потреба у вантажі в пунктах призначення дорівнює запасу вантажу в пунктах відправлення, то модель такої транспортної задачі називається закритою. Якщо ж зазначена умова не виконується, то модель транспортної задачі називається відкритою.
У разі перевищення запасу над потребою, вводиться фіктивний (n +1)-й пункт призначення з потребою (формула 2.10) і відповідні тарифи вважаються рівними нулю. Аналогічно, у разі, якщо потреби перевищують кількість запасів, також вводиться фіктивний (m +1)-й пункт відправлення з запасом вантажу і тарифи покладаються рівними нулю (формула 2.11). Цим завдання зводиться до звичайної транспортної задачі, з оптимального плану якої виходить оптимальний план вихідної задачі.
Як і для будь-якої задачі лінійного програмування, оптимальний план транспортної задачі є і опорним планом. Опорний план є допустимим рішенням ТЗ і використовується в якості початкового базисного рішення при знаходженні оптимального рішення методом потенціалів. Існує чотири методи знаходження опорних планів:
1. метод північно-західного кута;
2. метод мінімального елемента;
3. метод подвійного переваги;
4. метод штрафів (Фогеля).
"Якість" опорних планів, отриманих цими методами, розрізняється: у загальному випадку метод Фогеля дає найкраще рішення (часто оптимальне), а метод північно-західного кута-найгірше.
Всі існуючі методи знаходження опорних планів відрізняються тільки способом вибору клітки для заповнення. Саме заповнення відбувається однаково незалежно від використовуваного методу. Слід пам'ятати, що перед знаходженням опорного плану транспортна задача повинна бути збалансована.
У методі північно-західного кута з усіх не викреслених клітин вибирається сама ліва і верхня (північно-західна) клітина. Іншими словами, на кожному кроці вибирається перша з залишилися не викреслених рядків і перший з залишилися не викреслених стовпчиків.
Для того щоб заповнити клітку (i, j), необхідно порівняти поточний запас товару в розглянутій i-му рядку з поточною потребою в розглянутому j-му стовпці. Знаходження опорного плану продовжується до тих пір, поки не будуть викреслені всі рядки і стовпці. [3 c.137]
У методі мінімального елемента першого клітиною вибирають клітку з найменшою сумою доставки і заповнюють її максимально можливим вантажем.
Якщо таблиця вартостей велика, то перебір всіх елементів скрутний. У цьому випадку використовують метод подвійного переваги, суть якого полягає в наступному: у кожному рядку і кожному стовпці відзначають «V» найменшу вартість, а потім клітини з подвійним символом «VV» заповнюють з урахуванням найменшої вартості. Потім розподіляють перевезення по клітках, зазначеним знаком «V». У частині таблиці перевезення розподіляють за найменшою вартістю.
На кожному кроці методу Фогеля для кожної i-го рядка обчислюються штрафи, як різниця між двома найменшими тарифами рядка. Таким же чином обчислюються штрафи для кожного j-го стовпця. Після чого вибирається максимальний штраф з усіх штрафів рядків і стовпців. У рядку або стовпці, відповідному обраному штрафу, для заповнення вибирається не викреслена клітка з мінімальним тарифом. Якщо існує кілька однакових за величиною максимальних штрафів у матриці, то у відповідних рядках або стовпцях вибирається одна не викреслена клітка з мінімальним тарифом.
Якщо клітин з мінімальним тарифом також кілька, то з них вибирається клітина (i, j) з максимальним сумарним штрафом, тобто сумою штрафів за i-му рядку і j-му стовпцю.
Якщо план транспортної задачі є оптимальним, то йому відповідає система з m + n чисел Ui і Vj, які відповідають умовам: Ui + Vj = Cij для зайнятих клітин і Ui + Vj ≤ Сij у вільних клітинах. Числа Ui і Vj називаються потенціалами відповідно постачальників і споживачів. При вирішенні одному невідомому потенціалу надається довільне значення. [3 c.141]
3. Оптимізація прибутку із застосуванням методу лінійного програмування
3.1 Постановка завдання і формування оптимізаційної моделі
Підприємство реалізує товари трьох груп. Відомі нормативи витрат ресурсів A ij в розрахунку на одиницю товару та обмеження щодо розташовуваним ресурсів, які наведені в (табл. 3.1)Таблиця 3.1
Нормативи витрат ресурсів і обмежень
| Ресурси | Нормативи витрат ресурсів з продажу товарів | ||
| Aj | Bj | Cj | |
| Робочий час, чел.ч. | А11 = 0,1 | А12 = 0,2 | А13 = 0,4 |
| Площа торгових приміщень, м2 | А21 = 0,05 | А22 = 0,02 | А23 = 0,02 |
| Витрати обігу на од. товару, руб. | А31 = 3 | А32 = 1 | А33 = 2 |
| Дохід на одиницю товару, руб. | С1 = 3 | С2 = 5 | С3 = 4 |
| План продажу, од. | X1 | X2 | X3 |
Необхідно скласти оптимальний план товарообігу за критерієм максимуму прибутку.
Це класична задача лінійного програмування про найкращому використанні ресурсів. У цьому завданню також буде присутній цілочисельне програмування, тому що продукція неподільна.
Складемо оптимізаційну модель. Запишемо цільову функцію (формула 3.1), обмеження на кількість ресурсів (формула 3.2) та умови невід'ємності (формула 3.3)
3.2 Розрахунок і аналіз результатів оптимізації прибутку
Початковий опорний план симплекс методом знаходиться тільки тоді, коли в системі обмеження ліві і праві частини рівняння рівні. Тому необхідно перейти від нерівностей до равенствам, додаючи до лівими частинами невід'ємні додаткові змінні (додатковим змінним в лінійній функції відповідають коефіцієнти рівні нулю). Отже, цільова функція (формула 3.4), система обмежень (формула 3.5) та умови невід'ємності (формула 3.6) візьмуть інший вигляд.Вирішуємо задачу симплексним методом. Розрахунки виробляємо в симплекс таблиці. (Див. табл. 3.2)
Таблиця 3.2
Перша симплексна таблиця
| Базис | Cj баз. | B | X1 | X2 | X3 | X4 | X5 | X6 |
| 3 | 5 | 4 | 0 | 0 | 0 | |||
| X4 | 0 | 1300 | 0.1 | 0.2 | 0.4 | 1 | 0 | 0 |
| X5 | 0 | 140 | 0.05 | 0.02 | 0.02 | 0 | 1 | 0 |
| X6 | 0 | 8200 | 3 | 1 | 2 | 0 | 0 | 1 |
| П (x) | 0 | -3 | -5 | -4 | 0 | 0 | 0 | |
Таблиця 3.2
Друга симплексна таблиця
| Базис | Cj баз. | B | X1 | X2 | X3 | X4 | X5 | X6 |
| 3 | 5 | 4 | 0 | 0 | 0 | |||
| X2 | 5 | 6500 | 0.5 | 1 | 2 | 5 | 0 | 0 |
| X5 | 0 | 10 | 0.04 | 0 | -0.02 | -0.1 | 1 | 0 |
| X6 | 0 | 1700 | 2.5 | 0 | 0 | -5 | 0 | 1 |
| П (x) | 32500 | -0.5 | 0 | 6 | 25 | 0 | 0 | |
Цей план теж не оптимальний, так як у рядку «прибуток» ще є негативні елементи. Знову знаходимо направляючий стовпець і рядок. Направляючий стовпець - четвертий, напрямна рядок - друга. Дозволяє елемент дорівнює 0.04. Будуємо третій сімплексною таблицю. (Табл. 3.4)
Таблиця 3.3
Третя симплексна таблиця
У результаті проведення двох ітерацій отримуємо оптимальний план 
У підсумковому рядку «прибуток» на перетині з стовпцями X 4 X 5 X 6 можна знайти двоїсті оцінки ресурсів, які покажуть, який прибуток приносить одна одиниця кожного наявного ресурсу.
Прибуток від одного людино-години робочого часу складе 23 рубля 75 копійок. Прибуток від одного квадратного метра торгових приміщень дорівнює 12 рублям 50 копійкам, а третій ресурс (витрати обігу на одиницю товару) використано не повністю і прибуток від нього дорівнює 0 рублям.
Відповідь: Підприємству необхідно реалізовувати 250 одиниць товару першої групи і 6375 одиниць товару другої групи, тоді залишки третього ресурсу (витрати обігу на одиницю товару) складуть 1075 рублів. При цьому максимальний дохід буде дорівнює 32625 рублів.
Завдання математичного програмування знаходять застосування в різних областях людської діяльності, де необхідний вибір одного з можливих образів дій (програм дій), наприклад, при вирішенні проблем управління і планування виробничих процесів, у проектуванні та перспективному плануванні, у військовій справі і т.д.
Значне число завдань, що виникають у суспільстві, пов'язане з керованими явищами, тобто з явищами, регульованими на основі свідомо прийнятих рішень. При тому обмеженому обсязі інформації, який був доступний на ранніх етапах розвитку суспільства, приймалося оптимальне в деякому сенсі рішення на підставі інтуїції і досвіду, а потім, зі зростанням обсягу інформації про досліджуваному явищі, - за допомогою ряду прямих розрахунків. Так відбувалося, наприклад, створення календарних планів роботи промислових підприємств.
Зовсім інша картина виникає на сучасному промисловому підприємстві з багатосерійним і багатономенклатурним виробництвом, коли обсяг вхідної інформації настільки великий, що його обробка з метою прийняття певного рішення неможлива без застосування комп'ютерів. Ще більші труднощі виникають у зв'язку із завданням про прийняття найкращого рішення. Проблема прийняття рішень в дослідженні операцій нерозривно пов'язана з процесом моделювання.
Перший етап процесу моделювання полягає в побудові якісної моделі. Другий етап - побудова математичної моделі paccматріваемой проблеми. Цей етап включає також побудова цільової функції, тобто такий числової характеристики, більшого (або меншого) значенню якої відповідає краща ситуація з точки зору приймає рішення. Отже, в результаті цих двох етапів формується відповідна математична задача.
Третій етап - дослідження впливу змінних на значення цільової функції. Цей етап передбачає володіння математичним апаратом для розв'язування математичних задач, що виникають на другому етапі процесу прийняття рішення.
Четвертий етап - зіставлення результатів обчислень, отриманих на третьому етапі, з модельованим об'єктом, тобто експертна перевірка результатів (критерій практики). Таким чином, на цьому етапі встановлюється ступінь адекватності моделі і модельованого об'єкта в межах точності вихідної інформації.
Широкий клас задач управління складають такі екстремальні завдання, в математичних моделях яких умови на змінні задаються рівностями і нерівностями. Теорія і методи вирішення цих завдань якраз і складають зміст математичного програмування.
2. Карманов В.Г. Математичне програмування: навчальний посібник для студентів вузів. - М.: Фізматліт, 2001. - 264с.
3. Кузнєцов А.В. Математичне програмування: навчальний посібник для вузів. - М.: Вища школа, 1976. - 352с.
4. Мочалов І.А. Нечітке лінійне програмування. / / Промислові АСУ та контролери. - 2006. - № 10. - С.26-29.
5. Пашутін С. Оптимізація витрат і технологія формування оптимального асортименту. / / Управління персоналом. - 2005. - № 5. - С.20-24.
Таблиця 3.3
Третя симплексна таблиця
| Базис | Cj баз. | B | X1 | X2 | X3 | X4 | X5 | X6 |
| 3 | 5 | 4 | 0 | 0 | 0 | |||
| X2 | 5 | 6375 | 0 | 1 | 2.25 | 6.25 | -12.5 | 0 |
| X1 | 3 | 250 | 1 | 0 | -0.5 | -2.5 | 25 | 0 |
| X6 | 0 | 1075 | 0 | 0 | 1.25 | 1.25 | -62.5 | 1 |
| П (x) | 32625 | 0 | 0 | 5.75 | 23.75 | 12.5 | 0 | |
У підсумковому рядку «прибуток» на перетині з стовпцями X 4 X 5 X 6 можна знайти двоїсті оцінки ресурсів, які покажуть, який прибуток приносить одна одиниця кожного наявного ресурсу.
Прибуток від одного людино-години робочого часу складе 23 рубля 75 копійок. Прибуток від одного квадратного метра торгових приміщень дорівнює 12 рублям 50 копійкам, а третій ресурс (витрати обігу на одиницю товару) використано не повністю і прибуток від нього дорівнює 0 рублям.
Відповідь: Підприємству необхідно реалізовувати 250 одиниць товару першої групи і 6375 одиниць товару другої групи, тоді залишки третього ресурсу (витрати обігу на одиницю товару) складуть 1075 рублів. При цьому максимальний дохід буде дорівнює 32625 рублів.
Висновок
Зміст математичного програмування становлять теорія і методи розв'язання задач про знаходження екстремумів функцій на множинах, що визначаються лінійними і нелінійними обмеженнями (равенствами і нерівностями). Математичне програмування є одним з розділів науки про дослідження операцій.Завдання математичного програмування знаходять застосування в різних областях людської діяльності, де необхідний вибір одного з можливих образів дій (програм дій), наприклад, при вирішенні проблем управління і планування виробничих процесів, у проектуванні та перспективному плануванні, у військовій справі і т.д.
Значне число завдань, що виникають у суспільстві, пов'язане з керованими явищами, тобто з явищами, регульованими на основі свідомо прийнятих рішень. При тому обмеженому обсязі інформації, який був доступний на ранніх етапах розвитку суспільства, приймалося оптимальне в деякому сенсі рішення на підставі інтуїції і досвіду, а потім, зі зростанням обсягу інформації про досліджуваному явищі, - за допомогою ряду прямих розрахунків. Так відбувалося, наприклад, створення календарних планів роботи промислових підприємств.
Зовсім інша картина виникає на сучасному промисловому підприємстві з багатосерійним і багатономенклатурним виробництвом, коли обсяг вхідної інформації настільки великий, що його обробка з метою прийняття певного рішення неможлива без застосування комп'ютерів. Ще більші труднощі виникають у зв'язку із завданням про прийняття найкращого рішення. Проблема прийняття рішень в дослідженні операцій нерозривно пов'язана з процесом моделювання.
Перший етап процесу моделювання полягає в побудові якісної моделі. Другий етап - побудова математичної моделі paccматріваемой проблеми. Цей етап включає також побудова цільової функції, тобто такий числової характеристики, більшого (або меншого) значенню якої відповідає краща ситуація з точки зору приймає рішення. Отже, в результаті цих двох етапів формується відповідна математична задача.
Третій етап - дослідження впливу змінних на значення цільової функції. Цей етап передбачає володіння математичним апаратом для розв'язування математичних задач, що виникають на другому етапі процесу прийняття рішення.
Четвертий етап - зіставлення результатів обчислень, отриманих на третьому етапі, з модельованим об'єктом, тобто експертна перевірка результатів (критерій практики). Таким чином, на цьому етапі встановлюється ступінь адекватності моделі і модельованого об'єкта в межах точності вихідної інформації.
Широкий клас задач управління складають такі екстремальні завдання, в математичних моделях яких умови на змінні задаються рівностями і нерівностями. Теорія і методи вирішення цих завдань якраз і складають зміст математичного програмування.
Список літератури
1. Берюхова Т. Н. Банк виробничих завдань у розрахунках на ЕОМ: навчальний посібник. - Тюмень.: ТюмІІ, 1992. - 124с.2. Карманов В.Г. Математичне програмування: навчальний посібник для студентів вузів. - М.: Фізматліт, 2001. - 264с.
3. Кузнєцов А.В. Математичне програмування: навчальний посібник для вузів. - М.: Вища школа, 1976. - 352с.
4. Мочалов І.А. Нечітке лінійне програмування. / / Промислові АСУ та контролери. - 2006. - № 10. - С.26-29.
5. Пашутін С. Оптимізація витрат і технологія формування оптимального асортименту. / / Управління персоналом. - 2005. - № 5. - С.20-24.