Задачи линейного программирования
Транспортные задачи
Северо-западного угла
1.Закрытый тип
2.КЗК=m+n-1
3.Начало: верхний левый угол
4. min(ai,bj);
5.Заполняем до тех пор пока ЗП и потреб. не исчерпаются
6.F
Алгоритм
Стандартная
1. ЦФ f--> max
2. CО <=
3. УН xj>=0
1. ЦФ f--> min
2. CО >=
3. УН xj>=0
Алгоритм
Устранение недостатков:
1. Применение мат.пакетов
2. Применение других методов
а) bi>=0
б) Задача каноническая
в) БП-?
г) в Ц.Ф. нет БП
д) f(x)
4. Улучшение опорного плана
Виды ТЗ
1. (*), [] - точки отрезка
2. fmin (*), [] - точки отрезка fmax=∞
3. (*)
4. Нет решений
Нахождение ОП
УН
1. ОДР
2. Построение вектора C
3. l перпендикулярна С
4. Оптимальный план f(max; min)
Методы
1. В f строке нет отрицательных элементов
2. Если существует столбец j0, такой что Сj0<0 и все числа aj0<=0, то fmax=∞
3. Если в какой-нибудь строке симплексной таблицы кроме свободного члена, других положительных элементов нет, то система не имеет неотрицательных значений, т.е. система ограницений задачи невозможна
КЗК
m+n-1
Характеристические произведения
* (1 ограничение ИЗ b1)y1
...
(m-ограничение ИЗ bm)ym
...
(m-ограничение ДЗ cm)xm
Варианты ОДР
Табличный способ
ЦФ
1. Умножить на (-1)
2. fmin=-fmax
>=-xk=
<=+xs=
xl=xl'-xl''
3. Использование других методов
4. Выражаем через небазисные переменные
ММТЗ
Геометрический метод
Признак разрешимости
Приведение к закрытому типу
®
СО
Двойственная оценка
Скрытые доходы, теневые доходы
yi*>0 -> деффицитный
yi*=0 -> недеффицитный
yi*>0 -> деффицитный
1. Неточность построения
2. Ограниченное количество переменных (x<=3)
Критерий остановки
Δij<=0=>ОП
3. Проверка критериев
Устранения если не так
Двойственные задачи
Виды
Структура
Целевая функция (ЦФ)
Система ограничений (СО)
Условие неотрицательности (УН)
Метод обратной матрицы
Недостатки
1. Проверяем условия
2. Составляем симплексную таблицу
3. Проверяем критерии остановки
4. Улучшение опорного плана
4 условия
Метод искусственного базиса
Метод потенциалов
Варианты оптимальных планов
Критерии остановки
Симплексная таблица
Ц.Ф.
f(x,z)=f+M(-Zi)
2. С.Т.
1. Проверка условий
В чистом виде
Алгоритм
1. f->max
2. f->min
A
A (транспортированная)
ДЗ
Симплекс-метод
Правила:
1. bi - без изменения
2. Коэффециенты с противоположными знаками
Свойства
ИЗ f->max; ДЗ f->min
ИЗ f->min; ДЗ f->max
a(n), xn, ИЗ - свободные члены СО и ДЗ
ИЗ в стандартном виде
ИЗ, Ф, ДЗ, А транспортированная
Число нер-в в СО ИЗ = числу переменных ДЗ
xj>=0; yi>=0
Открытая
Минимального элемента
1.Закрытый тип
2.КЗК
3.Начало:клетка с минимальной ценой
4. min(ai,bj);
5.Заполняем до тех пор пока ЗП и потреб. не исчерпаются
6.F
Теоремы
fmax(x*)=gmin(y*)
fmax∞↔Д2=Ø
Д=Ø↔gmin∞
X*ЄД↔Y*ЄД, где ХП для X* и Y*=0
(d fmax)/dbi=y*
В общем виде:
1. ЦФ f--> max
2. CО <=; =; >=
3. УН xj>=0
1. Выпуклый многоугольник
2. Выпуклая многоугольная область
3. (*)
4. Пустое множество
У.Н.
xi>=0; zi>=0
БП:
1. Коэфециент +1
2. Есть только в одном ограничении
C.O.
(+Zi)
Zi=0 (М строка зануляется)
Закрытая