117. Выпуклое множество. Выпуклая область

Мн-во MАⁿ называется выпуклым, если для любых 2-х точек А и В этого мн-ва отрезок АВ также лежит в мн-ве М (напр. куб, шар, квадрат, круг, пирамида, эллипс).

Пересечение нескольких полупространств в Аⁿ называется выпуклой многогранной областью в Аⁿ.

В ыпуклая многогранная область

В свою очередь, полупространством в Aⁿ – называется множество точек x(x₁,x₂,…,x_n) таких, что

a₁x₁+a₂x₂+…+a_nx_n+b0

a₁²+a₂²+…+a_n²>0

a₁, a₂,…,a_n, b – фиксированные числа.

119. Дайте определение выпуклой оболочки нескольких точек.

Пусть М-выпуклая оболочка точек Х₁(5,2), Х₂(7,2), Х₃(5,4), Х₄(31/5, 2), Х₅(26/5, 19/5), Х₆(5, 16/5). Найдите ограничения в виде системы неравенств, которые задают множество М.

множество всех выпуклых линейных комбинаций точек А₁, А₂,…,А_p называется выпуклой оболочкой системы точек А₁, А₂,…,А_p и обозначается <А₁,А₂,…,А_p>.

Ур-е пр. Х₃Х_2: х-5=у-7; 2х+2у=24; х≥ 5

2 -2 у≥ 2

2х+2у≤ 24

123. Как по сиплекс-таблице определить число решений ЗЛП?

а)если в последней строке среди оценок нет отрицательных, то достигнуто оптимальное решение;

б)если в последней строке есть хотя бы одна отрицательная оценка, но в соотв. столбце нет ни одного положительного эл-та, то ЗЛП не имеет решений z_max→∞;

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

125. Сформулируйте основные теоремы двойственности. Как получить решение двойственной задачи из последней симплексной таблицы исходной задачи?

Теорема1: если исходная задача имеет оптимально решение , то и двойственная ей тпакже имеет оптимальтное решение при этом оптимальные значения целевых ф-й обеих здачач раны т. е. zmax=Tmin

Теорема2: достаточный признак оптимизации: если х₀ и у₀ –допустимые решения пары двойственных задач и при этом z(x₀)=T(y₀), то х₀ и у₀ –оптимальные решения той и другой задачи. T(y₀)≥Z(x₀).

Теорема3:оснятии решения двойственной задачи с последней симплексной таблицы исходной задачи: у₀=а_0Е+с_{Е ;} а-вектор индексной строки, координаты которого соотв базисным перемененным исходной таблицы, с-вектор с теми же коорд целевой ф-ии соответственно.

122. Какими условиями связаны симметричные взаимно двойственные злп?

Max	min
1. Коэффициенты целевой функции	1. Свободные члены ограничений
2. Ограничения исходной задачи   	 2. Переменные (знаки)  =
3. Переменные (знаки)   	 3. Знаки ограничений  =
4. Матрица ограничений А	4. Матрица А^т