Постановка основної задачі лінійного програмування (ЗЛП).
Задачі лінійного програмування є окремим випадком задачі математичного програмування. Вони отримали найбільше практичне застосування, їх розв’язання найповніше математично розроблено.
Як вже було сказано, в задачах лінійного програмування цільова функція є лінійною і в системі обмежень рівняння і нерівності також є лінійними, тобто всі невідомі входять до них в першій степені.
Сформулюємо загальну задачу лінійного програмування:
знайти сукупність значень 
змінних 
, 
, ..., 
, що задовольняють системі обмежень:
і умовам невід’ємності:
, 
, ..., 
( 
),
для яких лінійна функція
досягає екстремуму.
Окремі види математичної моделі задач лінійного програмування.
Симетрична форма математичної моделі задач лінійного програмування.
1.
2.
Канонічна форми математичної моделі задач лінійного програмування.
Перетворення однієї форми запису в іншу.
Лема. Будь-яку задачу ЛП можна звести до канонічної форми.
Доведення. Математична модель будь-якої задачі ЛП складається з двох частин: системи обмежень і оптимізуючої форми. У системі обмежень окремі обмеження можуть бути двох типів: рівняння або нерівності.
Покажемо, що будь-яку нерівність, введенням додаткової невідомої можна звести до рівності. Дійсно, нехай деяке обмеження має вигляд
(7)
Перепишемо його таким чином:
|
|
|
Введемо позначення 
За побудовою 
є невідомою величиною. Крім того, останнє співвідношення є рівнянням відносно невідомих 
(8)
Отже, обмеження-нерівність (7) і обмеження-рівність (8) є еквівалентними, тобто рівнозначними. Щоб перейти від (8) до (7), досить згадати, що , і виконати зворотні міркування.
Якщо в системі обмежень є декілька нерівностей, то треба ввести відповідне число додаткових невідомих.
Лему доведено.
Зауваження 1. Нові додаткові невідомі треба додавати до менших частин нерівностей, бо у протилежному випадку вони не будуть невід’ємними величинами. А це одна з вимог канонічної форми ЗЛП.
Зауваження 2. З метою уніфікації нові невідомі позначають 
і так далі.
Лема 2. Канонічна форма ЗЛП завжди може бути зведена до симетричної форми ЗЛП.
Доведення. Припустимо, що невідомі 
є вільними, а 
– базисними, ранг матриці системи обмежень (5) дорівнює 
. Розв’яжемо систему рівнянь (5) відносно базисних невідомих і нехай розв’язок має вигляд
(9)
Всі невідомі (9) невід’ємні, тому
Враховуючи це, поставимо у відповідність (9) таку еквівалентну систему нерівностей:
(10)
|
|
|
Введемо позначення 
, і перепишемо (10) у вигляді
Очевидно, що остання система обмежень збігається з (3) і рівносильна системі обмежень (5) у тому розумінні, що вони мають однакові розв’язки . Спосіб переходу від канонічної форми до симетричної такий, що зворотним шляхом дістаємо вихідну задачу з базисними і вільними невідомими.
Для закінчення доведення леми нагадаємо, що коли замість базисних невідомих 
підставити їхні значення (9) у форму (6) і згрупувати подібні члени, то вона набуде вигляду (4). Лему доведено.
Зауваження 3. Якщо в системі обмежень є рівності і нерівності, то звести таку задачу лінійного програмування до симетричної форми можна двома шляхами: 1) спочатку звести її до канонічної форми, а потім до симетричної; 2) виділити окремою групою рівності і звести їх до нерівностей за допомогою методу, описаному в лемі 2, підставити замість базисних невідомих знайдені значення в інші нерівності і оптимізуючу форму.
Із лем 1, 2 випливає така теорема.
Теорема 1. Канонічна і симетрична форми еквівалентні між собою.
Зауваження 4. Симетрична форма ЗЛП, рівносильна канонічній формі ЗЛП, може мати різні вигляди. Все залежить від того, які невідомі вибрати за базисні, а які – за вільні.
|
|
|
Різні форми задачі лінійного програмування можуть бути приведені одна до іншої за допомогою наступних зауважень.
1. На практиці інколи зустрічаються задачі, коли на змінні накладаються обмеження знизу 
. Цю складність легко обійти, вводячи нові змінні 
. Очевидно, що 
. В нових змінних ми вже маємо справу з задачею типу (3), (4) чи (5), (6).
2. Форму можна оптимізувати або на максимум, або на мінімум. Очевидно, що коли в точці 
функція 
досягає максимуму, то 
в точці досягає мінімуму. Якщо в математичній моделі вихідною є оптимізація форми на максимум, то вводячи функцію 
, для неї дістанемо оптимізацію на мінімум.
3. Неравенства вида 
, которые могут встретиться в системе ограничений, можно привести к неравенству 
умножением на (–1).
4. Равенство 
можно заменить системой неравенств
5. Каждое неравенство вида
(11)
добавлением неотрицательной переменной 
, приводится к уравнению
(12)
( при этом называется балансовой или выравнивающей переменной). При этом справедлива следующая
Пример. Привести к канонической форме задачу:
при ограничениях
Решение. Третье неравенство системы ограничений умножим на (–1) (чтобы изменить знак неравенства), а затем во второе и третье неравенства введем неотрицательные балансовые переменные 
и 
. Получим
|
|
|
Заменим переменные 
и 
, которые не подчинены условию неотрицательности, разностью неотрицательных переменных 
, 
. Наконец, вместо функции 
будем рассматривать функцию 
. Получим задачу
при ограничениях
Дата добавления: 2018-05-13; просмотров: 513; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!