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

Запровадження. Багато завдання, із якими випадає мати справу у повсякденній практиці, є багатоваріантними. Серед сили-силенної можливих варіантів за умов ринкових відносин доводиться відшукувати найкращі у сенсі при обмеженнях, що накладаються на природні, економічні та технологічні можливості. У зв’язку з цим виникла потреба застосовувати для аналізу та синтезу економічних ситуацій і систем математичні методи лікування й сучасну обчислювальну техніку? Такі методи об'єднуються під загальним назвою — математичне програмування. Математичне програмування — область математики, котра розробляє теорію і чисельні на методи вирішення багатомірних екстремальних завдань із обмеженнями, т. е. завдань на екстремум функції багатьох змінних з обмеженнями галузь зміни цих змінних. Функцію, екстремальна значення потрібно знайти у умовах економічних можливостей, називають цільової, показником ефективності чи критерієм оптимальності. Економічні можливості формалізуються як системи обмежень. Усе це становить математичну модель. Математична модель завдання — це відбиток оригіналу як функцій, рівнянь, нерівностей, цифр тощо. буд. Модель завдання математичного програмування включає: 1) сукупність невідомих величин, діючи куди, систему можна удосконалювати. Їх називають планом завдання (вектором управління, рішенням, управлінням, стратегією, поведінкою та інших.); 2) цільову функцію (функцію мети, показник ефективності, критерій оптимальності, функціонал завдання й ін.). Цільова функція дозволяє вибирати найкращий варіантз багатьох можливих. Найкращий варіант доставляє цільової функції екстремальна значення. Це то, можливо прибуток, обсяг випуску чи реалізації, витрати виробництва, витрати звернення, обслуговування чи дефіцитності, число комплектів, відходи тощо. буд.; Ці умови взято з обмеженості ресурсів, якими володіє суспільство, у будь-який час, з необхідності задоволення насущних потреб, з умов виробничих та технологічних процесів. Обмеженими не є лише матеріальних, фінансові та трудові ресурси. Такими може бути можливості технічного, технологічного і взагалі наукового потенціалу. Нерідко потреби перевищують можливості їх задоволення. Математично обмеження виражаються у вигляді рівнянь і нерівностей. Їх сукупність утворює область допустимих рішень (область економічних можливостей). План, задовольняє системі обмежень завдання, називається допустимим. Допустимий план, котрий завдавав функції мети екстремальна значення, називається оптимальним. Оптимальний рішення, взагалі кажучи, необов’язково єдино, можливі випадки, як його не існує, є кінцеве чи незліченну кількість оптимальних рішень. Одне з розділів математичного програмування — лінійним програмуванням. Методи і моделі лінійного програмування широко застосовуються при оптимізації процесів в усіх галузях народного господарства: розробки виробничої програми підприємства, розподілі її за виконавцям, під час розміщення замовлень між виконавцями й по тимчасовим інтервалам, щодо найкращого асортименту своєї продукції, в завданнях перспективного, поточного та оперативної планування і управління; у разі планування вантажопотоків, визначенні плану товарообігу та її розподілі; в завданнях розвитку та розміщення продуктивних сил, баз і складів систем звернення матеріальних ресурсів немає і т. буд. Особливо широке застосування методи лікування й моделі лінійного програмування отримали при рішенні завдань економії ресурсів (вибір ресурсозберігаючих технологій, складання сумішей, розплющ матеріалів), производственно-транспортных і інші завдання. Початок лінійному програмування було покладено в 1939 р. радянським математиком-экономистом Л. У. Канторовичем у роботі «Математичні методи організації та планування виробництва». Поява цієї роботи відкрило новий етап при застосуванні математики економіці. Через десятиліття американський математик Дж. Данциг розробив ефективний метод рішення даного класу завдань — симплекс-метод. Загальна ідея симплексного методу (методу послідовного поліпшення плану) на вирішення ЗЛП полягає у наступному: 1) вміння знаходити початковий опорний план; 2) наявність ознаки оптимальності опорного плану; 3) вміння переходити до нехудшему опорному плану.

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

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

Формы записи завдання лінійного програмування: Загальною завданням лінійного програмування називають завдання [pic] (1) при обмеженнях [pic] (2) [pic] (3) [pic] (4) [pic] (5) [pic]- довільні [pic] (6) де [pic]- задані справжні числа; (1) — цільова функція; (1) — (6) -обмеження; [pic] - план задачи.

