Общие понятия

 

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

Определение: Гиперповерхностью в n-мерном пространстве называется геометрическое место точек, координаты которых удовлетворяют линейному уравнению(1), где-произвольные действительные числа

Пусть нам задана линейная функция F относительно переменных :

               F(x)= -это целевая функция или линейная форма.

 

                 F(x)=0              (2)

 

Возьмём c: F(x)=c  (3)

 

 

Определение: Гиперповерхность F(x)=c  называется гиперповерхностью равных значений  линейной формы

 

                F(x)=c₁

                              - данные гиперповерхности параллельны.

                F(x)=c₂

Пусть  у нас имеется n-точек.

Определение: Точка А называется выпуклой линейной комбинацией точек , если, гдеи

Определение: Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит их произвольную выпуклую, линейную комбинацию.

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

Определение: Точка множества называется граничной, если любой шар с центром в этой точке содержит как точки принадлежащие множеству, так и точке не принадлежащие ему.

Определение: Граничные точки образуют границу данного множества.

Определение: Замкнутым называют множество, содержащее все свои граничные точки.

Определение: Множество называется ограниченным, если существует шар радиуса конечной длины с центром в любой точке множества, который полностью содержит в себе данное множество. В противном случае множество называется неограниченным.  

Определение: Выпуклым многоугольником называется выпуклое, замкнутое, ограниченное множество на плоскости, имеющее конечное число угловых точек.

Определение:  Опорной прямой выпуклого многоугольника называется прямая, имеющая с многоугольником, расположенного по одну сторону от неё, хотя бы одну общую точку.

Теорема: Замкнутый ограниченный выпуклый многоугольник является выпуклой линейной комбинацией своих   угловых точек.

Теорема: Пересечение любого числа выпуклых множеств есть множество выпуклое (если только оно непустое).

 

 

Геометрическая интерпретация множества решений системы линейных неравенств с 2 неизвестными

В общем виде линейное неравенство с 2 переменными записывается следующим образом (1) или(2).

Каждому решению неравенств в (1) и (2) соответствует точка на плоскости . Геометрический смысл множества решений неравенств в (1) или (2) устанавливается теоремой.

Теорема: Множество решений линейного неравенства (1) служит одна из двух полуплоскостей, на которые всю плоскость делит прямая включая и эту прямую, а другая полуплоскость вместе с этой же прямой является  множеством решений линейного неравенства (2).

Возьмем систему из двух неравенств

Множество её решений это точки принадлежащие обеим полуплоскостям. По теореме 2 их пересечения выпуклое множество, имеющая конечное число угловых точек. Методом математический индукции установлено, что множеством решений системы m – линейных неравенств с двумя переменными является выпуклый многоугольник (если это пересечение пусто).

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

а) задача по использованию сырья

Виды сырья	Запасы сырья		Виды продукции
			П1	П2
S1 S2 S3 S4	b1 b2 b3 b4		a11 a21 a31 a41	a12 a22 a32 a42
Стоимость 1 ед. продукции		С1		С2

– количество единиц сырья вида S_i, расходуемого на производство одной единицы продукции вида П_j .

 

при условиях

   

 

б) задача о диете

Питательные вещества	Кол-во единиц питательных веществ, содержащихся в единице продукции вида					Количество питательного вещества в диете
	В1	В2	…	Вn
N1	a11	a12	…	a1n	b1
N2	a21	a22	….	a2n	b2
…	…	…	…	…	…
Nn	am1	am2	…	amn	bm
Стоимость единицы продукта	С1	С2	….	cn

 

- количество единицы питательного вещества вида , содержащегося в одной единице продукта вида.

 

при ограничениях