5834

Предмет і методологічні засади дослідження операцій

Конспект

Математика и математический анализ

Предмет і методологічні засади дослідження операцій Лекція 1 Сутність проблематики теорії дослідження операцій Понятійний апарат дослідження операцій. Класифікація задач оптимізації та управління Математичне моделювання в опт...

Украинкский

2012-12-23

1.58 MB

33 чел.

Предмет і методологічні засади дослідження операцій

Лекція 1

  •  Сутність проблематики теорії дослідження операцій
  •  Понятійний апарат дослідження операцій.
  •  Класифікація задач оптимізації та управління
  •  Математичне моделювання в оптимізації
  •  Формулювання математичної задачі оптимізації
  •  Інформаційне забезпечення математичної моделі
    1.  Сутність проблематики теорії дослідження операцій

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

Слово оптимальний походить від латинського Optimus, що означає найкращий, сучасний. Для того щоб знайти оптимальну з можливостей, доводиться розв'язувати задачі на відшукання максимуму чи мінімуму, тобто найбільших та найменших значень яких-небудь величин. Такі задачі вперше були поставлені античною наукою. Найбільш давньою з відомих експериментальних задач є класична ізопериметрична задача. Цю задачу зустрічаємо в легенді про Дідону. Фінікійська цариця Дідона, рятуючись від переслідувань брата  тирана, з невеликим загоном жителів залишила рідне місто. В пошуках щастя вони подалися берегом Середземного моря. Зупинившись на африканському узбережжі, Дідона та її супутники вирішили заснувати поселення. Вождь місцевих жителів Ярба погодився виділити Дідоні шмат землі, “який можна обгорнути шкірою бика”. Розрізавши шкіру на смуги, Дідона звязала їх у довгий пасок і, обгорнувши, ним значну територію, побудувала на ній місто Карфаген. Отже, якщо вірити легенді, першим оптимумом була Дідона.

Експериментальні задачі зустрічаються в працях великих математиків античності  Евкліда, Архімеда і Аполлонія. Пізніше, в XVI ст., коли було закладено основи алгебри, з’являються перші експериментальні задачі алгебраїчного змісту. З іменем Пєра Ферма повязане формулювання першого варіаційного принципу для фізичної проблеми. Його ідея полягала в тому, що промінь світла “вибирає” таку траєкторію, вздовж якої час, що витрачається на подолання шляху від однієї точки до іншої, був би мінімальним. Слідом за варіаційним принципом Ферма було відкрито багато інших принципів  спочатку в механіці, а потім у фізиці. З часом більшість вчених вважала, що природа завжди вибирає рух, ніби розвязуючи деяку задачу на екстремум.

В світі не відбувається нічого, в чому б не було б смислу якого-небудь максимуму чи мінімуму (Ейлер).

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

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

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

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

Отже, метою дослідження операцій є попереднє кількісне обгрунтування оптимальних рішень.

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

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

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

Так, наприклад, одну із перших кількісних моделей національної економіки – економічну таблицю Кене” запропонував лейб-медик французького короля Людовіка ХV Франсуа Кене (1694-1774  рр.) ще у 1766 р.

Французькі економісти і математики Антоній Курно (1801-1877 рр.) і Леон Вальрас (1834-1910 рр.), італійський соціолог і економіст Вільфредо Парето (1848-1923 рр.) у своїх роботах вже систематично застосували математичні моделі і методи. Зокрема, саме В. Парето запропонував один із методів прийняття рішення за умови кількох критеріїв їх ефективності. Л. Вальрас, якого вважають засновником математичної економіки, одним із перших визначив і продемонстрував роль і місце математичних методів у вивченні економіки. Його теорія загальної конкурентної рівноваги протягом багатьох років була рушійним чинником цих методів.

Теоретико-ігрову концепцію певних економічних відносин запропонував у 1928 р. видатний математик зі США, один із засновників кібернетики Джон фон Нейман (1903-1957 рр.), який разом з економістом Оскаром Моргенштерном (1902-1977 рр.) послідовно розвинув цю концепцію у монографії Теорія ігор і економічна поведінка (1944 р.). Крім того, у 1937 р. Дж. Фон Нейман запропонував економіко-математичну модель виробництва. Вона є узагальненням міжгалузевої моделі виробництва і розподілу, розробленої у 1936 р. американським економістом російського походження Василем Леонтьєвим (1906-1999  рр.), лауреатом Нобелівської премії 1973 р.

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

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

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

  1.  Понятійний апарат дослідження операцій

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

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

Приклад 1. Розмістити тимчасові торговельні точки з продажу заданих кількостей сезонних товарів, щоб забезпечити певну економічну ефективність розпродажу.

Приклад 2. З метою отримання прибутку встановити ціни продажу цих товарів.

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

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

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

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

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

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

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

Наявні ресурсні, технічні, технологічні, правові, морально-етичні, естетичні та. інші умови обмежують вибір ОПР певною множиною альтернативних рішень.

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

Оптимальне рішення  рішення із множини альтернативних рішень, яке у певному розумінні краще або не гірше за будь-яке із решти рішень.

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

Критерій ефективності рішень  кількісний показник прийнятого способу порівнювання між собою довільних альтернативних рішень.

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

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

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

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

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

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

У розробці математичної моделі операції беруть участь фахівці відповідної галузі діяльності (економісти, військові діячі, психологи, політики та ін.), математики, ОПР.

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

  1.  
    Класифікація задач оптимізації та управління

Класифікація задач оптимізації є досить складним завданням тому що ці задачі, в основному, історично розвивалися незалежно; одна від одної з використанням різних концепцій, математичних апаратів.

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

Накопичений досвід при розв’язанні задач дослідження операцій і його систематизація дозволили виокремити такі типи задач:

  •  задачі управління запасами;
  •  задачі розподілу ресурсів;
  •  задачі ремонту та заміни обладнання;
  •  задачі масового обслуговування;
  •  задачі впорядкування;
  •  задачі сітьового планування і управління;
  •  задачі вибору маршруту;
  •  комбіновані задачі.

До основних методів відшукання оптимальних рішень відносяться:

  •  математичне програмування;
  •  теорія масового обслуговування;
  •  сітьові моделі планування і управління;
  •  імітаційне моделювання.

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

  1.  Математичне моделювання в оптимізації

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

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

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

Системи обмежень включають систему рівнянь і нерівностей, яким задовольняють змінні моделі і які виходять з обмеженості ресурсів або інших економічних або фізичних умов, наприклад невід’ємності змінних і тому подібне.

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

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

,

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

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

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

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

1. План постачання підприємства. Нехай маємо ряд підприємств, які використовують різні види сировини, а також ряд баз, ікі постачають сировину. Бази повязані з підприємствами різними шляхами сполучення (залізничні шляхи, автотранспорт, водний, повітряний транспорт). Кожний вид транспорту має своі тарифи. Необхідно розробити такий план постачання підприємств сировиною так, щоб потреби у сировині були задоволені при мінімальних витратах на перевезення.

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

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

4. Військові дії. Метою в даному випадку є знищення ворожого об’єкта.

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

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

  1.  визчення границь об’єкту оптимізації, вибір змінних задачі;
  2.  вибір керуючих змінних;
  3.  визначення обмежень на керуючі змінні;
  4.  вибір числового критерію оптимізації.
    1.  Визчення границь об’єкту оптимізації

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

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

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

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

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

  1.  Вибір керуючих змінних

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

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

  1.  Визначення обмежень на керуючі змінні

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

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

  1.  Вибір числового критерія оптимізації

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

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

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

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

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

  1.  Формулювання математичної задачі оптимізації

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

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

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

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

Найкращим чином  означає, вибір деякого критерію оптимальності, тобто деякого економічного показника, який дозволить оцінити ефективність прийнятого рішення. Наприклад, “максимум прибутку”, “мінімум витрат”, “максимум рентабельності” та ін.

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

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

, (1.1)

, (1.2)

де    (1.1) – критерій оптимальності;

  керовані параметри, які можна змінювати у певних межах (управлінське рішення);

  некеровані параметри, значення яких визначаються зовнішніми умовами та характером системи (змінні параметри) ;

  кількісні характеристики системи чи умов (можуть бути незмінними, постійними);

  область допустимих рішень.

  1.  Інформаційне забезпечення математичної моделі

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

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

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

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


Лекція 2

"Ніяке людське дослідження не може називатися справжнім знанням, якщо воно не пройшло через математичні доведення".

Леонардо да Вінчі

  •  Предмет математичного програмування (МП).
  •  Класифікація задач МП.
  •  Постановка задачі МП.
  •  Типові задачі (ЛП).
  •  Загальна, стандартна та канонічна форма задачі лінійного програмування (ЛП).

  1.  Предмет математичного програмування

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

Розрізняють такі методи математичного програмування:

  •  лінійне програмування;
  •  нелінійне програмування;
  •  динамичне програмування;
  •  цілочисельне програмування;
  •  стохастичне програмування;
  •  евристичне програмування.

Сюди ж, як правило, теорію ігор, теорію масового обслуговування, теорію керування запасами та деякі інші.

Широкий інтерес до теорії і практики математичного програмування почався наприкінці 40-х - початку 50-х рр. ХХ ст. після того, як американський математик Д. Данциг розробив ефективний обчислювальний алгоритм для розв’язування задач лінійного програмування. Цей алгоритм увійшов до літератури під назвою симплексного методу. Слід зауважити, що робота над лінійним програмуванням почалася ще в 30-х  роках. В Угорщині в 1931 р. Була опублікована праця Б. Егерварі, присвячена проблемам мінімізації при транспортуванні вантажів. На основі цієї праці згодом було розроблено ефективний метод розв’язування транспортних задач лінійного програмування, який ввійшов до літератури під назвою “угорського методу”. В 1939 р. радянський математик Л. В. Канторович опублікував працю “Математичні методи в організації і спілкуванні виробництва”, в якій запропонував один в методів розв’язування задач лінійного програмування – метод розв’язуючих множників. Однак це були тільки спроби розв’язати окремі задачі лінійного програмування. Систематична робота над математичним програмуванням почалась якраз після розробки Дж. Данцигом симплексного методу розв’язування задач лінійного програмування.

Основоюдля досліджень задач нелінійного програмування стала опублікована В 1951 р. праця американських математиків Г. Куна і П. Таккера, в якій сформульовані необхідні й достатні умови оптимальності для розв’язування нелінійних задач.

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

  1.  Класифікація задач математичного програмування

У зв’язку з тим, що сьогодення висуває широкий клас задач, які розв’язуються методами оптимального (математичного) програмування, існує класифікація задач МП за такими ознаками:

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

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

  1.  Постановка задачі МП

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

 (1.3)

за умов

 (1.4)

  (1.5)

де      цільова функція,

  набір керованих параметрів,

(1.4), (1.5)  обмеження, які утворюють множину допустимих рішень.

Набір керованих параметрів , який задовольняє систему обмежень (1.4) - (1.5) називається допустимим розв’язком (планом) задачі МП.

Допустимий розв’язок задачі МП , який забезпечує екстремальне значення цільової функції, називається оптимальним розв’язком (планом) задачі МП.

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

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

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

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

  1.  Задача про використання ресурсів (задача планування виробництва)

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

Таблиця 1.1.

Вид ресурсу

Запас ресурсу

Число одиниць ресурсів, які витрачаються на виготовлення одиниці продукції

18

1

3

16

2

1

5

-

1

21

3

-

Математична постановка задачі

Необхідно скласти такий план виробництва продукції, при якому прибуток від її реалізації буде максимальним.

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

одиниць ресурсу

одиниць ресурсу

одиниць ресурсу

одиниць ресурсу

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

 (1.6)

Так як споживання ресурсів  не повинно перевищувати їх запасів, відповідно 18, 16, 5 і 21 одиниць, зв’язок між використанням ресурсів та їх запасами виражається системою нерівностей:

 (1.7)

За змістом задачі змінні . Отже, задача формулюється так: знайти такий план випуску продукції , який задовольняє систему (1.7) і при якому функція (1.6) приймає максимальне значення.

  1.  Задача про оптимальний раціон

В наявності є два види корму І і ІІ, які містять поживні речовини (вітаміни) . Вартість 1кг. Корму І та ІІ відповідно рівна 4 грн. та 6 грн.Вміст числа одиниць поживних речовин в 1кг. кожного виду корму і необхідний мінімум поживних речовин наведені в таблиці 1.2.

Таблиця 1.2.

Поживна речовина

Необхідний мінімум поживних речовин

Число одиниць поживних речовин в 1кг. корму

І

ІІ

9

3

1

8

1

2

12

1

6

Математична постановка задачі

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

Позначимо – кількість кормів І та ІІ, які входять у денний раціон. Тоді цей раціон буде містити:

одиниць поживної речовини ,

одиниць поживної речовини ,

одиниць поживної речовини .

Вміст поживних речовин  в раціоні повинен бути не менше відповідно 9, 8 та 12 одиниць.

Математична модель матиме вигляд:

за умов

  1.  Задача про суміш

Стандартом передбачено, що октанове число автомобільного бензину А-76 повинно бути не нижче 76, а вміст сірки у ньому – не більше 0,3%. Для виготовлення такого бензину на заводі використовується суміш із чотирьох компонентів. Дані наведені в таблиці 1.3.


        
Таблиця 1.3.

Характеристика

Компонент автомобільного бензину

№ 1

№ 2

№ 3

№ 4

Октанове число

68

72

80

90

Вміст сірки, %

0,35

0,35

0,3

0,2

Ресурси, т.

700

600

500

300

Собівартість, гр. од./т.

40

45

60

90

Математична постановка задачі

Необхідно визначити, скільки тон кожного компоненту слід використовувати для отримання 1000т. бензину А-76, щоб його собівартість була мінімальною.

Позначимо   кількість у суміші компоненти з номером . З врахуванням цих позначень маємо задачу (критерій оптимальності «мінімум собівартості»).

за умов

  1.  Задача оптимального розкрою (максимум комплектів розкрою)

Для виготовлення брусів довжиною 1,2м., 3м. і 5м. у відношенні 2:1:3 на розпил поступає 195 колод довжиною 6м.

Визначимо всі можливі способи розпилу колод, вказавши відповідне число отриманих при цьому брусів (табл. 1.1)

Таблиця 1.4

Способи розпилу

Спосіб розпилу

Число отриманих брусів довжиною, м.

1,2

3

5

1

5

-

-

2

2

1

-

3

-

2

-

4

-

-

1

Математична постановка задачі

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

  1.  
    Задача оптимального розкрою (мінімум відходів)

На підприємство поступають рулони шириною 730 см., які потрібно розрізати на заготовки трьох видів: 1-й шириною 225 см. 2-й шириною 200 см. 3-й шириною 110 см. План заготовок такий: першого типу – 60 шт. другого типу – 90 шт. третього типу 320 шт.

Таблиця 1.5

Таблиця варіантів розкрою

№ варіанту

Число заготовок з одного рулона

Відходи

1-го виду

2-го виду

3-го виду

1

3

0

0

55

2

1

2

0

105

3

2

1

0

80

4

0

0

6

70

5

1

0

4

65

6

2

0

2

60

7

0

1

4

90

8

0

2

3

0

9

0

3

1

20

10

1

1

2

85

Математична постановка задачі

План повинен виконуватися з мінімальними сумарними відходами.

Позначимо:  - кількість рулонів розкроєних по - му варіанту,

Цільова функція має вигляд:

Обмеження:

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

У кожного із постачальників накопичено відповідно 300, 250, 110 одиниць товару. Потреби споживачів складають відповідно 100, 200, 150, 210 одиниць товару. Вартості перевезення товару від -го постачальника до -го споживача подано у вигляді матриці, яку називають матрицею тарифів:

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

.

Математична постановка задачі

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

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

Таблиця 1.6




Постачальники

Споживачі

Запаси

В1

В2

В3

В4

А1

70

50

15

80

300

А2

80

90

40

60

250

А3

50

10

90

11

110

Потреби

100

200

150

210

660

З таблиці бачимо, що кількість товару, перевезеного від постачальників, задовольняє умову (a), а кількість товару, доставленого споживачам, задовольняє умову (b):

  (a)  (b)

Загальна вартість усіх перевезень повинна бути мінімальною, тобто:

  (c)

за умов

(a), (b)  та  

  1.  
    Модель «Витрати-випуск» В.
     В. Леонтьєва

Розглянемо одну із класичних задач дослідження операцій – закриту і стійку модель.

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

,

де   – вектор внутрішнього споживання продукції об’єктом;

  вектор кінцевої продукції (продукція, яка йде на продаж, запаси тощо).

Припустимо, що , де  – невід’ємна матриця елементів, які є коефіцієнтами прямих витрат при виробництві продукції. Тоді

 ()

У деталізованому вигляді матричне рівняння () має вигляд:

 ()

де  – кількість продукції -го виду, потрібної для виробництва одиниці продукції -го виду;

– компоненти вектора кінцевого випуску;

– кількість валового продукту відповідного виду.


Якщо технічні коефіцієнти  задані наперед, тоді за умов
и, коли відомо компоненти вектора кінцевого випуску , модель () дозволяє, визначити:

  1.  виробничу матрицю , де  – одинична матриця;
  2.  матрицю повних витрат ;
  3.  матрицю непрямих витрат ;
  4.  вектор валового випуску кожної галузі ;
  5.  виробничу програму кожної галузі ;
  6.  виробничу собівартість  кожного виду продукції за формулою , де  – алгебраїчні доповнення елементів матриці .

  1.  
    Форми запису задачі лінійного програмування (ЗЛП)

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

 (1.8)

за обмежень

 (1.9)

та умов невід’ємності

, (1.10)

Необхідно знайти такий розв’язок системи , при якому лінійна функція  прийме оптимальне (максимальна чи мінімальне) значення.

  1.  
    Загальна форма ЗЛП

Можна використовувати і більш стислий запис:

 (1.11)

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

 (1.12)

 (1.13)

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

Система (1.11) називається системою обмежень.

Оптимальним розв’язком (або оптимальним планом) задачі ЛП називається розв’язок  системи обмежень (1.12), який задовольняє умові (1.13) і при якому функція (1.11) приймає оптимальне значення.

В загальній формі ЗЛП умови невід’ємності можуть накладатися або на деякі змінні або не накладатися зовсім.

  1.  Стандартна (симетрична) форма ЗЛП

 (1.11c)

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

 (1.12c)

та умовах невід’ємності

 (1.13c)

  1.  
    Канонічна (основна) форма ЗЛП

 (1.11k)

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

 (1.12k)

та умовах невід’ємності

 (1.13k)

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

Для того, щоб перейти від однієї форми запису ЗЛП до іншої, необхідно вміти:

  1.  Заміняти нерівності виду  ” на нерівності виду “”.

 

  1.  Зводити задачу мінімізації функції до задачі максимізації.

 

  1.  Переходити від обмежень-нерівностеі до обмежень-рівностей і навпаки.

 ;

 .

 

  1.  Замінювати змінні, на які не накладено умови невід’ємності.

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


Запитання для самоконтролю

Яка суть операцій? Наведіть приклади операцій.

Що називають рішенням, оптимальним рішенням, критерієм ефективності операцій?

Навіщо потрібні математичні моделі операцій, хто їх розробляє?

У чому полягає проблематика теорії дослідження операцій?

Яка суть задач математичного програмування?

Яка роль ОПР у проведенні операцій?

Що розуміють під системою підтримки прийняття рішення?


