Метод множителя Лагранжа.
В мат. анализе существуют задачи на условный экстремум, если среди ограничений нет неравенств при условиях неотрицательности, то тогда задача приводится к виду:
z=f(x1,x2…xn) max(min); 
(x1x2…xn)=bi(i=1 
). Эта задача не линейного программирования, и эти задачи называются классическими задачами оптимизации. Их можно решать пот крайне мере, методами дифференциального исчисления. В простейшем случае условным экстремумом ф-ции f(x1x2) называется max(min), достигнутый при условий, что х1 и х2 удовлетворяют допол. условию.
Канонический вид задачи линейного программирования.
Не смотря на разнообразие условий (><=) их все можно свести к одной канонической форме, которая имеет вид:
а11х1 + а12х1+…а1n хn=в1
а21 х1 + а22х2+…а2n хn =в2
… … … … … … … … … … …(1)
аm1 х1 + аm2х1+…аnm хn =вm
F=C0 +C1x1+C2x2+…Cnxn→min
В матричном виде это выглядит так:
(А*х)=(В)
F=(C)*(x)→min
Всякое неотрицательное решение системы(1) называется допустимым. Допустимое решение системы точка которая минимизирует F называется оптимальным планом. Оптимальное решение:
-опт. решение
Допустимое решение: 
Как правило оптимальное решение бывает единственным.
Основные задачи приводящие к линейному программированию.
Задача о диете. Для сохранения работоспособности человек в сутки должен потреблять некоторое кол-во питательных веществ: В1-белки, В2-витамины, В3-жиры, В4-углеводы, В5-вода. Имеется два вида пищи: П1 и П2. Запасы веществ: Вi в пище Пj составляет aij. Стоимость единицы продукции будет П1-С1, П2-С2. Требуется так организовать питание, что бы его стоимость была меньше, а человек получил бы не меньше суточной нормы питания. Сост. мат. модель. Обозначим через х1 и х2-кол-во продуктов П1 и П2, тогда кол-во белков в П1-а11х1 в П2-а12х21.
а11х1+а12х2≥в1
а21х1+а22х2≥в2
а31х1+а32х2≥в3
а41х1+а42х2≥в4
а51х1+а52х2≥в5
F=C4x1+C2x2→min. К этому же виду приводится задача на смеси: бензин различных сортов получают путем смешивания нефти продуктов, имеющих разные химические характер-ки, но их количество должно выдерживаться точно.
Задача об использовании сырья.
Для изгот. двух видов продукции, требуется сырье 5-ти видов. Доход получаемый от реализации продукта П1 и П2, будет соответственно S1 и S2.
а11х1 +а12 х2=в1
а21 х1 +а22 х2 =в2
а31 х1 +а32 х2 =в3
а41 х1+ а42 х2 =в4
а51 х1+а51 х2 =в5
F=C1x1+C2x2→max
Геометрический способ решения задач линейного программирования.
Если число переменных равно 2 или 3, то задачу ЛП можно решить геометр. способом, но все ограничения должны иметь вид неравенств. Геометрически задача ЛП задается в виде призмы в основании которого лежит ОДЗ. Но для упрощения призму не рисуют, оставляют только ОДЗ, но тогда для того что бы узнать в какую сторону F убывает или возрастает, находят градиент N.
Находим ОДЗ.
Находим N.
Перпендикулярно N проводим прямую F.
Прямую F перемещаем параллельно себе в направлении градиента, первая вершина, в которую входят прямая F-min, последняя вершина которую покидает F-max.
Метод потенциалов.
После нахождения опорного плана перевозок каждому поставщику Ai (в каждой строке) ставится в соответствии некоторое число Ui, а каждому потребителю(каждому столбцу) Bi ставится в соответствии некоторое число Vj. Числа Ui и Vj наз-ся потенциалами и выбираются так, чтобы в любой загруженной клетке их сумма равнялась тарифу этой клетке. Ui+Vj=Cij. Т.к. всех потенциалов m+n, а число занятых клеток m+n-1, то одному из неизвестных можно придать произвольное значение. И найти все оставшиеся потенциалы. Затем для проверки оптимальности просматриваются свободные клетки ij и для каждой их них вычисляется оценка:
S_ij=C_ij-(U_i+V_j). План оптимален, если для каждой свобод. клетки Sij≥0. Если есть отрицательные оценки, то переходят к новому плану по правилам распределительного метода. В новом плане определяется потенциалы строк и столбцов. Вычисляются оценки для всех свободных клеток. Когда среди оценок не окажется отрицательных полученный план будет оптимальным.
Алгебра-симлекс метод. Правила работы по симплекс методу.
1.Выбирается необходимое кол-во свободных клеток и вычисляется базисный z. Прирав. свобод. переменные к 0, если решение положит., то оно яв-ся опорным и переходим к пункту 2, если решение получилось отрицат., то нужно перераспределить свободные переменные, по не будет найдено положит. решение, если его не будет, то многоугольник лежит не в первой четверти. 2.если опорное решение найдено, то система записывается в исходном виде:
3.по исходному виду сост. симплекс таблица. 4.Выбирается разреш. элемент: а)в строке F находим положит. элемент, если такого нет, то решение уже найдено, а если положит. элементов несколько, выбирается любое. б)выбранный элемент определяет разрешающий элемент. в)сост. симплекс отношения для положит. элемент. столбца(если положит. нет) и выбирается min отношение, которое опред. разрешающую строку, если отношение одинаково для нескольких элементов, то выбирается любой. 5.Методом Жордановых исключений переходим к новой симплекс таблице: а)разрешающий элемент меняем на обратный, б)оставшиеся в столбце делим на «разрешающий» и меняем знак. г)все ост. элементы меняются по правилу прямоугольника.
Двойственная задача.
Двойственные задачи имеют важное значения: