Ласкаво просимо до ProgramaciónLineal.net сайт, орієнтований виключно на зміст цієї важливої галузі досліджень операцій. Він прагне подати зміст у простій та дидактичній формі, що дозволяє студенту доповнити своє формальне вивчення цієї дисципліни. Запрошуємо користувачів ставити свої запитання та коментарі, пишучи на адресу [email protected]
SEP
2018 рік
Що таке лінійне програмування?
Модель Лінійне програмування (PL) вважає, що змінні рішення мають лінійну поведінку як у цільовій функції, так і як обмеження проблеми. У цьому сенсі лінійне програмування є одним із найбільш часто використовуваних інструментів у дослідженні операцій, оскільки за своєю природою обчислення полегшуються, і загалом воно дозволяє добре наблизити реальність.
Математичні моделі в основному поділяються на Детермістичні моделі (MD) або Стохастичні моделі (ME). У першому випадку (MD) вважається, що параметри, пов'язані з моделлю, відомі з абсолютною достовірністю, на відміну від стохастичних моделей, де всі або підмножина параметрів мають пов'язаний розподіл ймовірностей. Вступні курси з досліджень операцій, як правило, зосереджені лише на детермістичних моделях.
Основні припущення лінійного програмування: Лінійність, детерміновані моделі, реальні змінні, відсутність негативності.
ЗАЯВКИ
1. Дієта Проблема: (Штіглер, 1945). Він полягає у визначенні дієти ефективно з певного набору продуктів, щоб задовольнити харчові потреби. Кількість продуктів, які слід враховувати, їх харчові характеристики та їх вартість, дозволяють отримати різні варіанти моделей цього типу. Наприклад:
Змінні рішення:
Завдання: (Мінімізувати витрати на дієту) Мінімум 2X1 + 0,2X2 + 0,25X3
Обмеження: Відповідати харчовим потребам
- Ніацин: 3,2X1 + 4,9X2 + 0,8X3> = 13
- Тіамін: 1,12X1 + 1,3X2 + 0,19X3> = 15
- Вітамін С: 32X1 + 0X2 + 93X3> = 45
- Відсутність негативності: X1> = 0; X2> = 0; X3> = 0
Перевірте, використовуючи наш Модуль дозволу що оптимальним рішенням є X1 = 0, Х2 = 11,4677, Х3 = 0,483871, з оптимальним значенням V (P) = 2,4145.
2. Проблема розміру партії: (Вагнер і Вітін, 1958). Він полягає у пошуку оптимальної виробничої політики для задоволення коливаються вимог з часом з метою мінімізації виробничих та виробничих запасів, враховуючи наявність дефіцитних ресурсів.
Врахуйте, що фабрика може виробляти до 150 одиниць за кожен з 4 періодів, за які горизонт планування був розподілений, і додатково має таку інформацію:
Крім того, враховуйте, що існує Початкова інвентаризація з 15 одиниць, і очікуваний або відсутній попит не приймається, тобто весь попит за цей період повинен бути задоволений.
Змінні рішення:
Завдання: (Мінімізуйте виробничі витрати та запаси) Мінімум 6X1 + 4X2 + 8X3 + 9X4 + 2I1 + 1I2 + 2,5I3 + 3I4
Обмеження:
- Виробнича потужність за період: Xt = 0, It> = 0
Оптимальне рішення з використанням MS Excel Solver (Щоб побачити застосування цього інструменту, введіть ТУТ): Х1 = 115, Х2 = 150, Х3 = 100, Х4 = 150, I1 = 0, I2 = 70, I3 = 45, I4 = 0. Оптимальне значення V (P) = 3622,5
3. Транспортна проблема: (Хічкок, 1941; Канторович, 1942; Купманс 1947).
Завантажте книгу "Лінійне програмування" СЬОГОДНІ!
ЧАСТО ЗАДАВАНІ ПИТАННЯ (FAQ)
Ми щиро запрошуємо користувачів сайту надсилати свої запити, вводячи наші Контактний формуляр:
1. Як я можу перевірити, чи проблема лінійного програмування має нескінченні рішення?
В: Проблема PL має нескінченні рішення, якщо в підсумковій таблиці методу Simplex зменшена вартість, пов'язана з неосновною змінною, рівною нулю.
2. За допомогою двофазного симплексного методу, як мені переконатися, що пов’язана проблема неможлива?
В: Це перевіряється, якщо значення цільової функції після фази I відрізняється від нуля.
3. Чи може бути активне обмеження з пов'язаною тіньовою ціною, рівною нулю?
В: Так. Однак цей випадок є скоріше винятком, ніж правилом.
4. Чи неправильно вважати змінною, яка входить до бази, якусь неосновну змінну з від’ємною зниженою вартістю, але не «найбільш негативну» з усіх? (Симплексний метод)
В: Це не неправильно. Взагалі, він використовується як критерій вибору як вхідної змінної до основи тієї неосновної змінної з найбільш негативною зниженою вартістю, так що за меншу кількість ітерацій ми можемо досягти оптимуму, якщо він існує (швидкість конвергенції).
5. За допомогою симплексного методу, як можна виявити, що проблема лінійного програмування необмежена?
В: Ця ситуація виявляється, коли при обчисленні змінної, яка залишає основу, всі елементи Ykj колони j у таблиці є від'ємними, бо j індекс неосновної змінної з негативною зниженою вартістю.
6. Якщо подвійна проблема, пов’язана з моделлю лінійного програмування, необмежена, яка ситуація з первинною моделлю?
В: Якщо подвійна модель необмежена, то первинна неможлива.
7. Як ви перевіряєте, що лінійна задача неможлива?
В: Якщо всі записи у стовпці для від’ємної зменшеної вартості неосновної змінної від’ємні або дорівнюють нулю.
8. Що означає, що модель лінійного програмування неможлива?
В: Це в основному полягає в тому, що немає значень, які змінні рішення можуть прийняти таким чином, щоб було перевірено виконання всіх обмежень моделі.
НАШІ ПОСИЛАННЯ
Нижче подано збірник посилань, що цікавлять користувача.
СПОНСОРОВІ ПОСИЛАННЯ
Рекламні посилання, які можуть зацікавити користувача.
ЯК ВИКОРИСТОВУВАТИ ДОПОВНЕННЯ MS EXCEL SOLVER?
Solver - відмінна надбудова MS Excel, яка дозволяє вирішувати малі та середні проблеми лінійного програмування. У більшості заявок для студентських цілей достатньо вирішити ці випадки. Якщо вам потрібно встановити цю надбудову, ви можете перевірити наступне Підручник з інсталяції вирішувача. Тепер давайте подивимося, як це працює, на простому прикладі:
МАКС 10X + 16Y
С.А. 2X + 2Y. 1X + 2Y. . X> = 0, Y> = 0
КРОК 1. Параметри вводяться в електронну таблицю. Клітини, позначені жовтим кольором, відповідають "Зміна клітинок" або змінним рішення. Осередок C2 відповідає значенню цільової функції, яке задається як: A2 * A3 + C2 * C3. Клітини С5 і С6 зберігають значення або ліву сторону обмежень 1 і 2, визначаючись як A2 * A5 + B2 * B5 та A2 * A6 + B2 * B6, відповідно.
КРОК 2. Запускається програма Solver і завантажуються дані електронних таблиць.
КРОК 3. Після введення параметрів виберіть «Параметри». Потрапивши до цього меню, потрібно активувати параметри «Прийняти лінійну модель» та «Припустити невід’ємне». Потім виберіть «Прийняти», а потім «Вирішити».
КРОК 4. Якщо модель допускає рішення, отримуються результати. Для кращого розуміння вирішеної моделі рекомендується вибрати звіти, запропоновані Solver.
КРОК 5. Результати відображаються в клітинках, що змінюються, і перевіряється відповідність обмеженням проблеми. Оптимальним рішенням є Х = 2, Y = 2 з оптимальним значенням V (P) = 52. Крім того, обидва обмеження є активними, тобто виконуються однаково.
КРОК 6. Обираючи Звіти про відповіді, зокрема "Звіт про чутливість", отримують відповідну інформацію про запропоновану модель.
Щодо зміна клітин (змінних рішення) для коефіцієнтів у цільовій функції, що підтримують поточне Оптимальне Рішення, включений інтервал варіацій. Наприклад, C1 (Коефіцієнт, що супроводжує X у цільовій функції, наразі дорівнює 10) може змінюватися в наступному інтервалі, що гарантує поточне Оптимальне Рішення: = 8, 16>. Таким же чином інтервал для C2 (коефіцієнт, що супроводжує Y в цільовій функції, наразі дорівнює 16) дорівнює 10, 20>
Щодо обмеження, тіньова ціна обмеження 1 становить два, що справедливо до тих пір, поки варіація на правій стороні знаходиться в інтервалі = 6, 12>. Таким же чином, тіньова ціна для обмеження 2 дорівнює 6, дійсна в інтервалі варіацій праворуч між 4, 8>.
Щоб переглянути програму Solver для більшої програми, введіть ТУТ. Додатково рекомендується переглянути наступне Підручник з розв’язування.