Методы и модели в экономике (стр. 2 )

По условию оптимальности решение оптимальное.

Теорема (об улучшении оптимального решения)

1.  Если при проверки очередной итерации симплекс-методом окажется, что среди коэффициентов при небазисных переменных в j - уравнении найдется хотя бы один отрицательный (в задаче max) и во всех таких столбцах будет хотя бы один положительный элемент, то полученное решение можно улучшить.

2.  Если среди переменных в j - уравнении окажется хотя бы один отрицательный коэффициент (в задаче max) и в таком столбце все элементы отрицательны, то задача имеет неограниченную область ДР.

3.  Ели все коэффициенты в j - уравнении неотрицательны, то полученное решение оптимальное.

§6. Методы получения искусственного начального базисного решения

Если в ограничениях задач ЛП есть знаки , то для получения начального допустимого решения используются следующие методы:

М – метод (метод больших штрафов), Двухэтапный метод.

Мы рассмотрим М-метод.

Рассмотрим пример.

при ограничениях:

Запишем в стандартной форме

при ограничениях:

В ограничении, где нет остаточных переменных вводятся новые искусственные переменные.

Ri играют роль остаточных

За использование этих переменных вводится "штраф", приписывающий к R1 и R2 достаточно большой коэффициент М.

Тогда

Замечание. В задаче max в целевой функции искусственные переменные пишутся (вводятся) со знаком "минус".

Задача сводится к

при ограничениях:

Получаем начальное базисное решение 6 – 3 = 3, три переменные приравниваем к нулю.

искусственное базисное решение

Для составления таблицы в целевой функции вместо R1 и R2 пишутся выражения, полученные из ограничений

Подставим:

Получаем таблицу.

Базисные переменные	x1	x2	s1	R1	R2	s2	Решение
R1	3	1	0	1	0	0	3
R2	4	3	-1	0	1	0	6
s2	1	2	0	0	0	1	4
j	7M-4	4M-1	-M	0	0	0	9M

Задача решается симплекс-методом (3 итерации)

Получаем

Замечание. Если М-задача не имеет решения, то исходная задача тоже не имеет решения.

§5. Двойственная задача ЛП.

Это вспомогательная задача ЛП, получаемая непосредственно из исходной задачи с помощью определенных правил. Исходная задача будет называться прямой. Понятие двойственности очень важно и используется при разработки эффективных методов анализа на чувствительность.

Использование симплекс – метода требует приведение задачи к стандартной форме. Двойственная задача будет получена из стандартной формы исходной задачи.

Пусть прямая задача задана в стандартной форме:

при ограничениях

Здесь в состав переменных включаются также остаточные и избыточные переменные.

Двойственная задача получается с помощью следующих правил:

1.  Каждому ограничению прямой задачи соответствует переменная двойственной задачи. Число переменных равно числу ограничений.

2.  Каждой переменной прямой задачи соответствует ограничение двойственной задачи.

3.  Коэффициенты при некоторой переменной в ограничениях прямой задачи становятся коэффициентами левой части соответствующего ограничения двойственной задачи, а коэффициент при той же переменной в выражении для целевой функции прямой задачи становится постоянной правой части этого же ограничения двойственной задачи.

Остальные условия двойственной задачи:

Прямая задача в стандартной форме	Двойственная задача
Целевая функция	Ограничения	Переменные
Максимизация	min		не ограничены в знаке
Минимизация	max		не ограничены в знаке

Примеры.

1.  а) Прямая задача:

при ограничениях:

Приведем к стандартной форме:

x4 – остаточная переменная

n = 4 переменные, m = 2 ограничения

y1, y2 – переменные в двойственной задаче, j(x) – целевая функция.

(по правилам 2)

при ограничениях:

y1, y2 – не ограничены в знаке

y10, y2 - не ограничена в знаке

б) Если в исходной задаче j - min, как изменятся условия двойственной задачи.

Тогда получим:

2. а) Прямая задача

при ограничениях:

Стандартная форма:

При ограничениях:

Двойственная задача:

б) Если в исходной прямой задаче функция min, то в двойственной max.

Теорема.

1.  Для любой пары допустимых решений прямой и двойственной задач

2. В точке, соответствующей оптимальным решениям обеих задач, значения у целевых функций в задачах max и min совпадают.

Эта теорема основная теорема двойственности.

Неважно в данном случае, какая из задач прямая. Важно то, что надо учитывать направление оптимизации.

Оптимальное решение одной из задач можно получить из данных симплекс-таблицы для оптимального решения другой задачи. Продемонстрируем это на примере.

Прямая задача

при ограничениях

Стандартная форма:

Отсюда,

Двойственная задача:

Стандартная форма двойственной задачи:

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

Решаем эти задачи симплекс-методом независимо друг от друга. Сначала прямую. Оптимальную таблицу получаем через три итерации.

Начальная симплекс-таблица:

Базисные переменные	x1	x2	x3	x4	R	Решение
x4	1	2	1	1	0	10
R	2	-1	0	3	1	8
j	-5-2M	-12+M	-4-3M	0	0	-8M

Оптимальная таблица.

Базисные переменные	x1	x2	x3	x4	R	Реше-ние
x2	0	1	-1/5	2/5	-1/5	12/5
x1	1	0	7/5	1/5	2/5	26/5
j	0	0	3/5	29/5	-2/5+M	54*4/5

Решаем обратную (двойственную) задачу (решение через 4 итерации).

Базис. перем.	y1			y3	y4	y5	R1	R2	R3	Решение
R1	1	2	-2	-1	0	0	1	0	0	5
R2	2	-1	1	0	-1	0	0	1	0	12
R3	1	3	-3	0	0	-1	0	0	1	4
y	-10+4M	8+4M	8-4M	-M	-M	-M	0	0	0	21M

Базисные переменные	y1			y3	y4	y5	R1	R2	R3	Решение
y5	0	0	0	-7/5	1/5	1	7/5	-1/5	-1	3/5
	0	-1	1	2/5	-1/5	0	-2/5	1/5	0	2/5
y1	1	0	0	-1/5	-2/5	0	1/5	2/5	0	29/5
y	0	0	0	-26/5	-12/5	0	26/5-M	12/5-M	-M	54

Оптимальная таблица.