Каноническая форма задачи линейного программирования
Канонической формой записи ЗЛП называют задачу
; (2.24)
, (2.25)
. (2.26)
Существуют 5 основных признаков представления задачи линейного программирования в канонической форме:
1) минимизация целевой функции (2.24);
2) запись системы ограничений в виде строгих равенств (2.25);
3) условие неотрицательности на все переменные (2.26);
4) наличие в системе ограничений исходного базиса;
5) неотрицательность всех свободных членов в системе ограничений.
Приведение задачи линейного программирования к канонической форме
1. если исходная ф-я бала на max, то *(-1) и исследуем ее на min
2. Если в неравенстве стоит знак <= то в это нер-во добавляется новый х со знаком «+», если знак >= то со знаком «-»
Геометрический смысл задачи линейного программирования
Геометрическая интерпретация задач дает возможность наглядно представить их структуру, выявить особенности и открывает пути исследования более сложных свойств.
область допустимых решений задачи есть выпуклое множество.
Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы. Совокупность этих точек (решений) наз. многоугольником решений – это точка, отрез, луч, многоугольник, неограниченной многоугольной областью.
|
|
|
геометрическая задача линейного программирования представляет собой отыскание такой точки многогранника рещений, координаты которой доставляют линейной функции минимальное значение, причем допустимыми решениями служат все точки многогранника решений.
геометрической интерпретации целевой функции: уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).
Свойства решений задачи линейного программирования (без док)
Т е о р е м а 1.Множество всех планов задачи линейного программирования выпукло.
Т е о р е м а 2. Линейная функция задачи линейного программирования достигает своего минимального значения в угловой точке многогранника рещений. Если линейная функция принимает минимальное значение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек.
|
|
|
Доказать, что множество допустимых решений ЗЛП является выпуклым множеством
Множество наз выпуклым если с любыми двумя точками оно содержит их произвольную линейную комбинацию.
Множество наз замкнутым если оно содержит в себе граничные точки
Точка наз. угловой если она не может быть представлена виде дух линейных комбинаций его других точек.
Дата добавления: 2018-05-12; просмотров: 944; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!