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

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

(10.10)

при условиях

(10.11)

(10.12)

                                              .                                 (10.13)

Функция  (10.10) называется целевой функцией (или линейной формой) задачи (10.10) – (10.13), а условия (10.11) – (10.13) – ограничениями данной задачи.

2. Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального для «≤» (минимального для «≥») значения функции (10.10) при выполнении условий (10.11) и (10.13), где k = m, s = n.

3. Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции (10.10) при выполнении условий (10.12) и (10.13), где k = 0, s = n.

Каноническая (основная) форма	Стандартная (симметричная) форма	Общая форма
1) ограничения
Уравнения .	Неравенства .	Уравнения и неравенств .
2) условия неотрицательности
Все переменные ,	Все переменные ,	Часть переменных , , .
3) цель задачи
max F(x) или minF(x)	max F(x) [min F(x)]	max F(x) или min F(x)

6.Выпуклые множества.

А1

А(х1,х2)

А2

Пусть на плоскости Х1 0 Х2 заданы А1 и А2 ( , ) и А1 ( , ) определяющий направление отрезка . Найдем координаты произвольной внутренней точки А (х1,х2). Векторы (х1- х2- ) (х1^2- х2^2- ) и одинаково направлены.

=t* , где 0< t 1

х1- =t (x1^2-x1^1)

x2-x2^1=t(x2^2-x2) отсюда x1=(1-t)x1^1+tx1^2

x2=(1-t)x2^1+tx2^2

1 -t= x1= x1^1+ x1^2 (1)

t= x2= x2^1+ x2^2

A= + A2 (2)

>=0 >=0 =1 (3)

Определение. Точка А для которой выполняется условия (2) и (3) называется выпуклой линейной комбинацией точек А1 и А2.

Точки А1 и А2 наз.ся условными или крайними точками отрезка

Пусть имеется n-точек А1,А2,А3,,,Аn . Точка А называется выпуклой линейной комбинацией точек А1,А2,А3,,,Аn, если выполняется условие

А=А1А1+А2А2+…+АnАn

Li>=0 (i=1.2…n)

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

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

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

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

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

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

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