Література до теми 1

  1.  Акулич И.Л. Математическое программирование В примерах и задачах.– М.: Высшая школа, 1986.– 319с.
  2.  Банди Б. Основы линейного программирования. – М.: Радио и связь, 1989.
  3.  Барвінський А.Ф. та ін. Математичне програмування. Дослідження операцій: Навч. посібник / А.Ф.Барвінсьий, І.А. Олексів, З.І. Крупка, І.О. зБобик, І.І. Демків, Р.І. Квіт, В.В.Кісілевич. – Львів: Інтелект-Захід, 2008.– 468с.
  4.  Вентцель Е.С. Исследование операций, задачи, принципы, методология.– М.: Наука, 1980.– 208с.
  5.  Воробьев Н.Н. Теория игр для экономистов-кибернетиков.– М.: Наука, 1985.–213с.
  6.  Высшая математика для экономистов/ Под ред. Н.Ш. Кремера. –М.: Банки и биржы, ЮНИТИ, 1995.
  7.  Гасс С Линейное программирование (методы и приложения).-М.: Гос. изд. физико-математической литературы,1961.-303с.
  8.  Гетманцев В.Д. Математика для економістів. Дослідження операцій. Математичне програмування: Навч. посібник.– К.: КНЕУ, 2006.– 308с.
  9.  Дослідження операцій в економіці: Підручник / За ред. І.К. Федоренко, О.І. Черняка.– К.: Знання, 2007.– 558с.–(Вища освіта ХХІ століття)
  10.  Дьяконов В.П., Абраменкова И.В. MATHCAD 8 PRO в математике, физике и Internet. -М.: Нолидж, 1999.
  11.  Ермольев Ю.М. и др. Математические методы исследования операций.–Киев.: Выща школа, 1979.– 312с.
  12.  Замков 0,0., Толстопятенко А.В.у ЧеремныхЮ.К, Математические методы в экономике. - М.: ДИС, 1998.
  13.  Исследование операций в экономике: Учеб. пособие для вузов / Н.Ш.Кремер, Б.А. Прутко, И.М. Фридман; Под ред. проф. Н.Ш.Кремера. – М.: ЮНИТИ. 2006, – 407с.
  14.  Калихман И.Л. Сборник задач по математическому программированию. – М.: Высшая школа, 1975.
  15.  Калихман И.Л., Войтенко М.А. Динамическое программирование. – М.: Высшая школа, 1979.
  16.  Крушевский А.В., Швецов К.И. Математическое программирование и моделирование в экономике. Киев: Выща школа, 1979.
  17.  Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование.. – Минск: Вышэйшая школа, 1994.
  18.  Кузнецов Ю. Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. – М.: Высшая школа, 1986.
  19.  Лагоша ЯЛ. Оптимальное управление в экономике. - М.: Финансы и статистика, 2002.
  20.  Макаров В.Л., Рубинов A.M. Математическая теория экономической динамики и равновесия. - М.: Наука, 1973. 9. Кротов В.Ф. Лагоша Б.А.у Сергеев СИ. Основы теории оптимального управления. -М.: Высшая школа, 1990.
  21.  Математическое программирование./ Под ред. Н.Ш. Кремера. – М.:Финстатинформ, 1995.
  22.  Общий курс высшей математики для экономистов: Учебник/ Под ред. В. И. Ермакова.- М.: ИНФРА-М, 1999.
  23.  Охорзин В.А. Курс лекций по теории оптимального управления с приложением алгоритмов и программ в системе MATHCAD. - Красноярск: Сибирская аэрокосмическая академия, 1999.
  24.  Рубинов A.M. Оптимальное управление в агрегированных моделях экономики. ~Л.: Наука, 1991.
  25.  Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / В.В.Федосеев, А.Н.Гармаш, И.В.Орлова и др.; Под ред. проф. В.В.Федосеева. – 2-е изд., перераб. и доп. – М.: ЮНИТИ-ДАНА, 2005. – 304с.


ТЕМА 2.
 МЕТОДИ РОЗВ’ЯЗУВАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ

Лекція 3

  •  Графічне розв’язування задачі лінійного програмування

2.1. Графічне розв’язування ЗЛП

Числом ступенів свободи  задач ЛП називається різниця між числом змінних і числом незалежних обмежень рівностей. Графічно можна розв’язати задачу з числом ступенів свободи меньше трьох.

Для графічного розв’язування ЗЛП необхідно:

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

4. Умови невід’ємності записати тільки для вільних змінних.

5. Побудувати область допустимих розв’язків системи обмежень для вільних змінних.

6. Визначити координати вершини ОДР, у якій цільова функція набуває екстремального значення.


Приклад
2.1

Розв’язати графічно ЗЛП:

  (2.1)

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

 (2.2)

і умовах невід’ємності:

 (2.3)

Приведемо в однорідну форму задачу (2.1) –(2.3). Випишемо матрицю коефіцієнтів та за допомогою елементарних перетворень утворимо одиничну підматрицю (віднімемо від першого рядка третій):

    

Отримаємо еквівалентну систему до системи (2.2)

 ()

Очевидно, що одиничну підматрицю утворюють коефіцієнти при змінних . Отже,  – базисні змінні,  – вільні. Виразимо базисні змінні через вільні:

 

Використовуючи ці залежності виключимо базисні змінні з функціоналу, підставивши їх у вираз функціоналу:

,

тобто

 

Після відкидання базисних змінних в системі обмежень отримаємо наступну ЗЛП:

 ()

 ()

 ()

Для графічного розвязування задачі () – () необхідно

Побудуємо область допустимих розв’язків (ОДР) системи ()

(рис. 2.1).

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

Напрямок зростання цільової функції  вказує її вектор-градієнт:

 

Для даної задачі . Отже .

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

Оптимальна точка , тобто .

Оптимальне значення цільової функції для задачі () – ():

 

Повернувшись до задачі (2.1) – (2.3), отримаємо значення базисних змінних:

 

Отже оптимальна точка задачі (2.1) – (2.3): .

Оптимальне значення цільової функції задачі (2.1) – (2.3):

 

Висновок: задачу(2.1) – (2.3) можна звести до задачі () – () і розв’язати графічно.


Лекція 4

  •  Математичні основи лінійного програмування. Жорданові перетворення
  •  Знаходження оберненої матриці
  •  Розв’язування СЛАР методом жорданових перетворень
    1.  Математичні основи лінійного програмування. Жорданові перетворення

Розглянемо таку задачу: змінні  виражаються через  таким чином

  (2.4)

Необхідно знайти вирази для через .

Для цього з 1-го рівняння системи (2.4) виразимо  через  і підставимо цей вираз у 2-ге і 3-тє рівняння.

 

або

 

Якщо тепер в 2-му рівнянні виразити  через

і підставити цей вираз в 1-е та 3-є рівняння, отримаємо:

 

або

 

І, нарешті, виразивши  через

,

підставивши цей вираз у 1-е та 2-е рівняння, отримаємо:

 (2.5)

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

Із системою лінійних рівнянь

 

зіставляємо таблицю,

Утворену коефіцієнтами при змінних , тобто матрицю , стовпець і стрічка, що окреслюють матрицю зліва і зверху, утворені символами .У цій таблиці –му рядку відповідає –е рівняння системи.

  1.  Алгоритм жорданових перетворень
  2.  Виберемо будь-який ненульовий елемент  і назвемо його розв’язуючим. Називаємо також рядок  таблиці розв’язуючим, а стовпець  – розв’язуючим стовпцем.
  3.  Розв’язуючий елемент замінюємо оберненим .
  4.  Всі елементи розв’язуючого рядка ділимо на розв’язуючий елемент і міняємо знак (крім розв’язуючого елемента).
  5.  Всі елементи розв’язуючого стовпчика ділимо на розв’язуючий елемент.
  6.  Решта елементів таблиці переховуємо за «правилом визначника», тобто елемент таблиці  замінимо на .

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

  1.  Міняємо місцями символи  та .

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


Запишемо вихідну систему у вигляді:

1

4

3

2

3

2

1

1

1

2

Вибравши розв’язуючий елемент і виконавши один крок жорданових перетворень, отримаємо таблицю:

2

Виконаємо наступні кроки жорданових перетворень.

3

-2

3

1

3

-4

-2

1

-1

1

4

-3

4

1

5

-6

-2

-1

1

1

Записавши згідно останньої таблиці систему, отримаємо:

 

  1.  
    Алгоритм модифікованих жорданових перетворень
  2.  Виберемо будь-який ненульовий елемент  і назвемо його розв’язуючим. Називаємо також рядок таблиці розв’язуючим, а стовпець  – розв’язуючим стовпцем.
  3.  Розв’язуючий елемент замінюємо оберненим .
  4.  Решта елементів розв’язуючого рядка ділимо на розв’язуючий.
  5.  Решта елементів розв’язуючого стовпчика ділимо на розв’язуючий елемент і міняємо знаки.
  6.  Решта елементів таблиці переховуємо за правилом визначника, тобто елемент таблиці  замінимо на .
    1.  Обчислення оберненої матриці за допомогою модифікованих жорданових перетворень

Запишемо умову попередньої задачі у матричному вигляді , де

  

Таблиці 4 відповідає рівність , де

 

Це означає, що .

Звідси отримаємо правило обчислення оберненої матриці за допомогою жорданових перетворень:

  1.  Елементи матриці  запишемо в жорданову таблицю у звичайному порядку.
  2.  Позначимо стовпці та рядки символами .


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

  1.  Розв’язання систем лінійних рівнянь методом жорданових перетворень

Систему лінійних рівнянь

 

перепишемо у вигляді:

 

Побудуємо жорданову таблицю:

1

0

2

-1

1

-2

0

1

-3

1

2

0

3

1

-1

-8

Проведемо жорданові перетворення, причому поставимо задачу отримати в лівому стовпці символи .

2

0

0

2

5

-1

-6

1

3

-1

-2

0

3

10

-4

-14


Перепишемо цю таблицю, виключивши стовпчик з позначкою 0.

0

5

-1

-6

3

-1

-2

0

10

-4

-14

3

0

5

-1

-6

-2

1

4

0

-10

4

10

5

-6

-2

4

0

-10

10

4

0

-1

2

1

-1

2

1

Отже, розв’язки системи:


Лекція 5.
Симплекс-метод

  •  Ідея симплекс-методу
  •  Алгоритм знаходження опорного плану
  •  Алгоритм знаходження оптимального плану

  1.  Ідея симплекс-методу

Симплес-метод є універсальним, оскільки дозволяє розв’язати практично будь-яку задачу лінійного програмування, записану в канонічній формі.

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

Розглянемо задачу лінійного програмування:

 (2.6)

 (2.7)

 (2.8)

Система обмежень (2.7) визначає в  випуклий многогранник , в одній із вершин якого досягається максимум або мінімум функціоналу (2.6).

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

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

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

  1.  Алгоритм знаходження початкового опорного плану
    1.  Складаємо початкову жорданову таблицю для задачі (2.6) – (2.8).

….

….

І

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

0

Якщо усі (стовпчик вільних членів) додатні, то опорний план знайдено:

Якщо , то  - опорний план

  1.  Припустимо, що серед вільних членів є від’ємне число . Проглядаємо стрічку з номером . Якщо у цій стрічці всі елементи невід’ємні , то система обмежень визначає пустий многогранник, нерівності несумісні, задача розв’язку немає.
    1.  Нехай у - ій стрічці елемент   від’ємний. Таких елементів може бути декілька. Проглядаємо елементи стовпчика з номером  і елементи стовпчика вільних членів, порівнюючи їх попарно (в одній стрічці). Фіксуємо тільки ті пари, у яких однакові знаки.
    2.  Для цих пар знаходимо так звані симплексні відношення, поділивши вільний член на відповідний коефіцієнт із рядка , тобто . Отримані симплексні відношення, завжди будуть додатними.
    3.  Знаходимо найменше симплексне відношення:

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

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

….

….

І

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

….

1. Після отримання опорного плану переглядаємо коефіцієнти рядка функціоналу . Якщо всі  окрім , то оптимальний план знайдено. Цей розв’язок можна виписати із таблиці, прирівнюючі «верхні» змінні до нуля, а «бокові»  до вільних членів.

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

3. У якості розв’язуючого елемента обирається елемент у розв’язуючому стовпчику, якому відповідає мінімальне симплексне відношення. З цим елементом робимо один крок МЖВ.

4. Отриманий план досліджуємо на оптимальність (п. 1). За наявності  процес продовжується.

5. Якщо хоча б в одному із стовпчиків, якому відповідає від’ємний елемент у рядку  не має додатних елементів (тобто неможливо вибрати розв’язуючий елемент), то це означає, що функціонал в ОДР необмежений. Задача на знаходження максимуму не має розв’язку.


Приклад.

Знайти максимум функціоналу

Лекція 6 Метод потенціалів для розв’язування транспортної задачі

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

6.1 Основні теоретичні відомості

6.1.1 Постановка задачі

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

Розрізняють два типи ТЗ: по критерію вартості (план перевезень оптимальний, якщо досягнуто максимум затрат на його реалізацію), та по критерію часу (план оптимальний, якщо на його реалізацію витрачається мінімум часу). Позначимо кількість вантажу, який є на кожній із  баз (запаси) відповідно , а загальну кількість вантажу – . Замовлення кожного із споживачів (потреби) позначимо відповідно , а загальну кількість потреб – .

Тоді при умові  маємо закриту модель, а при умові  – відкриту модель ТЗ.

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

План перевезень з вказанням запасів та потреб зручно записувати у вигляді таблиці (таблиця перевезень).

Пункти відправлення

Пункти призначення

Запаси

...

...

...

...

...

...

...

...

...

...

Потреби

...

Змінна  означає кількість вантажу, який перевозиться з бази  споживачу . Сукупність цих величин утворює матрицю перевезень.

Для розв’язку ТЗ необхідно, крім запасів та потреб знайти також і тарифи  тобто вартість перевезень одиниці вантажу з бази  споживачу .

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

Сума всіх витрат тобто вартість реалізації даного плану перевезень є лінійною функцією змінних , тобто

 

В таблиці перевезень, що представляє опорний план маємо  заповнених і  вільних клітинок.

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

В першому випадку можемо виключити стовпчик, який містить заповнену клітину у другому випадку виключається стрічка, яка містить заповнену клітину.

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

Зауваження! Може статися так, що вже на деякому (але не на останньому) кроці потреби чергового споживача виявляється рівним запасу вантажу на черговій базі, тоді після заповнення чергової клітини об’єм таблиці одночасно зменшується на один стовпчик та на одну стрічку. Але при цьому ми повинні рахувати, що зменшення об’єму таблиці відбувається або на один стовпчик або на одну стрічку, а у замовника ще залишилась незадоволена потреба в кількості нуля одиниць вантажу, яка і задовольняється на протязі наступних кроків. Цей нуль (“запас” або “потреба”) треба записати в чергову клітину, що заповнюється на одному із послідуючих кроків. Так як при цьому виявляється рівною нулю одна із невідомих, то ми маємо справу з виродженим випадком.

6.2 Методи відшукання початкового опорного плану ТЗ

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

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

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

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

Нехай на три бази  поступив однорідний вантаж в кількості 300т, 150т, 250т відповідно. Отриманий вантаж необхідно перевезти в п’ять пунктів  – відповідно у кілкостях 170т, 110т, 100т, 120т, 200т. Відстані між пунктами відправлення і пунктами призначення вказані в таблиці:


Бази

Споживач

Запаси

70

50

15

80

70

300

80

90

40

60

85

150

50

10

90

11

25

250

Потреби

170

110

100

120

200

700

6.2.1 Метод північно-західного кута

Бази

Споживач

Запаси

70

170

50

110

15

20

80

70

300

80

90

40

80

60

70

85

150

50

10

90

11

50

25

200

250

Потреби

170

110

100

120

200

700

Вартість перевезень при такому плані:

  

6.2.2 Метод мінімальної вартості

Бази

Споживач

Запаси

70

20

50

15

100

80

70

180

300

80

150

90

40

60

85

150

50

10

110

90

11

120

25

20

250

Потреби

170

110

100

120

200

700

Вартість перевезень при такому плані:

   

6.2.3 Метод подвійної переваги

Бази

Споживач

Запаси

70

170

50

^^     15

100

80

70

30

300

80

90

^       40

60

85

150

150

^       50

^^     10

110

90

^       11

120

^       25

20

250

Потреби

170

110

100

120

200

700

Вартість перевезень при такому плані:

   

Висновок: вартість перевезень, спланованих методом подвійної переваги є найменшою.

6.3 Приклади розв’язання ТЗ

6.3.1 Метод потенціалів

Нехай необхідно побудувати план перевезень вантажів з найменшою загальною вартістю від чотирьох постачальників  відповідно в кількостях: 120; 350; 150; 120 одиниць, до п’яти споживачів   відповідно в кількостях: 70, 150, 100, 180, 200. Вартості перевозом одиниці вантажу приведені в таблиці.

3

11

13

10

11

11

5

10

11

10

9

3

14

6

11

5

7

12

9

10

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

Спочатку побудуємо початковий опорний план методом північно-західного кута.

Запаси

v

u

3

11

16

17

22

0

3

70

–     11

50

13

10

+     11

120

-6

11

+       5

100

10

200

–     11

50

10

350

-11

9

3

14

+      6

130

–     11

20

150

-12

5

7

12

9

10

120

120

-22

0

0

0

0

0

60

60

потреби

70

150

200

180

200

Вартість перевезень при такому плані:

   

По завантажених клітинах будуємо систему потенціалів, поклавши один з них, наприклад, , та оцінюємо незавантажені клітини.

 

Серед нерівностей „>” вибираємо ту, для якої  – є максимальною, тобто ; ; ; , отже, максимальна різниця між сумою потенціалів та тарифом перевезення дорівнює 11, тому плюсова клітина .

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

Запаси

v

u

3

11

16

17

11

0

3

70

–     11

30

13

+     10

11

20

120

-6

11

+      5

120

10

200

–     11

30

10

350

-11

9

3

14

6

150

11

150

-1

5

7

12

9

10

120

120

-11

0

0

0

0

0

60

60

потреби

70

150

200

180

200

Вартість перевезень

Будуємо систему потенціалів та оцінюємо незавантажені клітини: Визначимо клітини, потенційні для завантаження.

 

Плюсова клітина . Перезавантаження виконуємо з величиною 30

Запаси

v

u

3

11

10

17

11

0

3

70

11

30

13

10

11

20

120

-6

11

5

120

10

200

11

30

10

350

-11

9

3

14

6

150

11

150

-1

5

7

12

9

10

120

120

-11

0

0

0

0

0

60

60

потреби

70

150

200

180

200

Вартість перевезень

Будуємо систему потенціалів і оцінюємо не завантажені клітини.

Для всіх не завантажених клітин виконується умова: , отже даний план – оптимальний, і мінімальна вартість перевезень


ТЕМА 3.
 ДВОЇСТІСТЬ У ЛІНІЙНОМУ ПРОГРАМУВАННІ

Лекція 7.

  •  Економічний зміст двоїстої задачі
  •  Правила побудови двоїстої задачі
  •  Симетричні задачі
  •  Несиметричні задачі
  •  Приклади побудови двоїстої задачі

  1.  Економічний зміст двоїстої задачі

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

Припустимо, що відходи основного виробництва забезпечують чотири види сировини в кількостях 150, 180, 160 та 80 одиниць відповідно і з них планується виготовляти два види виробів. Нормативні витрати кожного з чотирьох видів сировини на виробництво продукції першого виду – 4, 2, 3, 1 одиниць, а витрати тих же видів сировини на виробництво одиниці продукції другого виду – 0, 6, 2, 3 одиниці відповідно.

Очікуваний прибуток від реалізації одиниці продукції першого виду 30гр., а другого – 20гр. підприємство зацікавлене в максимізації прибутку при виготовленні виробів широкого вжитку.

Вид сировини

Запас ресурсу

Число одиниць сировини, які витрачаються на виготовлення одиниці продукції

150

4

0

180

2

6

160

3

2

80

1

3


Позначимо

