3. Означення стандартної форми злп і характеристика умов означення на можливість їх виконання.

ЗЛП называется заданной в стандартной форме канонического вида, если выполняются следующие условия: 1) система осн-ых ограничений представлена уравнениями и все они линейно независимы. Приведение системы осн.огран-ий-если оно необходимо, можно осуществить введением дополительных переменных;

Если фун. огр. основным знаком содержит (≤), то все хn+к берутся со знаком(+), и наоборот.

2) число уравнений меньше числа переменных(В случае, когда число уравнений больше числа неизвестных, система несовместна и ЗЛП решений не имеет3) решается задача минимизации целевой функции( Когда исходная задача заключается в поиске максимума целевой функции,а исходная задача сформулирована на поиск мин-ма, то,для изменения экстремума значение целевой ф-ии умножают на (-1) z^'=-z, получим задачу минимизации.;; 4)свободные члены-правые части системы осн. ограничений неотрицательны(если некоторое bi<0, то, умножая уровнение на -1, можно добиться выполнения данного условия; 5)на все переменные накладывается условие неотрицательности(если на некоторую переменную хк не наложено условие отрицательности, то произведем замену: хк= хк'-хк'', где хк'≥0,хк''≥0.

4. Форми запису злп (розгорнута, скорочена, матрична, векторна) і основні означення (плану, оптимального плану, опорного плану, невиродженого опорного плану).

Развернутая форма записи ЗЛП:

z = c1x1 + c2x2 + ... + cnxn (min)

a11x1 + a12x2 + ... + a1nxn = b1,

a21x1 + a22x2 + ... + a2nxn = b2,

am1x1 + am2x2 + ... + amnxn= bm;

х1≥0, х2≥0….,хn≥0

Сокращенная ( с помощью знаков суммирования) форма записи ЗЛП:

z= (min)

(i=1,m)

xj≥0 Матричная форма записи ЗЛП: Здесь С = (с1, с2, ..., сn) –матрица-строка размерности(1×n) Х= -матрица-столбец неизвестных разм.( n×1) А=||аij||-матрица системы осн.ограничений разм-ти(m×n) В= -матрица-столбец свободных членов разм.(m×1) Тогда ЗЛП можно записать: Z = СХ(min); АХ = В; Х≥0

Векторная форма:

Здесь С = (с1, с2, ..., сn) –n-мерный вектор; Аj и В-вектор-столбцы: А1= ;А2= ;Аn= ; В= Тогда ЗЛП можно представить в виде: Z = СХ(min), x1A1+x2A2+…+xnAn=B, Х≥0

План ЗЛП-набор значений переменных х1, х2….,хn, удовлетв-ий полной системе огр-ий. Оптимальный план-план, достовляющий минимум целевой фун-ии. Опорный план-план, у которого система линейно незав-ых векторов соответствует его положительным компонентам. Опорный план ЗЛП наз-ся невырожденным, если векторы, соответствующие его положительным компонентам, образуют базис.

5. Графоаналітичний метод розв'язання ЗЛП та його характеристика. Спосіб повного перебору кутових точок і спосіб направленого перебору, їх етапи. Поняття лінії рівня, градієнта цільової функції, опорної прямої до множини "к".

Из названия следует, что его применение содержит графическую и расчетную части. При этом граф-ая часть исп-ся для нахождения множества планов ЗЛП,т.е. множества К.К есть пересечение всех полуплоскостей. Граф-ий метод применяется в основном для решения ЗЛП с двумя переменными и некоторых ЗЛП с 3-мя переем-ми. Он иллюстрирует свойства множества планов и решений ЗЛП и не пригоден для решения практич—их задач.Способ полного перебора. Состоит из этапов:1.Построение К и его оценка:если К=ǿ, решения нет; если К-выпуклая многограннаяобласть, метод не применим; если К-выпуклый многоугольник, осуществляется переход к этапу 2. 2.Определение координат угловых точек К. 3.Вычисление значений целевой фун-ии в каждой угловой точке К определение точек экстремума:-если требуемый экстремум достигаетсяв одной угловой точке, то решение ЗЛП единственно и координаты данной угловой точки-оптимальный план.-если тебуемый экст. достигается в двух угловых точках, то ЗЛП имеет бесчисленное множество решений, которыми явл-ся координаты любой точки отрезка, соединяющего данные угловые точки. Способ направленного перебора. Этапы:1) Построение К и его оценка:если К=ǿ, решения нет; если К≠ǿ-переход к этапу 2.2)Построение gradz ,т.е. N(C1;C2). 3.Построение линии уровня, имеющей с К общие точки. 4.Перемещение линии уровня в направлении gradz , если задача на макс-ум целевой фун-ии, и в противоположном, если задача на мин-ум, до тех. пор, пока она не станет опорной для К. Возможны 3 случая:1) опорная прямая с К имеет общ. точку, тога решением ЗЛП явл-ся координаті єтой точки;2)...имеет общий отрезок или общий луч, тога реш.ЗЛП явл-ся корд-ты любой точки этого отрезка или луча,т.е.ЗЛП имеет множ-во решений; 3)прямая не может стать опорной для К, т.е.всегда пересекает К, тога ЗЛП решений не имеет-целевая ф-ия не ограничена на К.

Линия уровня u(x,y)- совокупность точек области определения этой функции, в которых она принимает одно и то же значение, т.е. u(x,y)=c. Градиент функции u(x,y) в т. М-это вектор, проекциями которого на оси координат явл-ся значения частных производных в этой точке.( grad_mu). Опорная прямая к множеству G –назыв-ся прямая, если с этим множеством имеет хотя бы одну общую точку и все точки G расположены по одну сторону от неё.