- або багатокрокові залежних від способу їх розв'язування. ЯКЩО задачу можна розв'язувати Як однокрокову, то розв'язувати її Як багатокрокову недоцільно, абі НЕ застосовуваті для знаходження оптимального плану складнішіх методів. Проти більшість Економічних процесів є дінамічнімі, їх Параметри змінюються в часі й залежався від рішень керівніцтва, Що їх доводитися прійматі з метою Досягнення розвітку економічної системи за траєкторією, Яка візначається Стратегічним планом.
Щойно Було розглянуто Лише найбільші класи задач математичного програмування, які візначені згідно з математичних крітеріямі. Можна кож за різнімі ознайо виокремити й підкласі. Це особливо стосується задач лінійного, нелінійного и стохастичного програмування. Наприклад, Як окрема клас розглядають дробового-Лінійне програмування, коли обмеження є лінійнімі, а цільова функція - дробового-лінійна. Особливий клас становляит Задачі Теорії Ігор, які широко застосовують у рінковій економіці. Аджея тут діють Дві чі Більше конфліктніх сторін, які мают цілі, Що не збігаються, або протілежні цілі. У сукупності задач Теорії Ігор, у свою Черга, кож віокремлюють певні підкласі. Наприклад, ігри двох ОСІБ Із Нульовий сумою. Наведення класіфікацію використан для структурування курсу В«Математичного програмуванняВ».
2. Економічна інтерпретація прямої та двоїстої задач лінійного програмування
Кожна задача лінійного програмування пов'язана з іншою, так званні двоїстою задачею.
Економічну інтерпретацію кожної з пари таких задач розглянемо на прікладі виробничої Задачі.
Пряма завдання :
max F = c1x1 + C2x2 + ... + cnxn (3.1)
економічний двоїстій лінійній програмування
за умов: (3.2)
. (3.3)
Необхідно візначіті, Яку кількість продукції шкірного j- го виду необхідно віготовляті в процесі виробництва, щоб максімізуваті Загальну виручки від реалізації продукції підпріємства. Причому відомі: наявні обсягах ресурсів -; норми витрат і- го увазі ресурсу на виробництво одініці j- го виду продукції -, а також - ціні реалізації одініці j-ої продукції.
Розглянемо тепер Цю саму задачу з іншого подивимось. Припустимо, Що за Певної умів доцільно продавати Деяк Частину чі ВСІ наявні ресурси. Необхідно візначіті ціні ресурсів. Шкірному ресурсу поставімо у відповідність Його оцінку. Умовно вважатімемо, Що - Ціна одініці і- го ресурсу.
На виготовлення одініці j- го виду продукції вітрачається згідно з моделлю (3.1) - (3.3) m відів ресурсів у кількості відповідно. Оскількі ціна одініці і- го увазі ресурсу дорівнює, то загальна вартість ресурсів, Що вітрачаються на виробництво одініці j- го виду продукції, обчіслюється у такий спосіб:
.
продавати ресурси доцільно Ліше за умов, Що виручка, отримавших від продаж ресурсів, перевіщує торбу, Якові можна Було б Отримати від реалізації продукції, віготовленої з тихий самих обсягів ресурсів, тобто:
.
Зрозуміло, Що Покупець ресурсів прагнуть здійсніті операцію якнайдешевше, отже, необхідно візначіті мінімальні ціні одиниць шкірного увазі ресурсів, за якіх їх продажів є доцільнішім, Ніж виготовлення продукції. Загальну вартість ресурсів можна віразіті формулою:
.
Отже, в результаті маємо двоїсту задачу :
(3.4)
за умов: (3.5)
(3.6)
Тобто необхідно візначіті, які мінімальні ціні можна Встановити для одініці шкірного і- го увазі ресурсу, щоб продажів ресурсів БУВ доцільнішім, Ніж виробництво продукції.
Зауважімо, Що Справжній Зміст величин - умовні ціні, Що віражають Рівень В«цінностіВ» відповідного ресурсу для даного виробництва. Англійський Термін В«shadowpricesВ» у літературі перекладають Як В«ОцінкаВ» або В«Тіньова, неявна цінаВ». Академік Л.В. Канторович назвавши їх об'єктивно обумовлених оцінкамі відповідного ресурсу.
Задача (3.4) - (3.6) є двоїстою або дієвідміни до Задачі (3.1) - (3.3), Якові назівають прямою (основною, Початкова). Поняття двоїстості є взаємнім. За суті мова Йде про одну и ту ж задачу, альо з різніх поглядів. Дійсно, не Важко переконатіся, Що двоїста задача до (3.4) - (3.6) збігається з початково. Того шкірних з них можна вважаті прямою, а іншу - двоїстою. Сіметрічність двох таких завдань очевидна. Як у прямій, так и у двоїстій Задачі вікорістовують один набор Початкова даніх:,;. Крім того, вектор обмежень початкової Задачі стає вектором коефіцієнтів цільової функції двоїстої Задачі и навпаки, а рядки матріці А (матріці коефіцієнтів при змінніх з обмежень прямої Задачі) стають стовпцямі матріці коефіцієнтів при змінніх в Обмеження двоїстої Задачі. Кожному обмеження початкової Задачі відповідає змінна двоїстої и навпаки.
Початкова постановка Задачі та математична модель Може мати Вигляд ЯК (3.1) - (3.3), так і (3.4) - (3.6). Отже, Як правило, кажуть про пару спряжених задач лінійного програмування.
2.1 Правила побудова двоїстіх завдань
Для Побудова двоїстої Задачі необхідно звесті пряму задачу до стандартного вигляду. Вважають, Що задача лінійного програмування подана у стандартному вігляді, ЯКЩО для відшукання максимального значення цільової функції ВСІ нерівності її системи обмежень пріведені до виду «», а для Задачі на відшукання мінімального значення - до виду «».
ЯКЩО пряма задача лінійного програмування подана в стандартному вігляді, то двоїста задача утворюється за такими правилами :
1. Кожному обмеження прямої Задачі відповідає змінна двоїстої Задачі. Кількість невідоміх двоїстої Задачі дорівнює кількості обмежень прямої Задачі.
2. Кожній змінній прямої Задачі відповідає обмеження двоїстої Задачі, причому кількість обмежень двоїстої Задачі дорівнює кількості невідоміх прямої Задачі.
3. ЯКЩО цільова функція прямої Задачі задається на поиск найбільшого значення (max), то цільова функція двоїстої Задачі - на визначення найменшого значення (min), и навпаки.
4. Коефіцієнтамі при змінніх у цільовій функції двоїстої Задачі є Вільні члени системи обмежень прямої Задачі.
5. права частина системи обмежень двоїстої Задачі є коефіцієнті при змінніх у цільовій функції прямої Задачі.
6. Матриця
,
Що Складається з коефіцієнтів при змінніх у сістемі обмежень прямої Задачі, и матриця коефіцієнтів у сістемі обмежень двоїстої Задачі
утворюються одна з одної транспонуванням, тобто заміною рядків стовпчікамі, а стовпчіків - рядками.
Процес Побудова двоїстої Задачі Зручний зобразіті схематично:
Рис. 3.1. Схема Побудова двоїстої Задачі до прямої
Парі завдань лінійного програмування бувають сіметрічні та несіметрічні.
У симетрично завданнях обмеження прямої та двоїстої завдань є Ліше нерівностямі, а змінні обох задач можут набуваті Ліше невід'ємніх значення.
У несіметрічніх завданнях деякі обмеження прямої Задачі можут буті рівняннямі, а двоїстої - Ліше нерівностямі. У цьому разі відповідні рівнянням змінні двоїстої Задачі можут набуваті будь-яких значень, НЕ обмеження знаком.
Всі можліві формі прямих завдань лінійного програмування та відповідні їм варіанті моделей двоїстіх завдань у матрічній формі наведено ніжче.
Пряма задача
Двоїста задача
Cіметрічні Задачі
max F = CX
AX B
X 0
min Z = BY
...
