31. Графический метод решения задач лп:

-Построим прямые,соотв каждому ограничению(2х1+3х2=5)

-Найдем решение каждого ограничения в отдельности,для этого выберем любую точку на плоскости(1,3) и подставим ее в данное ограничение.если нерав несправедливо,то не явл решением огранич,то решениям явл все точки,противоположные прямой;если же справедливо,то реш явл полуплоскость,которой принадл данная точка.

-Находим общую область системы лин ограничений.Для этого отбрас области,не явл реш-ем.Получается прямоугольник.Множ-во точек явл реш.

-Строим целевой вектор,координаты которого совпадают с коэфф данной функции зэд.Начало ветора равно началу координат.

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

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

-Это и будет ответ(координаты точки)

32. Теоремы симплексного метода.

Теорема1.(Достаточное условие оптимальности опорного плана). Если решается задача и при этом все элементы оценочной строки симплексной таблицы неотриц., то соответствующий план этой задачи явл-ся оптимальным, а элемент а00 представляет собой наибольшее значение целевой ф-ции на мн-ве планов задачи.

Теорема2.(Случай неограниченности целевой ф-ции).Если оценочная строка задачи содержит отрицательный элемент, например, а0n, а в столбце, соответствующему неизвестному xn, нет ни одного положительного элемента, то на мн-ве планов задачи целевая ф-ция не ограничена сверху.

Теорема3.(Об улучшении опрного плана).Если решается задача и в оценочной строке симплексной таблицы есть хотя бы один отрицательный элемент а0k, а соответствующий столбец содержит хотя бы один положительный элемент, то можно улучшить план, выполнив преобразование однократного замещения.

33. Алгоритм симплекс-метода:

-Методом жордана гаусса система лин алг уравнений в матричном виде приводится к канонической

-Указывается первоначальное опорное решение

-Заполняется симплексная таблица

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

-Если все оценки свободных переменных оценочной строки исходной симплексной таблицы не отрицат,то первонач опорное решение будет оптимальным(по Теореме1).Оно будет единственным,если все оценки положительны.Наличие нулевых оценок свободных переменных свидетельствует о множестве оптимальных решений(Т:если существует единственное оптимальное решение и множество допустимых решений ограничено,то оптимальное реш совпадает с одним из опорных)

-Если в первой оценочной строке имеются отрицательные элементы,то нужно переходить к новым опорнм решениям.Переход возможен,если в каком либо столбце с отриц элементом имеется хотя бы один положительный коэфф.Переход осуществл с помощью преобразов однократного замещения.При этом разрешающ столбец выбирается по наименьш отрицат оценке свободной переменной.Заполняется вторая оценочная строка. Шаги симплексного метода продолж до тех пор,пока не возникнут ситуации пункта 4,5.Разреш столб и строк обознач стрелочкой