Лінійне програмування

Лінійне програмування

Означення. Лінійне програмування - це розділ математичного програмування, який досліджує моделі екстремальних задач з лінійної цільової функцією і системою обмежень, що складається з лінійних рівнянь і нерівностей. 

Класичні методи знаходження екстремуму функції багатьох змінних пов'язані з рішенням системи рівнянь: 

Очевидно, для лінійної функції Z: 

А так як всі коефіцієнти одночасно не можуть бути рівні 0, то всередині області, утвореної системою обмежень, екстремальної точки не існує. 

Вона може існувати тільки на границі  області, але застосування класичних методів також неможливо, оскільки частинні похідні функції Z по всім змінним також рівні константам. Тому для вирішення завдань лінійного програмування (ЗЛП) були створені спеціальні методи.

Приклад. Знайти максимум функції  в області:  (прямокутний рівнобедрений трикутник).

1)По теоремі Вейерштрасса максимум існує для функції - область обмежена і замкнена, функція неперервна в цій області. З математики відомо, що в точці максимуму (і мінімуму) усі частинні похідні дорівнюють нулю в тому випадку, якщо ці похідні існують. Але в нашому випадку всередині області, там де всі частинні похідні існують: . Отже, точки максимуму (і мінімуму) обов'язково повинні бути розташовані на границі області.

Припустимо, точка максимуму розташована на відрізку, але не в кутовій точці. Рівняння відрізка, що проходить через точки (x₁,y₁) и (x₂,y₂) можно записати в вигліді:. Підставимо рівняння прямої:.   

Функція на границі області лінійна, приймати максимальні (і мінімальні) значення вона може тільки при , тобто тільки в кутових точках.
Аналогічно можна довести, що в загальному випадку лінійна функція може приймати оптимальні значення тільки в кутових точках. 

Приклад задачі лінійного програмування. Задача оптимального виробничого планування 

Для виготовлення n видів продукції P₁,…,P_n використовується m видів сировини S₁,…,S_m,   запаси якого обмежені і становлять відповідно b₁,…,b_m  одиниць. Відомо, що на виробництво одиниці продукції P_j (j=)  витрачається а_ij  одиниць ресурсу S_i (i=,а прибуток від реалізації одиниці продукції P_j (j=  становить с_j(j=.

Потрібно визначити план виробництва, який дозволяє при наявних ресурсах отримати максимальний прибуток підприємства від реалізації продукції. 

Складемо математичну модель завдання.

Позначимо через x_j (j= плановане до випуску кількість продукції Р_j  (j=, а через  Z (х₁,…, x_n) - прибуток підприємства від реалізації всієї продукції.
Тоді планом виробництва буде вектор Х = (х₁,…,х_n), що показує, яку кількість продукції кожного виду буде заплановано. Змінні  х₁,…,х_n - керовані змінні.
Мета рішення задачі (критерій оптимальності) - максимізувати прибуток:

Z = c₁x₁ + c₂x₂ +. . . + c_nx_n .

Сумарні витрати ресурсу S_i (i=складають:.

У силу обмеженості ресурсу S_i величиной b_i отримаємо систему обмежень: .

На змінні х_j повинно бути накладено умову невідємності, тобто продукція Р_j   може або випускатися (x_j > 0), або не випускатися (x_j=0).

Отже, математична модель прийме вигляд:

Поняття допустимого рішення, області допустимих рішень, оптимального рішення задачі лінійного програмування

Визначення 1. Вектор X, що задовольняє системі обмежень ЗЛП, в тому числі і умові невідємності,  якщо вони є, називається допустимим рішенням ЗЛП.
Визначення 2. Сукупність усіх допустимих рішень утворює область допустимих рішень (ОДР) ЗЛП.
Визначення 3. Допустиме рішення, для якого цільова функція досягає максимуму (або мінімуму), називається оптимальним рішенням. Будемо позначати оптимальне рішення

Опуклі множини

Визначення 4. Вектор  називається опуклою лінійною комбінацією векторів  якщо коефіцієнти задовольняють умовам.

Зокрема, опуклої лінійної комбінацією двох векторів (точок) )  X ¹ та X ² является є вектор: , де  
Визначення 5.  Множина D векторів (точок) лінійного простору називається опуклою, якщо разом з будь-якими її двома точками  та   йому належить відрізок, що з'єднує ці точки. Аналітично умова опуклості множини   записується таким чином: для будь-яких,  та довільного: виконується умова.

На рис зображені опуклі множини (а, б) і множина, яка не є опуклою (в).

Визначення 6.  Точка X¹  опуклої множини D називається його кутовий (крайньою) точкою, якщо вона не може бути представлена ​​опуклої лінійної комбінацією двох інших точок цієї множини (не є внутрішньою точкою ні для якого відрізка, кінці якого належать множині D).

Наприклад, крайніми точками трикутника є його вершини, крайніми точками кола - точки кола, яка його обмежує. Однак не всяка опукла множина має крайні точки. Пряма, площина, півплощини, простір, півпростір кутових точок не мають.

Визначення 7.   Опуклим многогранником  називається замкнена обмежена опукла множина, що має кінцеве число крайніх (кутових) точок.

Теорема. Будь-яка точка опуклого багатогранника може бути представлена ​​як опукла лінійна комбінація його вершин (крайніх точок). 

Графічне зображення розвязку задачі лінійного програмування 

Припустимо, що число невідомих рівне 2  в задачі лінійного програмування. Побудуємо область, яку задають обмеження, при цьому до числа обмежень ще треба додати прямі х=0, y=0 та  m=m+2.

Приклад. Знайти мінімум для функціїпри обмеженнях на змінні: , ,, .

Будемо вводити  обмеження для цього прикладу  в текстовому файлі таким чином:

1 2 <  5

6 2 >  8

1 5 >  6

2 1 > -4 

На першому місці задаємо коефіцієнт при х₁, на другому при х₂ . Знаки нерівностей будемо задавати тільки в вигляді <,>,=.

Область обмежень може бути:

1) Cкінчена, непорожня.

2) Пуста множина.

3) Непорожня, нескінчена.

Алгоритм повинен побудувати область обмежень в випадку 1) і видати повідомлення для 2) та 3) 

