• § 1. Завдання лінійного програмування і властивості
  • 1.2 Властивості рішень.
  • § 2. Графічний спосіб вирішення ЗЛП.
  • § 3. Симплексних метод.
  • Теорема.
  • Ознаки оптимальності.
  • § 4. Поняття двоїстості.
  • Теорема. (критерій оптимальності Канторовича)
  • Теорема. (мала теорема подвійності)
  • Теорема. (про що доповнює нежорсткості)
  • 5.2 Завдання про сумішах.
  • 5.3 Завдання про розкрої матеріалів.
  • 5.4 Транспортна задача.
  • 5.5 Завдання про розміщення замовлення.


  • Дата конвертації23.03.2017
    Розмір68.06 Kb.
    Типреферат

    Скачати 68.06 Kb.

    Аналіз економічних завдань симплексним методом

    Вступ.

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

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

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

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

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

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

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

    Початок лінійному програмуванню було покладено в 1939 р радянським математиком-економістом Л. В. Канторовичем в роботі «Математичні методи організації і планування виробництва». Поява цієї роботи відкрило новий етап в застосуванні математики в економіці. Через десять років американський математик Дж. Данциг розробив ефективний метод вирішення даного класу задач - симплекс-метод. Загальна ідея симплексного методу (методу послідовного поліпшення плану) для вирішення ЗЛП полягає в наступному:

    1) вміння знаходити початковий опорний план;

    2) наявність ознаки оптимальності опорного плану;

    3) вміння переходити до нехудшему опорного плану.

    § 1. Завдання лінійного програмування і властивості її рішень.

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

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

    Форми запису задачі лінійного програмування:

    Загальним завданням лінійного програмування називають завдання

    (1)

    при обмеженнях

    (2)

    (3)

    (4)

    (5)

    - довільні (6)

    де - Задані дійсні числа; (1) - цільова функція; (1) - (6) -обмеження;

    - План завдання.

    1.2 Властивості рішень.

    Нехай ЗПП представлена ​​в наступному записі:

    (7)

    (8)

    (9)

    Щоб завдання (7) - (8) мала рішення, системі її обмежень (8) повинна бути спільною. Це можливо, якщо r цієї системи не більше числа невідомих n. Випадок r> n взагалі неможливий. При r = n система має єдине рішення, яке буде при оптимальним. У цьому випадку проблема вибору оптимального рішення втрачає сенс. З'ясуємо структуру координат кутовий точки багатогранних рішень. нехай r містить базис - максимальну лінійно незалежну підсистему векторів, через яку будь-який вектор системи може бути виражений як її лінійна комбінація. Базисів, взагалі кажучи, може бути кілька, але не більше . Кожен з них складається точно з r векторів. Змінні ЗЛП, відповідні r векторах базису, називають, як відомо, базисними і позначають БП. Решта n - r змінних будуть вільними, їх позначають СП. Без обмеження спільності, будемо вважати, що базис складають перші m векторів . Цьому базису відповідають базисні змінні , А вільними будуть змінні .

    Якщо вільні змінні прирівняти нулю, а базисні змінні при цьому візьмуть невід'ємні значення, то отримане приватне рішення системи (8) називають опорним рішенням (планом).

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

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

    § 2. Графічний спосіб вирішення ЗЛП.

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

    Нехай дана задача

    (11)

    (12)

    (13)

    Дамо геометричну інтерпретацію елементів цього завдання. Кожне з обмежень (12), (13) задає на площині деяку полуплоскость. Напівплощина - опукле безліч. Але перетин будь-якого числа опуклих множин є опуклим безліччю. Звідси випливає, що область допустимих рішень задачі (11) - (13) є опукле безліч.

    Перейдемо до геометричної інтерпретації цільової функції.Нехай область допустимих рішень ЗЛП - непорожня множина, наприклад багатокутник .

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

    Знайдемо приватні похідні цільової функції по і

    (14)

    (15)

    Приватна похідна (14) ((15)) функції показує швидкість її зростання вздовж даної осі. отже, і - Швидкості зростання відповідно уздовж осей і . вектор називається градієнтом функції. Він показує напрямок найшвидшого зростання цільової функції:

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

    вектор перпендикулярний до прямих сімейства

    З геометричної інтерпретації елементів ЗЛП випливає наступний порядок її графічного рішення.

    1. З урахуванням системи обмежень будуємо область допустимих рішень

    2. Будуємо вектор найшвидшого зростання цільової функції - вектор градієнтного напрямку.

    3. Проводимо довільну лінію рівня

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

    5. Визначаємо оптимальний план і екстремальне значення цільової функції .

    § 3. Симплексних метод.

    Загальна ідея симплексного методу (методу послідовного поліпшення плану) для вирішення ЗЛП полягає

    1) вміння знаходити початковий опорний план;

    2) наявність ознаки оптимальності опорного плану;

    3) вміння переходити до нехудшему опорного плану.

    Нехай ЗЛП представлена ​​системою обмежень в канонічному вигляді:

    .

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

    Нехай система обмежень має вигляд

    Зведемо задачу до канонічного вигляду. Для цього додамо до лівих частинах нерівностей додаткові змінні . Отримаємо систему, еквівалентну вихідній:

    ,

    яка має кращий вигляд

    .

    У цільову функцію додаткові змінні вводяться з коефіцієнтами, рівними нулю .

    Нехай далі система обмежень має вигляд

    Зведемо її до еквівалентної вирахуванням додаткових змінних з лівих частин нерівностей системи. отримаємо систему

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

    Нехай вихідна ЗЛП має вигляд

    (1)

    (2)

    (3)

    причому жодне з обмежень не має кращою змінної. М-задача запишеться так:

    (4)

    (5)

    , , (6)

    Завдання (4) - (6) має кращий план. Її початковий опорний план має вигляд

    Якщо деякі з рівнянь (2) мають кращий вигляд, то в них не слід вводити штучні змінні.

    Теорема. Якщо в оптимальному плані

    (7)

    М-задачі (4) - (6) усі штучні змінні , То план є оптимальним планом вихідної завдання (1) - (3).

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

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

    Якщо в результаті застосування симплексного методу до розширеної задачі отримано оптимальний план, в якому все штучні змінні , То його перші n компоненти дають оптимальний план вихідної завдання.

    Теорема. Якщо в оптимальному плані М-задачі хоча б одна зі штучних змінних відмінна від нуля, то вихідна задача не має допустимих планів, т. Е. Її умови несумісні.

    3.1 Ознаки оптимальності.

    Теорема. Нехай вихідна задача вирішується на максимум. Якщо для деякого опорного плану всі оцінки невід'ємні, то такий план оптимальний.

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

    § 4. Поняття двоїстості.

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

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

    (1)

    (2)

    (3)

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

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

    1) загальну вартість відходів сировини купує організація прагне мінімізувати;

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

    Ці вимоги формалізуються у вигляді такої ЗЛП.

    Вимога 1 купує організації - мінімізація покупки: (4)

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

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

    (5)

    За змістом задачі оцінки не повинні бути негативними:

    (6)

    змінні називають подвійними оцінками або об'єктивно зумовленими оцінками.

    Завдання (1) - (3) і (4) - (6) називають парою взаємно двоїстих ЗПП.

    Між прямий і двоїстої завданнями можна встановити наступну взаємозв'язок:

    1. Якщо пряма задача на максимум, то двоїста до неї - на мінімум, і навпаки.

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

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

    4. Матриці обмежень прямої і двоїстої задач є транспоновану один до одного.

    5. Якщо пряма задача на максимум, то її система обмежень представляється у вигляді нерівностей типу . Двоїста задача вирішується на мінімум, і її система обмежень має вигляд нерівностей типу .

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

    7. Всі змінні в обох задачах невід'ємні.

    Теорема. Для будь-яких допустимих планів і прямий і двоїстої ЗЛП справедливо нерівність , Тобто

    (7) - основне нерівність теорії подвійності.

    Теорема. (критерій оптимальності Канторовича)

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

    Теорема. (мала теорема подвійності)

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

    §5. Основні теореми подвійності

    і їх економічний зміст

    Теорема.

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

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

    Теорема. (про що доповнює нежорсткості)

    Для того, щоб плани і пари двоїстих задач були оптимальними, необхідно і достатньо виконання умов:

    (1)

    (2)

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

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

    Теорема. (Про оцінки). Двоїсті оцінки показують приріст функції мети, викликане малим зміною вільного члена відповідного обмеження задачі математичного програмування, точніше

    (3)

    §6. Приклади економічних задач

    5.1 Завдання про найкращому використанні ресурсів. Нехай деяка виробнича одиниця (цех, завод, об'єднання і т. Д.), Виходячи з кон'юнктури ринку, технічних або технологічних можливостей і наявних ресурсів, може випускати n різних видів продукції (товарів), відомих під номерами, що позначаються індексом j . Її будемо позначати . Підприємство при виробництві цих видів продукції повинно обмежуватися наявними видами ресурсів, технологій, інших виробничих факторів (сировини, напівфабрикатів, робочої сили, обладнання, електроенергії та т. Д.). Всі ці види обмежуючих факторів називають інгредієнтами . Нехай їх число дорівнює m; пріпішем їм індекс i . Вони обмежені, і їх кількості рівні відповідно умовних одиниць.Таким чином, - Вектор ресурсів. Відома економічна вигода (міра корисності) виробництва продукції кожного виду, що обчислюється, скажімо, за відпускною ціною товару, його прибутковості, витрат виробництва, ступеня задоволення потреб і т. Д. Приймемо в якості такого заходу, наприклад, ціну реалізації

    , Т. Е. - Вектор цін. Відомі також технологічні коефіцієнти , Які вказують, скільки одиниць i-го ресурсу потрібно для виробництва одиниці продукції j-го виду. матрицю коефіцієнтів називають технологічної і позначають буквою А. маємо . позначимо через план виробництва, що показує, які види товарів потрібно проводити і в яких кількостях, щоб забезпечити підприємству максимум обсягу реалізації при наявних ресурсах.

    Так як - Ціна реалізації одиниці j'-й продукції, вартість реалізованих одиниць дорівнюватиме , А загальний обсяг реалізації

    Цей вислів - цільова функція, яку потрібно максимізувати.

    Так як - Витрата i-го ресурсу на виробництво одиниць j-й продукції, то, підсумувавши витрата i-го ресурсу на випуск всіх n видів продукції, отримаємо загальну витрату цього ресурсу, який не повинен перевищувати одиниць:

    Щоб шуканий план був реалізований, поряд з обмеженнями на ресурси потрібно накласти умову невід'ємності на обсяги випуску продукції:

    .

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

    (1)

    при обмеженнях:

    (2)

    (3)

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

    5.2 Завдання про сумішах.

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

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

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

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

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

    5.5 Завдання про розміщення замовлення.

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

    §7. Аналіз завдання про оптимальне використання сировини.

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

    ресурси

    Продукція, що випускається

    Об `єм

    ресурсів

    Трудові ресурси, чол-год

    4

    2

    2

    8

    4800

    Напівфабрикати, кг

    2

    10

    6

    0

    2400

    Верстатне обладнання, верстато-год

    1

    0

    2

    1

    1500

    Ціна одиниці продукції, р.

    65

    70

    60

    120

    Рішення.

    нехай - Обсяги продукції планований до випуску; - Сума очікуваної виручки.

    Математична модель пря мій завдання:

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

    За умовами прикладу знайти:

    1. Асортимент продукції, що випускається, що забезпечує підприємству максимум реалізації (максимум виручки)

    2. Оцінки ресурсів, використовуваних при виробництві продукції.

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

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

    Основні змінні показують, що продукцію і випускати недоцільно, а продукції слід зробити 400 од., - 500 од.

    додаткові змінні і показують, що ресурси використовуються повністю , А ось рівність свідчить про те, що 200 одиниць продукції залишилося невикористаним.

    Номери ит.

    БП

    Сб

    65

    70

    60

    120

    0

    0

    0

    0

    0

    4800

    4

    2

    2

    8

    1

    0

    0

    0

    2400

    2

    10

    6

    0

    0

    1

    0

    0

    1500

    1

    0

    2

    1

    0

    0

    1

    0

    -65

    -70

    -60

    -120

    0

    0

    0

    1

    120

    600

    1/2

    1/4

    1/4

    1

    1/8

    0

    0

    0

    2400

    2

    0

    6

    0

    0

    1

    0

    0

    900

    1/2

    -1/4

    7/4

    0

    -1/8

    0

    1

    72000

    -5

    -40

    -30

    0

    15

    0

    0

    2

    120

    500

    5/12

    -1/6

    0

    1

    1/8

    -1/24

    0

    60

    400

    1/3

    5/3

    1

    0

    0

    1/6

    0

    0

    200

    -1/12

    -19,6

    0

    0

    -1/8

    -7/24

    1

    84000

    5

    10

    0

    0

    15

    5

    0

    Випишемо з табліци2. Компоненти оптимального плану двоїстої задачі - двоїсті оцінки. У канонічної формі прямої задачі змінні - Є вільними, а додаткові змінні - Базисними. У канонічної формі двоїстої завдання вільними будуть змінні - А базисними

    Відповідність між змінними набуде вигляду

    З огляду на це відповідність, випишемо з індексного рядка останньої ітерації компоненти шуканого плану - Двоїсті оцінки.

    min f = max Z = 84000.

    Запишемо це нерівність в розгорнутій формі:

    48000 * 15 + 2400 * 5 + 1500 * 0 = 65 * 0 + 70 * 0 + 60 * 400 + 120 * 500

    З огляду на, що компонети є оцінки ресурсів укладаємо:

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

    Тепер встановимо ступінь дефіцитності використовуваних ресурсів і обгрунтуємо рентабельність оптимального плану.

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

    0 + 2-400 + 500 = 1300 <1500. Це означає, що витрата ресурсу менше його запасу, т. е. ресурс надлишковий. Саме тому в оптимальному плані двоїстої задачі оцінка цього ресурсу дорівнює нулю.

    А ось оцінки і ресурсів і виражаються позитивними числами 15 і 5, що свідчить про недостатність цих ресурсів: вони при оптимальному плані використовуються повністю. Справді, обмеження по цих ресурсів виконуються як строгі рівності: 4.0 + 2.0 + 2.400 + 8.500 = 4800, 2-0 + 10.0 + 6.400 = 2400.

    Оскільки 15> 5, ресурс вважається більш дефіцитним, ніж ресурс .

    На основі теореми (про що доповнює нежорсткості) неважко пояснити, чому не увійшла в оптимальний план продукція і : Перше і друге обмеження двоїстої задачі виконуються як строгі нерівності: 4-15 + 2-5 + 0> 65, 2-15 + 10 * 5> 70.

    Це означає, що оцінки ресурсів, що витрачаються на виготовлення одиниці продукції і , Перевищують оцінки одиниці цієї продукції. Зрозуміло, що таку продукцію випускати підприємству невигідно. Що ж стосується продукції і , То випуск її виправданий, оскільки оцінка витрачених ресурсів збігається з оцінкою виробленої продукції: 2 * 15 + + 6 * 5 + 2 * 0 = 60, 8 * 15 + 0 = 120.

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

    Розглянемо можливість подальшого вдосконалення оптимального асортименту продукції, що випускається.

    Вище встановлено, що ресурси і є дефіцитними. У зв'язку з цим на основі теореми (про оцінки) можна стверджувати, що на кожну одиницю ресурсу , Введену додатково у виробництво, буде отримана додаткова виручка , Чисельно рівна . Справді, при отримуємо . З тих же причин кожна додаткова одиниця ресурсу забезпечить приріст виручки, що дорівнює 5 р. Тепер стає зрозуміло, чому ресурс вважається більш дефіцитним в порівнянні з ресурсом : Він може сприяти отриманню більшої виручки.

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

    З'ясуємо економічний сенс оцінок продукції , , , .

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

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

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

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

    §8. Програма та розрахунки.

    {Програма складена для вирішення завдання лінійного програмування

    симплексним методом}

    uses crt;

    const n = 2; {число невідомих вихідної задачі}

    m = 3; {число обмежень}

    m1 = 0; {останній рядок рівності}

    m2 = 1; {останній рядок нерівностей виду> =}

    label 5,15,20,10;

    var b, cb: array [1..m] of real; c, x, e: array [1..50] of real; a: array [1..m, 1..50] of real;

    s0, max, mb, s1: real; i, j, k, i0, j0, m21, nm1, n1: integer; Bi: array [1..m] of integer;

    begin

    clrscr;

    writeln;

    writeln ( 'Симплексних метод вирішення задачі лінійного програмування:');

    writeln;

    writeln ( 'Проведемо деякі перетворення з цим завданням:');

    writeln;

    writeln ( 'Підготуйте матрицю: спочатку рівності, потім нерівності виду> = і нерівності виду <=;');

    writeln ( 'Цільова функція повинна бути на мінімум (привести її до такого виду);');

    writeln ( 'Вектор b повинен складатися тільки з позитивних елементів (привести його до та- кому увазі);');

    writeln ( 'Введіть матрицю А', m, '*', n, 'через підрядник:');

    for i: = 1 to m

    do begin for j: = 1 to n

    do read (a [i, j]);

    readln

    end;

    writeln ( 'Введіть у вигляді рядка вектор b, що складається з', m, 'компонент:');

    for i: = 1 to m

    do read (b [i]);

    writeln ( 'Введіть тепер вектор с, що складається з', n, 'компонент:');

    for i: = 1 to n

    do read (c [i]);

    m21: = m2-m1 + n; nm1: = n + m-m1; n1: = n + m-m1 + m2;

    for i: = 1 to m

    do for j: = n + 1 to n1

    do a [i, j]: = 0;

    {Перехід до рівності в нерівності> =}

    for i: = m1 + 1 to m2

    do a [i, n + i-m1]: = - 1;

    {Перехід до рівності в нерівності <=}

    for i: = m2 + 1 to m

    do a [i, m21 + i-m2]: ​​= 1;

    {Створення штучного базису}

    for i: = 1 to m2

    do a [i, nm1 + i]: = 1;

    {Введення mb в вектор з}

    mb: = 12345;

    for i: = n + 1 to nm1

    do c [i]: = 0;

    for i: = nm1 + 1 to n1

    do c [i]: = mb;

    {Виписати cb}

    for i: = 1 to m2

    do begin cb [i]: = mb; Bi [i]: = nm1 + i end;

    for i: = m2 + 1 to m

    do begin Bi [i]: = m21 + i-m2;

    cb [i]: = 0;

    end;

    for i: = 1 to n1

    do x [i]: = 0;

    writeln ( 'Рішення завдання:');

    {Застосовуємо симплексний метод, обчислюємо оцінки}

    5: for j: = 1 to n1

    do begin s0: = 0;

    for i: = 1 to m

    do s0: = s0 + cb [i] * a [i, j];

    e [j]: = s0-c [j]

    end;

    max: = e [1]; j0: = 1;

    for i: = 2 to n1

    do if e [i]> max

    then begin max: = e [i];

    j0: = i

    end;

    {Отримали стовпець з максимальною оцінкою}

    if max <= 0

    then begin for i: = 1 to m

    do x [Bi [i]]: = b [i];

    goto 15

    end;

    s1: = a [1, j0];

    for i: = 2 to m

    do if s1

    then s1: = a [i, j0];

    if s1 <= 0

    then goto 10;

    s1: = mb;

    for i: = 1 to m

    do if a [i, j0]> 0

    then if s1> b [i] / a [i, j0]

    then begin

    s1: = b [i] / a [i, j0];

    i0: = i

    end;

    {Головний елемент a [i0, j0]}

    s0: = a [i0, j0]; Bi [i0]: = j0;

    for j: = 1 to n1

    do a [i0, j]: = a [i0, j] / s0;

    b [i0]: = b [i0] / s0;

    for i: = 1 to m

    do if i <> i0

    then begin s1: = - a [i, j0];

    b [i]: = b [i] + b [i0] * s1;

    for j: = 1 to n1

    do a [i, j]: = a [i, j] + a [i0, j] * s1

    end;

    cb [i0]: = c [j0];

    goto 5;

    10: writeln ( 'Ні оптимального плану, функція необмежена');

    goto 20;

    {Перегляд позов. змінних}

    15: for i: = nm1 + 1 to n1

    do if x [i]> 0

    then begin writeln ( 'Порожня множина планів');

    goto 20

    end;

    for i: = 1 to n

    do writeln ( 'x [', i, '] =', x [i]: 7: 4);

    20: readkey

    end.

    зміст

    Введення .......................................................................................... 1

    §1. Завдання лінійного програмування і властивості її рішень ................ ... 4

    §2. Графічний спосіб вирішення

    задачі лінійного програмування .............................................. ... 6

    §3. Симплексний метод ..................................................................... .8

    §4. Поняття двоїстості ............................................................... .11

    §5. Основні теореми подвійності

    і їх економічний зміст ................................................. ...... 14

    §6. Приклади економічних задач ...................................................... ..16

    §7. Аналіз завдання про оптимальне використання сировини ........................... 19

    §8. Програма та розрахунки .................................................................. ..25