Реферати

Реферат: Аналіз економічних задач симплексним методом

Соціальні мережі як інструмент PR діяльності на прикладі соціальної мережі "У Контакті". Поняття "соціальна мережа" і можливості PR у соціальних мережах. Загальні принципи роботи віртуальних соціальних мереж. Аналіз змісту групи "Турфирми MIRACLE TRAVEL". Аналіз групи в соціальній мережі "У Контакті" косметичної компанії "Орифлейм".

Банківська система як інститут ринкової економіки. Сутність і функції банківської системи. Етапи становлення, проблеми і перспективи розвитку банківської системи Росії. Оцінка ефективності функціонування банківської системи країни, з погляду застосовуваних нею фінансово-кредитних інструментів.

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

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

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

Введення.

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

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

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

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 < n. У цьому випадку система векторів містить базис - максимальну лінійно незалежну підсистему векторів, через яку будь-який вектор системи може бути виражений як її лінійна комбінація. Базисів, взагалі говорячи, може бути декілька, але не більш. Кожний з них складається точно з r векторів. Змінні ЗЛП, відповідні r векторам базису, називають, як відомо, базиснимії означають БП. Інші n - r змінних будутсвободними, їх означають СП. Не обмежуючи спільності, будемо вважати, що базис складають перші m векторів. Цьому базису відповідають базисні змінні, а вільними будуть змінні.

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

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

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

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

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

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

(11)

(12)

(13)

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

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

Виберемо довільне значення цільової функції. Отримаємо. Це рівняння прямої лінії. У точках прямойNМцелевая функція зберігає одне і те ж постійне значення. Вважаючи в рівності (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;з, х, е: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 (з[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 з[i]:=0;

for i:=nm1+1 to n1

do з[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 х[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];

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

end;

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

for i:=2 to n1

do if е[i] > max

then begin max:=е[i];

j0:=i

end;

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

if max <=0

then begin for i:=1 to m

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

goto 15

end;

s1:=a[1, j0];

for i:=2 to m

do if s1 <a[i, j0]

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]:=з[j0];

goto 5;

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

goto 20;

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

15: for i:=nm1+1 to n1

do if х[i] > 0

then begin writeln(' Пуста безліч планів');

goto 20

end;

for i:=1 to n

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

20:readkey

end.

Зміст

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

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

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

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

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

з4. Поняття подвійності...11

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

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

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

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

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