ПРОБЛЕМА ЛІНІЙНОГО ПРОГРАМУВАННЯ (PPL)
Математика
ІНШІ ДОКУМЕНТИ
ПРОБЛЕМА ЛІНІЙНОГО ПРОГРАМУВАННЯ (PPL)
Основні форми PPL, рішення, класифікація; економічне тлумачення ЗОЗ.
Проблема математичне програмування являє собою визначення оптимуму (максимуму або мінімуму) векторної змінної функції, яка відповідає умовам (обмеженням, зв'язкам) типу нерівностей або рівнянь, а також умовам невід'ємності змінних функції. Якщо всі функції, що втручаються у постановку задачі математичного програмування, є лінійними, то задачу називають проблема лінійного програмування (PPL); інакше це називається задача нелінійного програмування.
Стандартна форма - - це та, яка містить обмеження типу рівняння.
- оптимальний z =
-обмеження рівності:
- умови невід'ємності:
Стандартну матричну форму можна виразити так:
де
- це називається цільова функція ( функція економічний)
називається простір R n вектора X, відповідно C - простір діяльності
вектор називається ресурс вектор
називається простір R m ресурсний простір.
Канонічні форми
який перевіряє систему обмежень рішення проблеми (можливе рішення);
- називається рішення обмежень, яке перевіряє умови невід'ємності графік або допустиме рішення;
- викликається програма, для якої виконується запитуваний кінець функції оптимальна програма.
Нехай задача лінійного програмування буде у стандартній формі.
Можливо, обмеження типу нерівності подаються у вигляді обмежень типу рівності шляхом додавання (або віднімання) в одному з термінів нерівності терміна, який називається змінний ecart або компенсаційна змінна.
Позначаємо вектори стовпців матриці A,; тоді систему обмежень можна записати:
Нехай B - основа в просторі. Примітка для одного з векторів основи B. Або базовий розчин відповідає основі B. Основа B, яка веде до програми, називається допустима основа; якщо це не програма, ми говоримо, що B є можливо.
Моделі лінійного програмування, що зустрічаються в економічній практиці
Серед найпоширеніших економічних проблем, модельованих за допомогою лінійного програмування, ми представляємо наступне:
а) проблема планування виробництва
Підприємство виробляє в асортименті та має m ресурсів. Потрібно організувати виробництво, якщо відомі обсяг наявних ресурсів, конкретні споживання та унітарні переваги.
Ми ототожнюємо організацію виробництва при створенні моделі PPL із виробничим планом.
Або: кількість доступних ресурсів Ri
aij - кількість ресурсів Ri, необхідних для споживання для асортименту Sj
cj - вигода, яку приносить асортимент Sj.
Позначаємо xj - кількість асортиментів типу Sj. Тоді план виробництва представляється вектором стовпців
Отже, PPL можна заявити наступним чином:
Для визначення його координат за умов:
отримання максимальної вигоди
б) проблема харчування
Дієта повинна містити поживні речовини в кількості, що міститься в їжі
Нехай aij - кількість речовини, що міститься в їжі Aj,
cij-одиниця вартості їжі Aj.
Визначте кількість їжі xj, необхідну для забезпечення необхідного рівня речовин, щоб загальна вартість дієти була мінімальною.
Математична модель задачі: так
в) Транспортна проблема
Той самий товар повинен бути перерозподілений від m-виробничих центрів (постачальник) до n-центрів збуту (бенефіціар), наявність постачальника становить, потреба бенефіціара Bj дорівнює bj, собівартість одиниці від постачальника до бенефіціара Bj cij. Організація перевезення полягає у визначенні кількості продукції, яку потрібно транспортувати від кожного постачальника до кожного бенефіціара, щоб загальна вартість транспорту була мінімальною.
Відзначимо xij - кількість, яка транспортується від постачальника до бенефіціара Bj.
Враховуючи, що загальна сума, доступна для постачальників, дорівнює сумі, необхідній для бенефіціарів, проблема стає збалансованою, і модель лінійного програмування є:
хв
г) Проблема змішування
Продукт отримують із суміші n-сировини Mj, одиниця сировини Mj містить aij одиниць речовини. Продукт повинен містити щонайменше dh, одиниць речовини і не більше dk, одиниць речовини, вартість одиниці сировини Mj становить cj .
Визначте xj кількості сировини Mj, яка повинна входити до складу продукту, щоб його вартість була мінімальною. Математична модель задачі, сформульованої як PPL, є:
,
,