Канонічна форма задачі лінійного програмування
У загальному випадку задача лінійного програмування записується так, що обмеженнями є як рівняння, так і нерівності, а змінні можуть бути як невід'ємними, так і довільно змінюються. У тому випадку, коли всі обмеження є рівняннями і всі змінні задовольняють умові незаперечності, завдання лінійного програмування називають канонічною. Вона може бути представлена в координатної, векторної або матричної записи.
1. Канонічна задача лінійного програмування в координатної запису має вигляд
.
У більш компактній формі це завдання можна записати, використовуючи знак підсумовування,
2. Канонічна задача лінійного програмування в векторної записи має вигляд
3. Канонічна задача лінійного програмування в матричної записи має вигляд
Тут А - матриця коефіцієнтів системи рівнянь, Х - матриця-стовпець змінних задачі, - матриця-стовпець правих частин системи обмежень.
Нерідко використовуються завдання лінійного програмування, звані симетричними. які в матричної записи мають вигляд
1.4. Приведення загальної задачі лінійного програмування
до канонічної формі
У більшості методів вирішення завдань лінійного програмування передбачається, що система обмежень складається з рівнянь і природних умов невід'ємності змінних. Однак при складанні математичних моделей економічних задач обмеження в основному формуються в системи нерівностей, тому необхідно вміти переходити від системи нерівностей до системи рівнянь. З цією метою доведемо наступну теорему.
Теорема 1.1. Про заміну нерівності рівнянням. Кожному рішенню нерівності
відповідає єдине рішення рівняння
і, навпаки, кожному рішенню рівняння (1.13) і нерівності (1.14) відповідає єдине рішення нерівності (1.12).
Доведення. Нехай - розв'язок нерівності (1.12), тоді. Позначимо різницю правої і лівої частин цієї нерівності через. т. е.
.
Очевидно. Підставами в рівняння (1.13) замість змінних значення. отримаємо
.
Таким чином, задовольняє рівняння (1.13) і нерівності (1.14). Значить доведена перша частина теореми.
Нехай тепер задовольняє рівняння (1.13) і нерівності (1.14), т. Е. Маємо
Відкидаючи в лівій частині останнього рівності неотрицательную величину. отримуємо
,
т. е. задовольняє нерівності (1.12). Теорема доведена.
Якщо нерівність. то додаткову неотрицательную змінну необхідно ввести в його ліву частину зі знаком мінус, т. е..
Невід'ємні змінні, що вводиться в обмеження нерівності для перетворення їх в рівняння, називаються додатковими змінними. Додаткові змінні вводяться в цільову функцію з нульовими коефіцієнтами і тому не впливають на її значення.
У тому випадку, коли задача має довільно змінюються змінні, то будь-яку таку змінну замінюють різницею двох невід'ємних змінних, т. Е.. де і .
Іноді виникає необхідність перейти в завданні від знаходження мінімуму до знаходження максимуму або навпаки. Для цього достатньо змінити знаки всіх коефіцієнтів цільової функції на протилежні, а в іншому завдання залишити без зміни. Оптимальні рішення отриманих таким чином задач на максимум і мінімум збігаються, а значення цільових функцій на оптимальних рішеннях відрізняються тільки знаком.
Приклад 1.1. Привести до канонічного вигляду завдання лінійного програмування.
Рішення. Перейдемо до задачі на відшукання максимуму цільової функції. Для цього змінимо знаки коефіцієнтів цільової функції. Для перетворення в рівняння другого і третього нерівностей системи обмежень введемо невід'ємні додаткові змінні (на математичній моделі ця операція відзначена буквою Д). Мінлива вводиться в ліву частину другої нерівності зі знаком "+", так як нерівність має вигляд. Мінлива вводиться в ліву частину третього нерівності зі знаком "-", так як нерівність має вигляд. У цільову функцію змінні вводяться з коефіцієнтом, рівним нулю. Змінну. на яку не накладено умова позитивності замінюємо різницею. . Записуємо завдання в канонічному вигляді
.
У деяких випадках виникає необхідність приведення канонічної задачі до симетричної задачі. Розглянемо приклад.
Приклад 1.2. Привести до симетричного виду завдання лінійного програмування
.
Рішення. Методом Жордана-Гаусса наведемо систему рівнянь-обмежень завдання до еквівалентної дозволеної. Одночасно дозволені невідомі виключимо з цільової функції. Для цього в таблиці рішення задачі (табл. 1.1) поряд з коефіцієнтами рівнянь системи обмежень в додатковому рядку запишемо коефіцієнти цільової функції. В останньому стовпці додаткової рядки (на місці правої частини рівнянь) запишемо вільний член цільової функції, рівний нулю. При обчисленнях враховуємо, що дозволяє елемент в останньому рядку (в цільової функції) вибирати не можна.
Т а б л і ц а 1.1
Число -9, отримане в останньому стовпці останнього рядка таблиці необхідно записати в цільову функцію з протилежним знаком. В результаті даних перетворень завдання приймає наступний вигляд:
.
Так як змінні невід'ємні, відкинувши їх, можна записати задачу в симетричному вигляді
.