1.2 Властивості рішень. Нехай ЗПЛ представленій у наступній записи: [pic] (7) [pic] (8) [pic] (9) Щоб завдання (7) — (8) мала рішення, системі її обмежень (8) повинна бути спільної. Це можна, якщо r цією системою максимум числа невідомих n. Випадок r>n взагалі неможливий. При r= n система має єдине рішення, що буде при [pic]оптимальным. І тут проблема вибору оптимального рішення утрачає будь-який сенс. З’ясуємо де структуру координат кутовий точки багатогранних рішень. Нехай r5, ресурс [pic] вважається більш дефіцитним, ніж ресурс [pic]. За підсумками теореми (про доповнювала нежесткости) неважко пояснити, чому увійшла у оптимальний план продукція [pic]и [pic]: перше і друге обмеження двоїстої завдання виконуються як суворі нерівності: 4−15+2- 5+0>65, 2−15+10*5>70. Це означає, що оцінки ресурсів, витрачених на виготовлення одиниці продукції [pic] і [pic], перевищують оцінки одиниці цієї категорії продукції. Зрозуміло, таку продукцію випускати підприємству невигідно. Що ж до продукції [pic] і [pic] [pic], то випуск її виправданий, оскільки оцінка витрачених ресурсів збігаються з оцінкою вироблену продукцію: 2*15+ +6*5+2*0=60, 8*15+0=120. Отже, в оптимальний план ввійде лише та продукція, яка вигідна підприємству, і ввійде збиткова продукція. У цьому полягає рентабельність оптимального плана.

Рассмотрим можливість подальшого вдосконалення оптимального асортименту своєї продукції. Вище встановлено, що ресурси [pic] і [pic] є дефіцитними. У зв’язку з цим з урахуванням теореми (про оцінки) можна стверджувати, що у кожну одиницю ресурсу [pic], введену додатково у виробництві, буде отримана додаткова виручка [pic], чисельно рівна [pic]. У насправді, при [pic]получаем [pic]. З тих самих причин кожна додаткова одиниця ресурса[pic]обеспечит приріст [pic] виручки, рівний 5 р. Тепер стає зрозуміло, чому ресурс [pic]считается більш дефіцитним проти ресурсом [pic]: може сприяти отриманню більшої виручки. Що ж до надлишкового ресурсу [pic], то збільшення його запасу не призведе до зростання виручки, оскільки [pic]. З міркувань слід, що оцінки ресурсів дозволяють удосконалювати план випуску продукції. З’ясуємо де економічний сенс оцінок [pic]продукции [pic],[pic],[pic],[pic]. По оптимальному плану [pic]выпускать слід продукцію [pic]и [pic]. Оцінки [pic] і [pic] цих видів продукції рівні нулю. Що це, практично стане зрозуміло, коли уявити оцінки на розгорнутої записи: [pic] [pic] Отже, нульова оцінка показує, що ця продукція є неубыточной, оскільки оцінка ресурсів, витрачених на випуск одиниці такий продукції, збігаються з оцінкою одиниці виготовленої продукції. Що ж до продукції [pic] і [pic] що є, як встановлено вище, збитковою, тож і не вкорінений у оптимальний план, то тут для її оцінок [pic] і [pic]получаем: [pic] [pic] Звідси видно, що оцінка збитковою продукції показує, наскільки знижуватиме кожна одиниця такої продукції досягнутий оптимальний уровень.

§ 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 («Підготуйте матрицю: спочатку рівності, потім нерівності виду >= і нерівності виду =} for i:=m1+1 to m2 do a[i, n+i-m1]: =-1;

{перехід до равенствам в неравенствах max then begin max:=e[i]; j0:=i end;

{отримали стовпець з максимальною оцінкою} if max0 then begin writeln («Байдуже безліч планів »); goto 20 end;

for i:=1 to n do writeln («x[ «,і, «]= «, x[i]: 7:4);

20:readkey end.

Зміст Введение…1.

§ 1. Завдання лінійного програмування й поліпшуючи властивості її решений…4 § 2. Графічний спосіб розв’язання завдання лінійного программирования…6 § 3. Симплексный метод…8 § 4. Поняття двойственности…11 § 5. Основні теореми двоїстості та його економічне содержание…14 § 6. Приклади економічних задач…16 § 7. Аналіз завдання про оптимальному використанні сырья…19 § 8. Програма і расчеты…25.