Алгоритм 

1) Знайдемо всі попарні точки перетину прямих, що утворюють область обмежень.

Якщо  прямих m і серед них немає паралельних, то число точок перетину прямих рівне.

2) Перевіримо кожну точку перетину за допомогою обмежень: кожна точка перетину прямих повина задовольняти всім обмеженням. Для цього підставляємо координати точки в ріняння обмеження і перевіряємо знак нерівності. Точки, які не задоволняють обмеженням – відкинемо.

Позначимо число точок, що задовольняють обмеженням  К, а масив точок x_i,y_i i=1,K. Цей масив буде утворювати вершини області обмежень. Але треба ці точки правильно з’єднати, вони можуть бути розташовані в будь-якому порядку. 

3) Якщо К=0, то обмеження суперечливі, область допустимих значень – порожня множина. Повідомлення, кінець алгоритму

4) З’єднаємо між собою точки. Область обмежень повина бути опуклою.

А) Виберемо першу точку -  M₁(x₁,y₁), i=1, Kol=1, в цій змінній підраховуємо, скільки точок області уже є.

Б) j=1,K; j≠i;

В) Наступна точка області обмежень: M_j(x_j,y_j); Перевірямо умову: пряма, що проходить через точки M_iM_j не повинна розділяти множину точок вершин так що частина точок лежить  з однієї сторони прямої, частина з іншої.

Для цього підставляємо всі точки в рівняння прямої M_iM_j. Наприклад, якщо рівняння прямої  M_iM_j задане в вигляді f(x,y)=a*x+b*y+c, то при підстановці координат всіх інших точок в f(x,y) значення повинні бути або >0, або <0. Перебираємо всі точки j=1,K, j≠i. Якщо точка знвайдена, то Kol=Kol+1;

Г) Якщо Kol=K то 5).

5) Треба перевірити, щоб кожний відрізок області обмежень пунку 4) лежав на деякій прямій, що задані були спочатку. Якщо наша область обмежень скінчена, то цей пункт не потрібен, якщо ні то 4) буде давати невірний результат. В цьому випадку потрібно видати повідомлення.

З повагою ІЦ "KURSOVIKS"!