Задачі лінійного програмування постановка задачі: методи рішення і формування
Етапи постановки завдань
Загальна постановка задачі лінійного програмування та її формулювання ставиться до перекладу реальної проблеми до виду математичних рівнянь, які можуть бути вирішені.
Визначають число, яке виявляє поведінку цільової функції для оптимізації.
Знаходять набір обмежень і виражають їх у вигляді лінійних рівнянь або нерівностей. Це встановить область в n-мірному просторі оптимізованих функцій.
Необхідно накласти умову неотрицательности на змінні задачі, тобто всі вони повинні бути позитивними.
Виражають функцію у формі лінійного рівняння.
Оптимізують функцію графічно або математично, коли виконується математична постановка задачі лінійного програмування.
Графічний спосіб
Графічний метод використовується для виконання завдань LP двох змінних. Цей метод не застосовується для вирішення проблем, які мають три або більше змінних рішень.
Стандартна задача максимізації невідомих проблем LP, в якій збільшують функцію, за умови обмежень виду:
x ≥ 0, y ≥ 0, z ≥ 0 і подальші обмеження форми:
Ax + By + C z +. , ≤ N,
де А, В, С і N є неотрицательными числами.
Нерівність має бути «≤», а не «=» або «≥».
Графічний метод LP з двома невідомими полягає в наступному:
Встановлюють можливі області графіка.
Обчислюють кутові координати точок.
Підставляють їх з метою побачити оптимальне значення. Цей момент дає рішення задачі LP.
Мінімізують функцію і, якщо її невід’ємні коефіцієнти, рішення існує.
Визначення існуючих рішень:
Обмежують область, додавши вертикальну лінію праворуч від крайньої правої кутової точки і горизонтальну лінію вище найвищої кутової точки.
Розраховують координати нових кутових точок.
Знаходять кутову точку з оптимальним значенням.
Якщо воно має місце у вихідній точці необмеженої області, то у завдання LP є рішення в даній точці. Якщо ні, то вона не має оптимального рішення.
