Каноническая форма задачи линейного программирования



Канонической формой записи ЗЛП называют задачу

 ;                                                                                                (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; просмотров: 860; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!