Сформулюйте основні аналітичні властивості розв’язків задач лінійного програмування.

Властивості розв’язків задачі лінійного програмування формулюються у вигляді чотирьох теорем.

Властивість 1. (Теорема 2.2) Множина всіх планів задачі лінійного програмування опукла.

Властивість 2. (Теорема 2.3) Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин її багатогранника розв’яз­ків. Якщо ж цільова функція набуває екстремального значення більш як в одній вершині цього багатогранника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією таких вершин.

Властивість 3. (Теорема 2.4) Якщо відомо, що система векторів A ₁, A ₂, …, A_k (k ≤ n) у розкладі A ₁ x ₁ + A ₂ x ₂ + … + A_nx_n = A ₀, X ≥ 0 лінійно незалежна і така, що

A ₁ x ₁ + A ₂ x ₂ + … + A_kx_k = A ₀,

де всі x_j ≥ 0, то точка X = (x ₁, x ₂, …, x_k, 0, …, 0) є кутовою точкою багатогранника розв’язків.

Властивість 4. (Теорема 2.5) Якщо X = (x ₁, x ₂, …, x_n) — кутова точка багатогранника розв’язків, то вектори в розкладі A ₁ x ₁ + + A ₂ x ₂ + … + A_nx_n = A ₀, X ≥ 0, що відповідають додатним x_j, є лінійно незалежними.

30. Які ви знаєте властивості опорних планів транспортної задачі?

Якщо умови транспортної задачі і її опорний план записані у вигляді табл. 5.1, то клітини, в яких  (ненульові значення поставок), називаються заповненими, всі інші — пустими. Заповнені клітини відповідають базисним змінним і для невиродженого плану їх кількість дорівнює m + n – 1.

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

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

Теорема 5.1. Щоб деякий план транспортної задачі був опо р­ним, необхідно і достатньо його ациклічності.

Всякий план не може містити від’ємних компонент, а кількість лінійно незалежних між собою векторів у обмеженнях транспортної задачі завжди дорівнює m + n – 1, так що кількість відмінних від нуля компонент плану, якщо він опорний, не перевищує цієї величини.

Теорема 5.2. (Наслідок теореми 5.1.) Будь-яка сукупність з  клітин матриці транспортної задачі утворює цикл.

Теорема 5.3. Якщо всі запаси  і всі потреби  є невід’ємними цілими числами, то будь-який опорний план складається із значень, що є цілими числами.

 

31.Побудуйте просту економіко-математичну модель. Запишіть до неї двоїсту. Дайте економічну інтерпретацію двоїстих оцінок.

Кожна задача лінійного програмування пов’язана з іншою, так званою двоїстою задачею.

Економічну інтерпретацію кожної з пари таких задач розглянемо на прикладі виробничої задачі (§ 2.1).

Пряма задача:                                                         max F = c₁x₁ + c₂x₂ + … + c_nx_n                                                                                                                                     (3.1)

                                 за умов:                                                                                  (3.2)

Необхідно визначити, яку кількість продукції кожного j -го виду  необхідно виготовляти в процесі виробництва, щоб максимізувати загальну виручку від реалізації продукції підприємства. Причому відомі: наявні обсяги ресурсів — ; норми витрат і- го виду ресурсу на виробництво одиниці j -го виду продукції — , а також  — ціни реалізації одиниці j -ої продукції.

Розглянемо тепер цю саму задачу з іншого погляду. Допустимо, що за певних умов доцільно продавати деяку частину чи всі наявні ресурси. Необхідно визначити ціни ресурсів. Кожному ресурсу  поставимо у відповідність його оцінку . Умов­но вважатимемо, що  — ціна одиниці і- го ресурсу.

На виготовлення одиниці j -го виду продукції витрачається згід­но з моделлю (3.1)—(3.3) m видів ресурсів у кількості відповідно . Оскільки ціна одиниці і- го виду ресурсу дорівнює , то загальна вартість ресурсів, що витрачаються на виробництво одиниці j -го виду продукції, обчислюється у такий спосіб:

.

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

.

Загальну вартість ресурсів можна виразити формулою:

.

Отже, в результаті маємо двоїсту задачу:

                                                                                                                      (3.4)

                                 за умов:                                                                        (3.5)

                                                                                                          (3.6)

Тобто необхідно визначити, які мінімальні ціни можна встановити для одиниці кожного і- го виду ресурсу , щоб продаж ресурсів був доцільнішим, ніж виробництво продукції.