Головна

Властивості задач ЛП

  1.  I. Завдання випробування
  2.  I. Завдання дослідження
  3.  I. Завдання на молярность.
  4.  I. Завдання на молярность. 1 сторінка
  5.  I. Завдання на молярность. 10 сторінка
  6.  I. Завдання на молярность. 2 сторінка
  7.  I. Завдання на молярность. 3 сторінка

Вище в лекції по ЛП було показано, що будь-яке завдання ЛП м. Б. представлена ??у вигляді загальної, канонічної чи стандартної задачі. Причому, від одного завдання можна перейти до іншої.

Будемо розглядати канонічну задачу, в якій система обмежень - система рівнянь.

Теорема 4. Безліч всіх допустимих рішень системи обмежень ЗЛП (завдання лінійного програмування) є опуклим, т. Е. Є опуклим багатогранників (або опуклою багатогранною областю). Будемо називати надалі - многогранником рішень.

Теорема 5. Якщо завдання ЛП має оптимальне рішення, то лінійна функція приймає макс (мін) значення в одній з кутових точок багатогранника рішень.

Ця теорема є фундаментальною, т. К. Вона вказує принциповий шлях рішення ЗЛП. Дійсно, згідно з цією теоремою замість дослідження нескінченної кількості допустимих рішень для знаходження серед них шуканого оптимального рішення необхідно досліджувати лише кінцеве число кутових точок багатогранника рішень.

Теорема 6. Кожному допустимому базисного вирішення ЗЛП відповідає кутова точка багатогранника рішень, і навпаки, кожній кутовій точці багатогранника рішень відповідає допустимий базисний розв'язок.

З теорем 5 і 6 випливає наслідок: якщо ЗЛП має оптимальне рішення, то воно збігається, по крайней мере, з одним з її допустимих базисних рішень.

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




 лінійне програмування |  Поняття економіко-математичної моделі |  Завдання про розкрої матеріалів. |  Система m лінійних рівнянь з n змінними |  Геометричний сенс рішень нерівностей, рівнянь і їх систем |  симплексний метод |  Знаходження оптимуму лінійної функції |  Особливі випадки симплексного методу |  сімплексні таблиці |

© um.co.ua - учбові матеріали та реферати