Сформулюйте основні аналітичні властивості розв’язків задачі лінійного програмування.
Властивість 1. (Теорема 1) Множина всіх планів задачі лінійного програмування опукла.
Властивість 2. (Теорема 2) Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин многогранника розв’язків. Якщо цільова функція набуває екстремального значення більш як в одній вершині цього многогранника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією таких вершин.
Властивість 3. (Теорема 3) Якщо відомо, що система векторів А1, А2,…, Аk (k≤n) у розкладі А1х1+А2х2+…+Аnxn=А0,
де всі хj≥0, то точка Х=(х1, х2,…, хk, 0,…, 0) є кутовою точкою багатогранника розв’язків.
Властивість 4. (Теорема 4) Якщо Х=(х1, х2,…, хn) – кутова точка багатогранника розв’язків, то вектори в розкладі А1х1+А2х2+…+Аnxn=А0, Х≥0, що відповідають додатним хj, лінійно незалежні.
30. Які ви знаете властивості опорних планів транспортної задачі?
Опорним планом транспортної задачі є такий допустимий її план, що містить не більш ніж m + n – 1 додатних компонент, а всі інші його компоненти дорівнюють нулю. Такий план є невиродженим. Якщо ж кількість базисних змінних менша ніж m + n – 1, то маємо вироджений опорний план.
Якщо умови транспортної задачі і її опорний план записані у вигляді транспортної таблиці,то клітини, в яких 
(ненульові значення поставок), називаються заповненими, всі інші — пустими. Заповнені клітини відповідають базисним змінним і для невиродженого плану їх кількість дорівнює m + n – 1.
|
|
|
Циклом називають таку послідовність заповнених клітин таблиці, яка задовольняє умову, що лише дві сусідні клітини містяться або в одному рядку, або в одному стовпці таблиці, причому перша клітина циклу є і його останньою клітиною. Якщо для певного набору заповнених клітин неможливо побудувати цикл, то така послідовність клітин є ациклічною.
1)Кількість клітин, які утворюють будь-який цикл транспортної задачі, завжди парна.
2)Щоб деякий план транспортної задачі був опорним, необхідно і достатньо його ациклічності.
3)Будь-яка сукупність з 
клітин матриці транспортної задачі утворює цикл.
4)Якщо всі запаси 
і всі потреби 
є невід’ємними цілими числами, то будь-який опорний план складається із значень, що є цілими числами.
Побудуйте просту економіко-математичну модель. Запишіть до неї двоїсту. Дайте економічну інтерпретацію двоїстих оцінок.
max F = –5x1 + 2x2;
Розв’язання. Перш ніж записати двоїсту задачу, необхідно пряму задачу звести до стандартного вигляду. Оскільки цільова функція F максимізується і в системі обмежень є нерівності, то вони мусять мати знак « 
». Тому перше обмеження задачі помножимо на (–1). Після цього знак нерівності зміниться на протилежний. Отримаємо:
|
|
|
max F = –5x1 + 2x2;
Тепер за відповідними правилами складемо двоїсту задачу:
;
Економічна інтерпретація двоїстих оцінок.
Якщо для виготовлення всієї продукції в обсязі, що визначається оптимальним планом Х*, витрати одного і-го ресурсу строго менші, ніж його загальний обсяг 
, то відповідна оцінка такого ресурсу 
(компонента оптимального плану двоїстої задачі) буде дорівнювати нулю, тобто такий ресурс за даних умов для виробництва не є «цінним». Якщо ж витрати ресурсу дорівнюють його наявному обсягові 
, тобто його використано повністю, то він є «цінним» для виробництва, і його оцінка 
буде строго більшою від нуля.
У разі, коли деяке j-те обмеження виконується як нерівність, тобто всі витрати на виробництво одиниці j-го виду продукції перевищують її ціну сj, виробництво такого виду продукції є недоцільним, і в оптимальному плані прямої задачі обсяг такої продукції 
дорівнює нулю. Якщо витрати на виробництво j-го виду продукції дорівнюють ціні одиниці продукції 
, то її необхідно виготовляти в обсязі, який визначає оптимальний план прямої задачі 
.
Двоїсті оцінки є унікальним інструментом, який дає змогу зіставляти непорівнянні речі. Очевидно, що неможливим є просте зіставлення величин, які мають різні одиниці вимірювання. Якщо взяти як приклад виробничу задачу, то цікавим є питання: як змінюватиметься значення цільової функції (може вимірюватися в грошових одиницях) за зміни обсягів різних ресурсів (можуть вимірюватися в тоннах, м2, люд./год, га тощо).
|
|
|
Дата добавления: 2018-02-18; просмотров: 1154; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!