Задачи линейного программирования

Plus de détails

Отдых в Германии без туроператора

par Мария Костина

Экологические проблемы города

par Татьяна Пручкина

Лекция

par Евгения Сидоренкова

Алгоритм – точное описание порядка действий, которые должен выполнить исполнитель для решения задач.

par Wither Sintex

1. bi>=0 2. Задача канноническая 3. В каждом ограничении есть базисная переменная 4. В ЦФ нет базисной переменной

М-метод

Cхема решений

Начальный ОП

Приводим к ЗТ

Тип

1. В 2. bi 3. xj 4. f-строка

Расширенная задача

Каноническая

Subtopic1. ЦФ f--> max 2. CО = 3. УН xj>=0

Потенциал

cij=ui+vj

Закрытая

Zi=0 (М строка зануляется)

C.O. (+Zi)

БП: 1. Коэфециент +1 2. Есть только в одном ограничении

У.Н. xi>=0; zi>=0

1. Выпуклый многоугольник 2. Выпуклая многоугольная область 3. (*) 4. Пустое множество

В общем виде:

1. ЦФ f--> max 2. CО <=; =; >= 3. УН xj>=0

Теоремы

(d fmax)/dbi=y*

fmax∞↔Д2=Ø Д=Ø↔gmin∞ X*ЄД↔Y*ЄД, где ХП для X* и Y*=0

fmax(x*)=gmin(y*)

Минимального элемента

1.Закрытый тип 2.КЗК 3.Начало:клетка с минимальной ценой 4. min(ai,bj); 5.Заполняем до тех пор пока ЗП и потреб. не исчерпаются 6.F

Открытая

Свойства

xj>=0; yi>=0

Число нер-в в СО ИЗ = числу переменных ДЗ

ИЗ, Ф, ДЗ, А транспортированная

ИЗ в стандартном виде

a(n), xn, ИЗ - свободные члены СО и ДЗ

ИЗ f->max; ДЗ f->min ИЗ f->min; ДЗ f->max

Правила: 1. bi - без изменения 2. Коэффециенты с противоположными знаками

Симплекс-метод

ДЗ

A (транспортированная)

A

1. f->max 2. f->min

Subtopic

В чистом виде

1. Проверка условий

2. С.Т.

Ц.Ф. f(x,z)=f+M(-Zi)

Симплексная таблица

Критерии остановки

Варианты оптимальных планов

Метод потенциалов

Метод искусственного базиса

4 условия

1. Проверяем условия 2. Составляем симплексную таблицу 3. Проверяем критерии остановки 4. Улучшение опорного плана

Недостатки

Метод обратной матрицы

Структура

Условие неотрицательности (УН)

Система ограничений (СО)

Целевая функция (ЦФ)

Виды

Двойственные задачи

Устранения если не так

3. Проверка критериев

Критерий остановки

Δij<=0=>ОП

1. Неточность построения 2. Ограниченное количество переменных (x<=3)

Двойственная оценка

yi*>0 -> деффицитный yi*=0 -> недеффицитный yi*>0 -> деффицитный

Скрытые доходы, теневые доходы

СО

Признак разрешимости

Приведение к закрытому типу

®

Геометрический метод

ММТЗ

1. Умножить на (-1) 2. fmin=-fmax >=-xk= <=+xs= xl=xl'-xl'' 3. Использование других методов 4. Выражаем через небазисные переменные

ЦФ

Табличный способ

Варианты ОДР

Характеристические произведения

* (1 ограничение ИЗ b1)y1 ... (m-ограничение ИЗ bm)ym ... (m-ограничение ДЗ cm)xm

КЗК

m+n-1

1. В f строке нет отрицательных элементов 2. Если существует столбец j0, такой что Сj0<0 и все числа aj0<=0, то fmax=∞ 3. Если в какой-нибудь строке симплексной таблицы кроме свободного члена, других положительных элементов нет, то система не имеет неотрицательных значений, т.е. система ограницений задачи невозможна

Методы

1. ОДР 2. Построение вектора C 3. l перпендикулярна С 4. Оптимальный план f(max; min)

УН

Нахождение ОП

1. (*), [] - точки отрезка 2. fmin (*), [] - точки отрезка fmax=∞ 3. (*) 4. Нет решений

Виды ТЗ

4. Улучшение опорного плана

а) bi>=0 б) Задача каноническая в) БП-? г) в Ц.Ф. нет БП д) f(x)

Устранение недостатков: 1. Применение мат.пакетов 2. Применение других методов

Стандартная

1. ЦФ f--> min 2. CО >= 3. УН xj>=0

1. ЦФ f--> max 2. CО <= 3. УН xj>=0

Алгоритм

Северо-западного угла

1.Закрытый тип 2.КЗК=m+n-1 3.Начало: верхний левый угол 4. min(ai,bj); 5.Заполняем до тех пор пока ЗП и потреб. не исчерпаются 6.F

Транспортные задачи

Задачи линейного программирования