– кількість одиниць -го виду продукції, запланованих для виготовлення,

– сумарний прибуток при реалізації запланованої виробничої програми.

Тоді математична модель вихідної задачі матиме вид

 (3.1)

 (3.2)

 (3.3)

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

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

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

 (3.4)

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

 (3.5)

причому, ціни не можуть бути від’ємними, тобто:

. (3.6)

в результаті отримаємо нову задачу ЛП (3.4) – (3.6), яка називається двоїстою або спряженою до вихідної задачі (3.1) – (3.3).

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

  1.  Правила побудови двоїстої задачі
  2.  цільова функція двоїстої задачі має протилежний сенс оптимізації;
  3.  число змінних двоїстої задачі визначається числом обмежень прямої задачі;
  4.  матриця коефіцієнтів при невідомих двоїстої задачі отримується транспонуванням матриці коефіцієнтів прямої задачі;
  5.  знаки в основних обмеженнях двоїстої задачі протилежні до знаків основних обмежень прямої задачі;
  6.  невід’ємність змінних зберігається тільки для симетричних задач.

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

– вартість одиниці -ої продукції;

– технологічний коефіцієнт – норма споживання -го ресурсу на виробництво –ої продукції;

– ресурси, які необхідно використати для випуску продукції;

– об’єм продукції -го виду, який необхідно випускати.

3.1.1. Симетричні задачі

Пряма задача ЛП Двоїста задача

 

 

 


3.1.2. Несиметричні задачі

Пряма задача ЛП Двоїста задача

 

 

 

Зауваження Перш ніж будувати двоїсту задачу, необхідно досягнути у вихідній задачі відповідності між сенсом оптимізації та знаком нерівностей обмежень. В основній системі обмежень max відповідає ””, а min – ””.

  1.  Приклади побудови двоїстої задачі

1. Нехай маємо задачу ЛП

 

 

 

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

Пряма задача:

.


Двоїста задача:

.

2. Нехай маємо задачу ЛП

 

 

 

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

Пряма задача:

Двоїста задача:

має довільний знак,

так як 1- є обмеження є рівнянням.

3.  Нехай маємо задачу ЛП:

 

 

 

Двоїста несиметрична задача:

 

 

умови невід’ємності не накладено.

Лекція 8.

  •  Приклад розв’язання прямої та двоїстої ЗЛП
  •  Аналіз чутливості лінійних моделей

Пряма задача:

 

 

 

Двоїста задача формується так:

 

 

 


Побудуємо початкову симплекс-таблицю (Табл. 3.1).

Табл. 3.1

ДЗЛП

W

ПЗЛП

1

1

1

-1,2

5,2

2

4

-5,5

12,5

1

-3

1

8

2

8

-1,6

11,6

1

-12,6

-6,2

7,5

0

В даному випадку маємо опорний план , так як всі вільні члени ПЗЛП додатні. Знайдемо оптимальний план.

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

Табл. 3.2

ДЗЛП

ПЗЛП

І

1

1

-1,2

5,2

-2

2

-3

2,1

-1

-4

2,2

2,8

-2

6

0,8

1,2

І

12,6

6,4

-7,52

65,52

На наступному кроці за розв’язуючий вибираємо третій стовпчик. Симплексні відношення: , тобто 1,5 та 1,27, отже за розв’язуючий вибираємо елемент  і знову виконуємо один крок модифікованих жорданових перетворень. В результаті отримаємо таблицю (Табл. 3.3).

Табл. 3.3

ДЗЛП

ПЗЛП

І

0,45

-1,18

0,55

6,73

-3,71

-3,64

1,71

6,05

-0,45

-1,82

0,45

1,27

-1,64

7,45

-0,36

0,18

І

9,1

-7,45

3,46

75,22

Далі за розв’язуючий стовпчик вибираємо другий. Симплексне відношення тут одне:, отже за розв’язуючий елемент беремо . На наступному кроці отримаємо таблицю:

Табл. 5.4

ДЗЛП

ПЗЛП

І

0,2

0,16

0,49

6,76

-4,21

0,49

1,23

6,13

-0,85

0,24

0,37

1,32

-0,22

0,13

-0,05

0,02

І

7,5

1

3,1

75,4

Отримали оптимальний план

прямої ЗЛП:       ;

та двоїстої ЗЛП:         ;


Аналіз розв’язків лінійних моделей

Планування випуску продукції підприємством. Планується випуск двох видів костюмів – чоловічих і жіночих.

На жіночий костюм потрібно 1м. шерсті, 2м. лавсану і один день трудовитрат. На чоловічий костюм – 3,5м. шерсті, 0,5м. лавсану і один день трудовитрат.

Всього є 350м. шерсті , 240м. лавсану і 150 людино-днів трудовитрат.

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

При цьому слід мати на увазі, що необхідно пошити не менше 60 чоловічих костюмів і забезпечити прибуток не менше 1400 гр. од.

Модель задачі

Введемо позначення:

- число жіночих костюмів; - число чоловічих костюмів;

Прибуток від реалізації складає:

Жіночих костюмів - 

Чоловічих костюмів -

Цільова функція

Обмеження задачі мають вид:

1. по шерсті:

2. по лавсану:

3. по трудовитратах:

4. по мінімальному прибутку:

5. по мінімуму виробів:


Сформулюємо модель двоїстої задачі

  1.  Приведемо всі нерівності системи обмежень початкової задачі до одного виду, якщо в початковій задачі вимагається знайти максимум лінійної форми, то всі нерівності системи обмежень привести до виду “”.

 

  1.  Випишемо матрицю з коефіцієнтів системи обмежень і транспонуємо

  

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

 

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

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

  1.  Записати умови невід’ємності змінних двоїстої задачі.

В результаті отримаємо модель двоїстої задачі

За умов

 

 

В якій змінні мають наступний зміст:

- двоїста оцінка ресурсу шерсті, яка може бути ціною шерсті.

- двоїста оцінка ресурсу лавсану, яка може бути ціною лавсану.

- двоїста оцінка ресурсу “трудовитрати”

- двоїста оцінка замовлення випуску жіночих і чоловічих костюмів.

- двоїста оцінка прогнозованого прибутку.

В результаті розв’язання задачі симплекс- методом отримаємо наступні дані:

 

 

Таким чином, максимальний прибуток складає 2300 гр.од. при виробництві
70-ти жіночих та 80-ти чоловічих костюмів.

Додаткові зміни  показують, що шерсть і трудові ресурси використані повністю.

Лавсану залишилося 60 м. (.)

Планові завдання перевиконані по числу костюмів (.) та по прибутку (гр. од.)

Розв’язок двоїстої задачі вказує на дефіцитність ресурсів “шерсті”() і трудовитрат ()


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

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

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

Лема та теореми двоїстості.

Кожна із пари взаємоспряжених задач фактично є самостійною задачею ЛП і може бути розв’язана незалежно одна від одної.

Однак при розв’язанні одної задачі симплексним методом одночасно розв’язується інша, яка є двоїстою до початкової.

Існує зв’язок між розв’язками початкової і двоїстої задач, який випливає з леми та теорем двоїстості.

Нехай є пара взаємоспряжених несиметричних задач:

         (1)              (3)

      (2)           (4)

 

Лема.

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

  або     .

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

,

то  і є оптимальними розв’язками цих задач.

Теорема 1. ( перша теорема двоїстості ).

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

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

Економічна інтерпретація першої теореми двоїстості.

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

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

Двоїсті оцінки виступають як інструмент балансування витрат і результатів виробництва.

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

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

Теорема 2. ( друга теорема двоїстості для симетричних задач ). Для того, щоб плани  і  пари взаємоспряжених задач були їх оптимальними розв’язками, необхідно і достатньо виконання умов додаткової нежорсткості:

 (5)

 (6)

Другій теоремі двоїстості дамо інше (еквівалентне до (5) і (6)) тлумачення:

Теорема 2. ( друга теорема двоїстості для симетричних задач ).

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

якщо  для деякого j, то ,

і якщо , то ;

або ж

якщо  для деякого і, то ,

і якщо , то

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

 

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

Отже, розглянуті теореми двоїстості є базою для проведення глибшого аналізу моделей взаємоспряжених задач лінійного програмування.


ТЕМА: ПАРАМЕТРИЧНЕ ПРОГРАМУВАННЯ

Лекція 9.

Постановка і геометрична інтерпретація задачі

Задачі параметричного програмування є узагальненням задач лінійного програмування.

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

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

а) постійної – вартості продукції на момент її виготовлення;

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

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

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

Представивши їх у вигляді функції лінійного параметра , можна вивчити поведінку розв’язків задач при різних значеннях цих коефіцієнтів.

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

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

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

Нехай параметр

,

де  і  – будь-які дійсні числа.

Необхідно знайти для кожного  на відрізку  свій вектор

, (1)

що максимізує

 (2)

за умов

 (3)

У виразі (2) числа    і   відомі і постійні.

Геометрична інтерпретація задачі.

Нехай система обмежень (3) сумісна і визначає опуклий многокутник .

Рис.1

Рівнянню

 (4)

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

Якщо параметру  надати деяке значення

, (5)

то гіперплощина займе цілком визначене положення.

Переміщаючи її від початку координат, в напрямку зростання функції, отримаємо розв’язок в точці  (рис.1.).

Надамо параметру  інше значення  і знову знайдемо в області  точку оптимуму. Гіперплощина внаслідок зміни параметра t повернеться навколо початку координат на деякий кут.

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

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

Нехай при  гіперплощина буде паралельною ребру АВ.

Оптимальний розв’язок в цьому випадку досягатиметься в будь-якій точці відрізка АВ.

Покладаючи  (), отримаємо оптимальний розв’язок у вершині В.

Для цієї вершини буде свій інтервал зміни параметра .

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

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

Якщо многокутник  необмежений,

Рис.2

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

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

Графічний розв’язок задачі

Приклад 1. Визначити інтервал зміни параметра  і знайти значення змінних  та , при яких максимум лінійної функції

,          ,

