Задачи линейного программирование. Задачи и постановка.

Линейное программирование – раздел математического программирование который изучает задачу определение экстремума линейной функции нескольких переменных при лененх ограничениях на переменные виде равенств и неравенств.

Методы решения данной задачи делятся на универсальные и специальные.

Классы задач: задачи оптимального использование ресурсов производства, задача оптимального выбора технологии, задача о смесях, задача о раскрое, задача о назначениях.

Формы записи задачи линейного программирование.

Стандартная формула ЗЛП – необходимо найти экстремум целевой функции имея систему ограничения неравенств, при условии неотрицательной всех переменных.

Каноническая форма ЗЛП – в канонической задаче линейного программирование необходимо найти экстремум целевой функции с использование системы ограничении равенств условии не отрицательности всех переменных.

Особенностью ЗЛП является то что экстремум целевой функции достигается на границы области допустимых решений(выпуклость обязательная, выпуклость анной функции гарантирует то что локальный экстремум совпадает с глобальным ).

//28-30 для лабы и по методе кон. Раб №1

Геометрическая интерпретация линейного программирование(в целевой функции не более 2 элементов , хоть она имеет ограничение на количество паромных но не имеет ограничении в какой форме она заданная ).

Теорема. Множество планов задачей программирование выпуклое.

X₁

8x₁+5x₂<40; -x₁+x₂<1; x₁>0 x₂>0

6

C

D

B

Y

X₂

б)

Лекция 5

X₁

ОДР

Область допустимых решений моет быть: пустой(множество планов пустое), система при этом не совместная(а)), представленная одной точке (б)), виде выпуклого многограннику(в)), неограниченной выпуклой многогранной областью(г))

Для вариантов представленных на рисунке с ограниченной областью допустимой могу встретиться 2 случая (б) в)) :

1. Vfrcbvev достигается в единой точке и ваксимум

2. Максимум может быть в 2 точках A и Б а следовательно на всем

X₁

Z

Z

X₂

X₁

(x_1опт,ч_2опт)

F min=

Функция не ограничена ни сверху, ни снизу

Fmax=

Fmin=-

Какую бы ли размерность вектор неизвестных X[x₁,x₂,….] канонической формы линейного програмирование , … планов задачи \, всегда опредеделяеться число независимых переменных, то есть разности, между числом переменных и рандом системы ограничении k=n-z r=m, n-число переменных, m-число ограничений.

Структура ЗЛП зависть от ранг r системы ограничений . Если система ограничений совместная, то матрица системы и ее расширенная матрица имеет один и тот же ранг r. При том ранг системы не может быть числа уравнений m. r<m . ранг не может бить больше общего числа переменных. Если ранг меньше числа n то при этом k значением k=n-r переменных можно присвоить какие либо значение, они являются не базовыми переными, а r-переменных можно линейно выразить через них.

//пз №1,№2