1. ДЗ
1.1. Свойства 1) ИЗ f→max, ДЗ(min) ДЗ f→min,ИС(max) 2) a_n x_n ИЗ - b_n 3) ИС в стандартном виде 4) ИЗ: А ДЗ: А ^ Т 5) Число неравенств в системе ( СО) огранич. пер-ных в ДР. 6) x_j ≥ 0, y_i ≥
1.2. Алгоритм: 1. е макс ≤ F мин ≥ 2. ^ Т 3. ДЗ
1.2.1. Устранения: *(-1)
1.3. Двойственные оценки
1.3.1. Деференцированные ресурсы ух *> 0
1.3.2. Недеференцированые ресурсы ух = 0
1.3.3. Скрытые доходы (теневые доходы)
1.4. Теоремы двойственности
1.4.1. Теорема 1:Fmax(x^*)=Gmin(g^*)
1.4.2. Теорема 2:x*∈D↔y* ϵ D_2,где ХП для x* и y* =0fmax =∞, то D_2=∅D =∅→g_mp=∞
1.4.3. Теорема 3: ∂Fmax/∂Bi=yi*, i=1,2,…,m.
1.4.4. ХП (1 огран. Исходной задачи -b1 * y1 { 2x1+3x2 ≤5 { 3x1-3x2≤7 (2x1+3x2-5)y1(послед. m огранич. ИЗ – Bm)Ym(1 огран. ДЗ – С1)X1(m огранич. ДЗ – Сm)Xm
2. Виды
2.1. В общем виде: Уф f→(max/min) ≤ СО{ ≥ = УН Xi ≥0
2.2. Каноническая: УФ f→max = СО{ = = УН > 0
2.3. Стандартная: УФ f→max ≤ СО{ ≤ ≤ все неравенства переводятся в такую форму Если УФ f→min, ≥ СО{ ≥ ≥ УН Xi ≥0
3. Структура 1.Целевая функция(функция цели) 2.Система ограничений 3.Условие неотрицательности
4. МЕТОДЫ
4.1. Геометрический метод
4.1.1. Варианты ОДР: 1.ВМ 2.ВМО 3.(.) 4.Ø
4.1.2. Алгоритм: 1.ОДР - D 2.С 3.L C 4.ОП,max (min)
4.1.2.1. Варианты ОП: 1.(.), [] 2.если fmin(.)[], если fmax→f 3.(.) решения нет
4.1.3. Недостатки: 1.Неточность построения 2.Ограниченное количество переменных (Xn≤3)
4.1.3.1. Устранение: 1.применение математических пакетов 2.применение другого метода
4.2. СИМПЛЕКС
4.2.1. ТС
4.2.1.1. ТС в чистом виде
4.2.1.1.1. Условия 1) Би>=0 2) Задача каноническая 3) Есть базисная переменная в каждом условии 4) УФ неотрицательное
4.2.1.1.2. Алгоритм 1) Проверяем условие 2) Составляем СТ 3) Критерии остановки 4) Улучшение опорного плана с помощью Гаусовых переменных
4.2.1.2. М-Метод
4.2.1.2.1. Расширенная задача: 1) ЦФ 2) СО 3) УН
4.2.1.2.2. Алгоритм 1) Проверка условий. - Би >=0 - Задача каноническая - БП 2) СТ 3) Проверка условий остановки 4) Улучшение опорного плана
4.2.2. МОМ
5. ТЗ
5.1. Виды ТЗ
5.1.1. Открытые
5.1.1.1. Признак разрешимости
5.1.2. Закрытые
5.2. Нахождение опорного плана
5.2.1. Метод Северо-Западного угла
5.2.1.1. -КЗК=m+n-1 Задача закрытого типа Начало с верхнего левого угла min (ai;bj) Заполняем до тех пор пока запасы и потребности не исчерпаются
5.2.2. Метод минимального элемента
5.2.2.1. Зактырый тип КЗК Клетка с min ценой min (ai;bj) -//- F
5.3. Метод потенциалов
5.3.1. Критерии остановки ∆ij≤0→ОП ∆ij=Vj-Ui-Cij
5.3.2. ui+vi=cij(i=1,m;j=1,n) Потенциал
5.3.3. КЗК m+n-1