досягається в одній і тій же вершині області допустимих розв’язків системи обмежень

 

Розв’язок. Знаходимо область допустимих розв’язків системи обмежень.

Це многокутник ABCD (рис.3).

Рис. 3

Надамо параметру найменше значення

,

тоді отримаємо функціонал з постійними коефіцієнтами.

.

Максимальне значення отриманого функціоналу  досягається в вершині С.

Прирівнюємо  до нуля

,

і запишемо рівняння розв’язуючої прямої як рівняння з кутовим коефіцієнтом при будь-якому :

Запишемо кутовий коефіцієнт  цієї прямої

і дослідимо його поведінку при зміні параметра :

Його початкове значення при  буде

.

Знайдемо похідну кутового коефіцієнта  по параметру :

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

Знайдемо границю його зростання:

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

(Нагадаємо, що при вертикальному положенні прямої кутовий коефіцієнт, як і функція, має розрив).

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

В розглядуваному прикладі при зміні параметра  від нуля до деякого значення, максимум функції буде у вершині С.

Далі в деякий фіксований момент часу екстремум буде досягатися на відрізку ВС, а потім він перейде в точку В і залишиться в ній для всіх великих значень .

Визначимо значення параметра , за якого розв’язок задачі буде на відрізку ВС.

Оскільки в цей момент пряма ВС і розв’язуюча пряма повинні бути паралельними, прирівняємо їх кутові коефіцієнти.

Кутовий коефіцієнт прямої ВС

,

отже,

,

звідки .

Отже, при  оптимальний розв’язок задачі буде в вершині , при  воно досягається на всьому відрізку ВС, а при  в точці .

Аналітичний розв’язок задачі

Алгоритм розв’язку задачі (1) – (2) складається з двох етапів.

Етап I. Параметру  надають фіксоване значення, наприклад

.

Цим задача приводиться до задачі лінійного програмування.

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

Етап II. Визначають інтервал зміни параметра , для якого максимум , досягається в одній і тій же вершині многогранника .

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

Розв’язок продовжується до тих пір поки весь відрізок  не буде розбито на частинні інтервали.

Задача. Знайти інтервали зміни параметра t на відрізку , для яких

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

Розв’язання.

Етап I.

  1.  Покладемо

.

Тоді функція  прийме вигляд

. (7)

Всі дані задачі заносимо в жорданову таблицю.

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

Крім того, додамо до таблиці два рядки для запису функції  з довільним параметром  (табл. 1).

При цьому в передостанньому рядку записуємо коефіцієнти , а в останньому – .

Щоб отримати , потрібно перемножити коефіцієнти останнього рядка на  і додати їх до коефіцієнтів передостаннього.


Таблиця 1

1

=

=

0

0

0

2. Знаходимо оптимальний план задачі звичайним симплекс-методом, здійснюючи перетворення і елементів останніх двох рядків.

Припустимо, що план, представлений в таблиці 2, є оптимальним.

 Таблиця 2

1

Тоді всі коефіцієнти рядка  – невід’ємні:

.

Оскільки оптимальний план знайдено, переходимо до виконання дій другого етапу.


Етап
II.

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

Для цього необхідно, щоб всі коефіцієнти функції  були невід’ємні:

 (8)

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

.

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

  •  якщо всі вони більші нуля, переходимо до пункту 2;
  •  якщо всі вони менші нуля – до пункту 3;
  •  якщо ж серед елементів  є і додатні, і від’ємні – до пункту 4.
  1.  Нехай всі .

Серед відношень

вибираємо найбільше.

Верхньої межі для  в цьому випадку не існує.

Таким чином,

 (9)

В інтервалі  функція  досягає максимум в тій самій вершині, що й при ; відповідно, .

3. Нехай всі .

Серед відношень

вибираємо найменше.

Якщо взяти

,

то всі умови (8) будуть задоволені.

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

Отже,

 (10)

Як і раніше, .

4. Нехай серед елементів  є як додатні, так і від’ємні.

Розділимо систему нерівностей (8) на дві підсистеми відповідно до знаків коефіцієнтів .

Тоді із підсистеми нерівностей з

отримаємо

,

а з другої підсистеми з

будемо мати

.

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

 (11)

В цьому випадку виділений інтервал, в якому функція досягає максимум в тій самій вершині, що й при , є відрізком

.

5. Зрівняємо отриманий інтервал  з заданим .

Незалежно від значення  лівою границею першого інтервалу буде , так як  більше  бути не може.

Якщо

,

то весь інтервал  попадає всередину інтервалу , і задача розв’язана.

Для будь-якого значення параметра  максимум функції  досягається в одній і тій самій вершині (рис. 4).

             

Рис. 4 Рис. 5

6.Якщо , то в інтервалі  максимум функції  буде в знайденій вершині (рис. 5).

Виключаємо цей інтервал із розгляду і розв’язуємо задачу для інтервалу, що залишився .

Для цього  надаємо значення  і замінюємо рядок  рядком .

В результаті заміни отримаємо нову таблицю (табл. 3).

 Таблиця 3

1


За розв’язуючий стовпчик в новій таблиці вибирається той, по якому визначено значення  (в цьому стовпчику на перетині з  – рядком знаходиться елемент, рівний нулю).

Якщо нулі знаходяться в кількох стовпцях, то за розв’язуючий можна брати будь-який з них.

Розв’язуючий елемент знаходимо по найменшому симплексному відношенню і робимо один крок модифікованих жорданових виключень.

Отримаємо наступний по порядку оптимальний розв’язок, так як всі коефіцієнти в стрічці  при перетворенні не зміняться.

Для знайденого розв’язку знову визначаємо інтервал зміни параметра , для чого переходимо до пункту 1.

Якщо в розв’язуючому стовпчику не виявиться невід’ємних коефіцієнтів, то функція  при  необмежена; задача на інтервалі , що залишився розв’язку не має.

Зауваження. При відшуканні оптимального розв’язку для  (при виконанні пункту 2 етапу І алгоритму) може виявитися, що функція  зверху необмежена.

В цьому випадку в розв’язуючому стовпчику  коефіцієнт - стрічки від’ємний , а всі інші коефіцієнти стовпчика  недодатні.

При значенні  на перетині стрічки  і стовпчика  буде елемент

.

Нас цікавить значення цього елемента, так як вони визначають поведінку функції при

.

Виберемо таке значення , при якому коефіцієнт

.

Звідси отримуємо, що

.

Якщо значення елемента , то для всіх  коефіцієнт розв’язуючого стовпчика в стрічці  буде від’ємним

.

Отже, на всьому заданому відрізку  цільова функція  необмежена (задача розв’язку не має).

Якщо елемент , то при  коефіцієнт, що знаходиться в розв’язуючому стовпчику та -стрічці, буде від’ємним.

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

При значенні  коефіцієнт

,

а при подальшому збільшенні  він буде додатнім.

До відрізку  застосовуємо послідовно весь алгоритм розв’язку задачі.

Приклад 3. Знайти розв’язок задачі з прикладу 1 при зміні параметра  на відрізку [0,12].

Розв’язок. Припускаємо .

Тоді

.

Заносимо умову задачі в таблицю 4 і розв’язуємо її симплекс-методом.

Опускаючи подробиці, наводимо оптимальний розв’язок (табл. 5.):

.

Визначаємо значення параметра , при яких оптимальний розв’язок в тій самій вершині, що й при .

Так як в останньому рядку елемент

, а ,

то для визначення значень , при яких максимум буде досягатись в знайденій вершині, підставимо відповідні значення в відношення (11), отримаємо

Таблиця 4. Таблиця 5

1

1

10

2

-5

14/3

1/30

7/30

-5

-1

-1

25/3

1/6

1/6

4

-1

1

11

3/10

1/10

40

4

5

4/3

-2/15

1/15

0

-4

-2

36

2/5

4/5

0

-4

-2

36

2/5

4/5

0

0

-1

4/3

-2/15

1/15

Тут , а .

Отриманий інтервал менший заданого , тому його виключаємо з подальшого розгляду і розв’язуємо задачу для інтервалу, що залишився .

Для цього даємо  значення  і обчислюємо для нього рядок .

Занесемо елементи - рядка в табл. 6. Всі інші елементи таблиці залишаємо без змін.

Таблиця 6 Таблиця 7

1

1

14/3

1/30

7/30

31/9

25/3

1/6

1/6

20/9

11

3/10

1/10

110/3

4/3

-2/15

1/15

56/9

40

0

1

40

0

1

36

2/5

4/5

64/3

-4/3

2/3

4/3

-2/15

1/15

56/9

4/9

1/9

В першому стовпчику і - рядку табл. 6. знаходиться нуль, тому цей стовпець беремо за розв’язуючий (при  на місце нуля першим з’явиться від’ємне число і план перестане бути оптимальним).

Знаходимо розв’язуючий елемент по найменшому симплексному відношенню і переходимо до нової таблиці (табл. 7).


План

в табл. 7 оптимальний, так як всі елементи - рядка невід’ємні.

В останньому рядку всі елементи , відповідно, застосовуємо формулу (7) і визначаємо, що

,

тобто .

Так як значення , то задача розв’язана.

Отже, при

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

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


ТЕМА 
7. ЗАДАЧІ ДРОБОВО-ЛІНІЙНОГО ПРОГРАМУВАННЯ

Лекція 9.

  •  Приклад економічної задачі та її математичне формулюванн
  •  Геометричний зміст і графічний спосіб розв’язку задачі Д-ЛП.

1. Приклад економічної задачі та її математичне формулювання.

Нехай виробництво випускає однорідний продукт і володіє технологічними способами (технологіями).

При роботі за цими технологіями за одиницю часу отримуємо продукту відповідно q1, q2,…qn, а виробничі витрати за одиницю часу складають p1, p2,…pn, одиниць.

Якщо скласти план, по якому підприємство буде працювати по відповідних технологіях x1, x2,…xn – одиниць часу, то загальний випуск продукції буде рівний:

, (1.1)

а загальні витрати складають:

 (1.2)

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

 (1.3)

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

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

Функція виду

 

називається дробово-лінійною.

Собівартість являється не єдиним економічним показником, що має добово-лінійну структуру (наприклад, рентабельність і т.д).

Загальна задача Д-ЛП (дробово-лінійного програмування) полягає у визначенні максимального (мінімального) значення функціоналу:

    max(min) (1.4)

при умовах:

 (1.5)

, (1.6)

де pj, qj, ai,  - деякі постійні числа, а

 (1.7)

(коли , то знак можна віднести до чисельника).

2. Геометричний зміст і графічний спосіб розв’язання задачі дробово-лінійного програмування.

Розглянемо на площині Ox1x2 цільову функцію:

  (2.1)

звідки виразимо x2:

ввівши позначення: , отримаємо: x2=k x1.

x2=k x1 - пряма, яка проходить через початок координат.

Рис.1

Встановимо, як буде поводити себе кутовий коефцієнт k при монотонному зростанні функції F. Для цього візьмемо похідну від k по .

(Fq2-P2)2 , а чисельник не залежить від F.

Отже, похідна має постійний знак і при звільненні F кутовий коефіцієнт буде тільки зростати або спадати і пряма буде повертатися в одну сторону.

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

При цьому можливі такі випадки:

  1.  Многокутник обмежений (Рис.2), максимум і мінімум є (стрілки на малюнку показують напрямок повороту прямої для збільшення F).

Рис.2

  1.  Область необмежена, але максимум і мінімум є (Рис.3).

Рис.3

  1.  Область необмежена, і один із екстремумів не досягається (Рис.4).
  2.  

Рис.4

  1.  Область необмежена, обидва екстремуми асимптотичні (Рис 5).

Рис.5

Такий гометричний зміст задачі і оснований на ньому графічний метод її розв’язку.

ПРИКЛАД.

Знайти максимум і мінімум функціоналу.

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

 

РОЗВ’ЯЗАННЯ.

Будуємо область допустимих розв’язків (Рис.6). Очевидно, що екстремальними будуть точки А і В.

Рис 6.

Визначимо де буде max, а де min. Виразимо з із цільової функції x2 :,  

Так як  при будь-якому F функція  

спадаюча, із збільшенням F кутовий коефіцієнт k зменшується. Це відповідає повороту за годинниковою стрілкою. Отже, в тоці А(2;3) значення F буде найменшим, а у вершині В(4;1) – найбільшим. Обчислимо значення функціоналу в цих точках.

 

Оскільки FA < FB, то  і .

Лекція 10.

  •  Симплек-метод у Д-ЛП.
  •  Перетворення дробово-лінійної задачі в лінійну

3. Симплекc-метод у дробово-лінійному програмуванні.

В задачі дробово-лійнійному прикладі обмеження ліній і екстремум функціоналу досягається у вершині многогранника розв’язків.

Ця подібність із задачею лінійного програмування дозволяє розв’язувати задачі дробово-лінійного програмування звичайним симплекс-методом із зміненим критерієм оптимальності.

РОЗГЛЯНЕМО ЗАДАЧУ.

Знайти максимум функціоналу:

  (3.1)

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

 (3.2)

  (3.3)

 (3.4)

РОЗВ’ЯЗУВАННЯ.

  1.  Складаємо початкову симплекс-таблицю (Табл.1).

При чому, для F передбачаємо два рядка: у верхньому записуємо коефіцієнт чисельника pj, в нижньому – знаменника qj.

Табл.1

-x1                    -x2                              -x m

1

y1=

y2=

-

ym=

a 11                    a 12                              a 1n

a 21                    a 22                              a 2n

a m1                    a m2                             a mn

a 1

a 2

a m

F1=

F2=

-p1                       -p2                              -p m

-q1                       -q2                              -q m

0

0

  1.  План записаний в Табл. 1 не може бути опорним, так як F2 = 0, а серед bі є від’ємні обов’язково.

Кроками МЖВ відшукуємо опорний план.

Нехай в результаті к – кроків ми отримали таблицю (Табл.2).

Табл.2

-y 1              -y 2          -y k         -x s            -x n

1

Х1=

Х2=

Хk=

Yr=

Ym=

b 11              b 12          b 1k         b 1s            b 1n

b 21              b 22          b 2k         b 2s            b 2n

b k1              b k2          b kk         b ks            b kn

b r1              b r2           b rk         b rs             b rn

b m1            b m2          b mk        b ms            b mn

b 1

b 2

b k

b r

b m

F1=

F2=

-p1‘             -p2‘          -pk          -ps              -pn

-q1‘             -q2‘          -qk          -qs              -qn

Тут вже всі bj невідємні. В рядках F1 і F2 зявились вільні члени P(k) і Q(k), Q(k) 0, .

Розглянемо відшукання оптимального плану, тобто Fmax. Треба переміщатися від отриманої вершини в сусідню вершину по ребру, яка ближче розміщена до оптимальної вершини (Рис.7).

Рис.7.

Аналітично це означає зробити крок МЖВ з деяким brs. Задача полягає в тому, щоб встановити правило вибору brs (розв’язуючого елементу). Нехай ми вибрали brs. В новій (k+1) - ій таблиці замість P(k) буде стояти число:

 (3.4)

Аналогічно замість i Q(k) буде стояти число:

 (3.5)

Значення функціоналу на (k+1)- му кроці: . Далі знаходимо:

 (3.6)

Позначимо:

 (3.7)

З цими позначеннями отримаємо:

 (3.8)

Дослідимо вираз (3.8).

  1.  Щоб не відірватися від многогранника розв’язків, симплексне відношення  повинно бути  і найменшим із всіх можливих

Звідки слідує, що , так як по умові допустимості плану . Отже, завжди.

  1.  Q(i) завжди > 0, то Q(k)Q(k+1) завжди > 0, тому знак   F(k+1)F(k) залежить від знаку ds. Коли ds > 0, то      F(k+1)F(k) < 0. Звідки F(k+1) < F(k) або F(k) > F(k+1). Іншими словами, коли за розв’язуючий стовпчик взяти стовпчик з ds > 0, то після кроку МЖВ функціонал зменшується, а при виборі розв’язуючого стовпчика з ds < 0, F(k) > F(k+1) – функціонал збільшується. При ds = 0, F(k+1)=F(k) функціонал не змінюється. Визначник ds служить критерієм для вибору brs.

Алгоритм відшукання оптимального плану.

  1.  Після знаходження опорного плану обчислюються значення визначників:

,

значення яких заносяться в додатковий рядок таблиці.

В стовпчику вільних членів в цьому рядку записуємо значення функціоналу, рівне відношенню F1 i F2

 

В результаті приходимо до таблиці (Табл.3):

Табл.3

-y 1                   -y 2             -x s            -x n

1

х1=

х2=

ym=

b 11                   b 12             b 1s            b 1n

b 21                   b 22             b 2s            b 2n

b m1                  b m2            b ms            b mn

b 1

b 2

b m

F1=

F2=

p 1                      p 2             p s              p n

q 1                      q 2             q s              q rn

0

0

dj=

  d 1                 d 2               d s             d n

  1.  При розв’язку задачі на максимум функціоналу за розв’язуючий стовпчик вибираємо той, в якому dj  < 0. Коли таких стовпчиків декілька, то за розв’язуючий стовпчик краще брати той, в якому dj найбільший по абсолютній величині.
  2.  Розв’язуючи елемент в стовпчику шукається по найменшому симплексному відношенню.
  3.  Із знайденим brs робимо один крок МЖВ при цьому коефіціент ціх стрічок F1 і F2 не перетворюються по загальних правилах, а останній рядок не перетворюється.
  4.  Далі для кожного стовпчика обчислюємо визначники dj, а для плану - значення функціоналу F(k+1). Якщо серед dj є хоча б один від’ємний, то робимо новий крок МЖВ і т. д.
  5.  Оптимальний розв’язок буде досягнуто, коли після чергового кроку всі визначники dj стануть невід’ємними.
  6.  При розв’язуванні задачі на мінімум, за розв’язуючий приймається стовпчик з dj > 0. Критерієм оптимальності служить недодатність dj.

ПРИКЛАД.

Знайти максимум та мінімум функціоналу:

При виконанні обмежень:

 

РОЗВ’ЯЗАННЯ.

Складаємо початкову жорданову таблицю, заповнюючи коефіцієнтами функціоналу для чисельника та знаменника окремо два рядки F1 F2 (Табл.4).

Табл.4

1

-x 1                   -х 2               -x 3

y1=

y2=

y3=

-3                  6                     1

-1                  7                     2

-2                  4                     -1

2

12

-1

F1=

F2=

1                  2                     -1

3                  1                     5

0

0

Так як b3 = -1 < 0, то план х1 = х2 = х3 = 0 не є опорним.

Знайдемо опорний план. Відшукавши такий план, додаємо до таблиці ще один рядок, в який записуємо значення dj і функціоналу F (Табл.5) .

 Табл.5

2

-x 1                   -х 2               -y 3

y1=

y2=

x3=

-5                  10                    1

-5                 15                     2

2                 -4                     -1

1

10

1

F1=

F2=

-3                  2                      1

7                -21                     -5

-1

5

dj

-8                -11                      0

-1/5

Оскільки всі визначники dj недодатні, робимо висновок, що функціонал досягає мінімуму у вершині

x1 = 0, x2 = 0, x3 = 1

Для знаходження максимуму вибираємо за розв’язуючий другий стовпчик. Розв’язуючий елемент     brs = 10. З цим елементом робимо крок МЖВ, перетворюючи всю таблицю, крім останнього рядка dj. В результаті отримаємо таблицю виду (Табл.6).

Табл.6

3

-x 2                   -y 1               -y 3

x2=

y2=

x3=

-1/2              1/10                  1/10

5/2              -3/2                   ½

0                 2/5                  -3/5

1/10

17/2

7/5

F1=

F2=

-2                -1/5                   4/5

-7/2                21/10             -29/10

28/5

7/5

dj=

-92/5            11/10                  11/5

-12/71

Елемент  від’ємний – це означає, що максимум ще не досягнуто.

В першому стовпчику вибираємо за розв’язуючий елемент  з ним робимо наступний крок МЖВ і отримаємо нову таблицю (Табл.7).

Табл.7


4

-y 2                   -y 1               -y 3

x1=

x2=

x3=

1/5                -1/5                  1/5

2/5              -3/5                   1/5

0                  2/5               -3/5

9/5

17/5

7/5

F1=

F2=

4/5                -7/5                  6/5

7/5                0                  -11/5

28/5

19

dj=

184/25          -133/5            878/25

28/15

Обчисливши в новій таблиці всі  знову знаходимо один від’ємний, а тому робимо ще один крок МЖВ з елементом . В результаті отримали таблицю (Табл.8).

 Табл.8

5

-y 2                   -y 1               -x 3

x1=

x2=

y3=

1/5                  1/2                  -1/10

2/5                 3/2                 -7/10

0                  5/2                  -3/2

5/2

11/2

7/2

F1=

F2=

4/5                -7/2                -9/10

7/5                   0                  -11/5

21/2

19

dj=

                                  

В Табл.8 всі визначники dj невід’ємні. Це свідчить про те, що при значеннях невідомих функціонал досягає максимального значення . Задача розв’язана.


4. Перетворення дробово-лінійної задачі в лінійну.

Задача дробово-лінійного програмування:

 (4.1)

 (4.2)

 (4.3)

 (4.4)

Введемо позначення:.

З новими змінними функціонал стає лінійним:

Після поділу кожної нерівності системи (4.2) на знаменник дробового функціоналу  для обмеження з номером і будемо мати:

Позначимо , і тоді обмеження (4.2) приймуть вигляд:

або  (4.2*)

В початковій задачі xj  0, а (строго більша нуля) і тому yj  0 (4.5), а yj+1  0 (строго додатня). Не зменшуючи загальності умов і порядку розв`язку замість yj+1 > 0 введемо нестрогу нерівність yj+1  0 (4.6), тому, що значення yn+1 = 0 отримуватися не буде.

Необхідно врахувати наступну обставину. В Евклідовому просторі розмірності (n+1) гіперплощини, що визначаються рівняннями ai1y1 + ai2y2 +…+ ainyn - biyn+1 = 0, які випливають із системи (4.2*) проходять через початок координат. Сукупність умов (4.2*), (4.5) і (4.6) утворюють необмежений многогранник з єдиною вершиною – початком координат (Рис.8).


Рис.8

А тому в перетвореній задачі або всі змінні yj виявляться рівними нулю, або функціонал завжди буде необмеженим. Задача в такому виді не розв’язується. Справа в тому, що змінні yj підкоряються ще одній додатковій умові:

 (4.7)

Отже, q1y1 + q2y2 +…+ qnyn = 1 (4.8)

З умовою (4.8) область допустимих розв’язків перетвореної задачі стає обмеженою (Рис.9), а сама задача буде мати розв’язок.

Рис.9

Підведемо підсумки перетворень. Якщо здійснити заміну змінних по формулах:

 (4.9)

Тоді замість задачі (4.1)-(4.3) з дробово-лінійним функціоналом отримаємо наступну лінійну задачу:

знайти максимум(мінімум) функціоналу

 (4.10)

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

 (4.11)

 (4.12)

Визначивши значення yj , переходимо до знаходження початкових невідомих xj. Використовуючи формули (4.9), отримаємо:

 (4.13)

Знаходимо значення функціоналу для початкової задачі:

 

але , тому

Отже, задачі (4.1), (4.2), (4.3) і (4.10), (4.11), (4.12) еквівалентні.

ПРИКЛАД.

Знайти максимум функціоналу:

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

РОЗВЯЗУВАННЯ.

Позначимо додаткові змінні через y1,y2,y3 і запишемо початкову задачу для послідуючого порівняння в жорданову таблицю (Табл. 9):

 Табл. 9

x1

-x2

-x3

1

y1

-3

6

1

2

y2

-1

7

2

12

y3

-2

4

-1

-1

F1

-1

-2

1

0

F2

-3

-1

-5

0

Введемо змінні yj по формулах (4.9) і сформулюємо перетворену задачу.

Знайти максимум функціоналу:

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

 

Умову цієї задачі вписуємо в Табл.10. Вона  може бути отримана із Табл.9 по наступних правилах:

  1.  Стовпчик вільних членів переносимо в основну частину таблиці із зміненими знаками, над стовпчиком записуємо змінну yn+1 (в нашому випадку y4).

  1.  До таблиці приєднуємо новий стовпчик вільних членів, заповнюємо нулями.
  2.  Рядок знаменника функціоналу переносимо в основну частину таблиці і знаки коефіцієнтів змінюємо на протилежні, в лівий заголовний стовпчик записуємо нуль, а в стовпчик вільних членів – одиницю.

Для знаходження розв’язку задачі в першу чергу позбавляємося від обмеження-рівності (Табл.10, Табл.11).

 

 Табл. 10

-y1

-y2

-y3

-y4

1

Z1

-3

6

1

-2

0

Z2

-1

7

2

-12

0

Z3

-2

4

-1

1

0

0

3

1

5

0

1

Fпер

-1

-2

1

0

0

 Табл. 11

-y2

-y3

-y4

1

Z1

7

6

-2

1

Z2

22/3

11/3

-12

1/3

Z3

14/3

7/3

1

2/3

y1

1/3

5/3

0

1/3

Fпер

-5/3

8/3

0

1/3

Послідуючі модифіковані жорданові перетворення приводять до наступних таблиць (Табл.12, Табл.13).


Табл. 12

-Z2

-y3

-y4

1

Z1

-21/22

5/2

104/11

15/22

y2

3/22

1/2

-18/11

1/22

Z3

-7/11

0

95/11

5/11

y1

-1/22

3/2

6/11

7/22

Fпер

-5/22

7/2

-30/11

9/22

 Табл. 13

-Z2

-y3

-Z3

1

Z1

-49/190

5/2

-104/95

7/58

y2

3/190

1/2

18/95

5/38

y4

-7/95

0

11/95

1/19

y1

-1/190

3/2

-6/25

11/38

Fпер

1/38

7/2

6/19

21/38

Ми отримали оптимальний план:

Обчислюємо значення початкових невідомих:

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

–1

x2

x1

4

4

2

1

x1+ x 2=4

0

x1=2

x1x 2=1

F

1

2

3

3

Р

Х

-

Р

Х

+

-

Р

Х

+

-

-

+

Х

Р

Опорна

вершина

Екстремальна

вершина

F = C1

F = C2

x2

x1

x2

Fmin

Fmax

x1

Fmin

Fmax

x2

x1

Fmin

Fmax

x2

x1

Fmin

Fmax

x2

x1

Fmax

Fmin

C

B

A

0

2

4

5

3

x2

x1

x1+x2=5

3x1-x2=11

-x1+3x2=7

Fопор.п.

Fmax

y2

y1

0

q1y1+q2y2=1

y2

y1

0


 

А также другие работы, которые могут Вас заинтересовать

43733. Оптимізація виробництва деталі маточина переднього колеса 399.47 KB
  Опис призначення й умов роботи деталі. Хімічний склад механічні властивості матеріалу деталі. Аналіз технологічності деталі. Проектування маршрутного технологічного процесу виготовлення деталі.
43735. Создании базы данных для построения крепёжных деталей 3.34 MB
  Исходное информационное обеспечение. Обеспечить пользователя необходимой информацией о крепёжных деталях. Решение: Использование формы в которых будет содержаться необходимая информация о крепежных элементах. Создать программу которая позволила бы обрабатывать сортировать и изменять информацию о крепёжных элементах.
43736. Реализация базы данных центра занятости 587.17 KB
  С чисто практической точки зрения базы данных позволяют избавиться от большого количества бумажных документов и значительно ускорить поиск и внесение информации. Цель данного курсового проекта – реализация базы данных центра занятости. Для выполнения работ в базе данных необходима авторизация с помощью пары...
43737. Система управління складським обліком продовольчих товарів 24.23 MB
  Завдяки використанню топології складських приміщень, система наочно відображає завантаженість товаром осередків та стелажів Грамотна організація роботи підприємств складського комплексу веде до підвищення продуктивності праці, скорочує витрати робочого часу на виконання складських операцій і дозволяє ефективно використовувати складські приміщення. Все це сприяє підвищенню економічної ефективності підприємства.
43738. Обґрунтування роздільної технології збирання льону-довгунця з використанням льонопідбирача-молотарки ПМЛ-1 в Інституті луб’яних культур 1.64 MB
  Первинна очистка насіння здійснюеться на чотирьох машинах ОВС-25, великі партії насіння до посівних кондицій доробляються на двох лініях, одна з яких змонтована з послідовно підключених Петкусі-Гігантів, друга являе з себе комплекс КЗС-40, переобладнаний зерноочисними машинами фірми “Петкус”. Доробка машин малих парків насіння здійснюется на чотирьох Петкус-Суперах і одному Петкус-Гіганті.
43739. Исследование торговой деятельности малых предприятий розничной торговли продовольственными товарами магазина ООО «Эклар» 329.68 KB
  Организация малого предпринимательства в сфере торговли Понятие малого предпринимательства и этапы его развития Формы государственной поддержки малого предпринимательства Организация торговой деятельности малого предприятия в розничной торговле на примере ООО Эклар.
43740. Определение способов модернизации системы управления сбытом в ООО «Шебекинcкий Картон» 519.4 KB
  Комплекс мероприятий решений и действий по формированию ассортимента выпускаемой продукции и ценообразованию по формированию спроса и стимулированию сбыта реклама обслуживание покупателей коммерческое кредитование скидки заключению договоров продажи поставки товаров товародвижению транспортировке по инкассации дебиторской задолженности организационным материально-техническим и прочим аспектам сбыта. Таким образом в хозяйственной деятельности организации одним из основных вопросов являются сбыт реализация готовой...