13.Основні властивості розв’язків задачі лінійного програмування

Властивості розв’язків задачі лінійного програмування формулюються у вигляді чотирьох теорем (доведення теорем та їх наслідки наведено нижче).Властивість 1. (Теорема 2.2) Множина всіх планів задачі лінійного програмування опукла.Властивість 2. (Теорема 2.3) Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин її багатогранника розв’язків. Якщо ж цільова функція набуває екстремального значення більш як в одній вершині цього багатогранника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією таких вершин.Властивість 3. (Теорема 2.4) Якщо відомо, що система векторів A1, A2, …, Ak (k ≤ n) у розкладі A1x1 +A2x2 + … + Anxn = A0, X ≥ 0 лінійно незалежна і така, що A1x1 + A2x2 + … + Akxk = A0,де всі xj ≥ 0, то точка X = (x1, x2, …, xk, 0, …, 0) є кутовою точкою багатогранника розв’язків.Властивість 4. (Теорема 2.5) Якщо X = (x1, x2, …, xn) — кутова точка багатогранника розв’язків, то вектори в розкладі A1x1 + + A2x2 + … + Anxn = A0, X ≥ 0, що відповідають додатним xj, є лінійно незалежними.Доведемо сформульовані теореми.Теорема 2.2. Множина всіх планів задачі лінійного програмування опукла. Доведення. Необхідно довести, що коли X1 та X2 — плани задачі лінійного програмування (2.1)—(2.3), то їх опукла комбінація також є планом задачі.Так як X1 і X2 — плани задачі, то виконуються такі співвідношення:AX1 = A0, X1 ≥ 0; AX2 = A0, X2 ≥ 0.Якщо підставити в систему обмежень значення X, то отримаємо: Отримали, що X задовольняє систему обмежень задачі лінійного програмування (2.2), і оскільки , тобто задовольняють і умову (2.3). У такий спосіб доведено, що Х — план задачі лінійного програмування.Теорема 2.3. Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин багатогранника розв’язків. Якщо цільова функція набуває екстремального значення більш як в одній вершині цього багатогранника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією таких вершин.

17.Метод штучного базису

випадок, коли система обмежень задачі лінійного програмування містила одиничну матрицю порядку m. Проте більшість задач не можна звести до потрібного вигляду. В такому разі застосовується метод штучного базису.Розглянемо задачу лінійного програмування:

(2.60) (1)

(2)

Задача подана в канонічному вигляді і система обмежень (1) не містить одиничної матриці. Отримати одиничну матрицю можна, якщо до кожного рівняння в системі обмежень задачі додати одну змінну . Такі змінні називають штучними. (Не обов’язково кількість введених штучних змінних має дорівнювати m. Їх необхідно вводити лише в ті рівняння системи обмежень, які не розв’язані відносно базисних змінних.) Допустимо, що система рівнянь (1) не містить жодного одиничного вектора, тоді штучну змінну вводять у кожне рівняння: (3)

У результаті додавання змінних у рівняння системи (1) область допустимих розв’язків задачі розширилась. Задачу з системою обмежень (3) називають розширеною, або М-задачею. Розв’язок розширеної задачі збігатиметься з розв’язком початкової лише за умови, що всі введені штучні змінні в оптимальному плані задачі будуть виведені з базису, тобто дорівнюватимуть нулеві. Тоді система обмежень (3) набуде вигляду (1) (не міститиме штучних змінних), а розв’язок розширеної задачі буде розв’язком і задачі (0)—(2).Згідно з симплексним методом до базису вводять змінні, які покращують значення цільової функції. Для даної задачі на максимум вони мають його збільшувати. Отже, для того, щоб у результаті процедур симплексних перетворень виключалися з базису штучні змінні, потрібно ввести їх у цільову функцію з від’ємними коефіцієнтами. Тобто цільова функція набуде вигляду:

(У разі розв’язання задачі на відшукання мінімального значення цільової функції вводять коефіцієнти, які є досить великими числами. Цільова функція тоді має вигляд: