- •К.А.Джафаров Методы и модели в экономике
- •Глава 1. Элементы математического программирования
- •Постановка основной задачи математического программирования
- •§1 Различные формы задач лп
- •1. Общая задача лп
- •2. Задача с ограничениями неравенствами
- •3. Стандартная форма задачи лп (каноническая )
- •Целевая функция.- Перейдя к противоположному знаку можно перейти к противоположной задаче. (от max к min, и наоборот):
- •§2 Некоторые теоремы о решении задач лп
- •Если целевая функция (X) достигает минимума (максимума) в нескольких опорных решениях , то любое оптимальное решение является выпуклой линейной комбинацией альтернативных опорных решений, т.Е.
- •§3. Графическое решение задач лп
- •§4. Алгебраический метод решения задач лп (Симплекс метод)
- •Включаемая переменная – небазисная в данный момент, которая будет включена в базис в следующей итерации.
- •§6. Методы получения искусственного начального базисного решения
- •§5. Двойственная задача лп.
- •§6. Транспортная модель
- •§7. Решение транспортной задачи
- •Глава 2. Элементы теории игр § 1. Введение
- •§ 2. Матричные игры
- •Задачи к § 2
- •§ 3. Простая а-игра Пусть задана прямоугольная матрица
- •Обозначим
- •Стало быть
- •Задачи к § 3
- •§ 4. Расширенная a – игра
- •Задачи к § 4
- •§ 5. Доминирующие и полезные стратегии
- •Задачи к § 6
- •§ 7. Некоторые критерии принятия решений в условиях неопределенности
- •Критерий Лапласа
- •Критерий Сэвиджа
- •Задачи к § 7
- •§ 8. Байесовский подход в теории игр
- •Задачи к § 8
- •§ 9. Статистические игры
- •Задачи к § 9
- •§ 10. Игры с ненулевой суммой
- •А. Некооперативные игры
- •Б. Кооперативные игры
- •Задачи к § 10
- •Глава 3. Элементы теории массового обслуживания
- •§ 1. Введение
- •§ 2. Входной поток клиентов Рассмотрим последовательности случайных величин
- •§ 3. Дифференциальные уравнения, отвечающие процессу гибели и размножения
- •§ 4. Основные типы систем массового обслуживания
- •1. Система mm1 (с очередью)
- •2. Система mmm (с очередью)
- •3. Система mm
- •§ 5. Практическое применение Теории массового обслуживания
- •§ 6. Подготовка исходных данных и проверка гипотез
- •Глава 4. Задачи экономического анализа, решаемые на основе регрессионных экономических моделей.
- •Пусть у – расход на питание в семье, а - фактические признаки, - душевой доход, - размер семьи.
§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 |
|
7M-4 |
4M-1 |
-M |
0 |
0 |
0 |
9M |
Задача решается симплекс-методом (3 итерации)
Получаем
Замечание. Если М-задача не имеет решения, то исходная задача тоже не имеет решения.
§5. Двойственная задача лп.
Это вспомогательная задача ЛП, получаемая непосредственно из исходной задачи с помощью определенных правил. Исходная задача будет называться прямой. Понятие двойственности очень важно и используется при разработки эффективных методов анализа на чувствительность.
Использование симплекс – метода требует приведение задачи к стандартной форме. Двойственная задача будет получена из стандартной формы исходной задачи.
Пусть прямая задача задана в стандартной форме:
при ограничениях
Здесь в состав переменных включаются также остаточные и избыточные переменные.
Двойственная задача получается с помощью следующих правил:
Каждому ограничению прямой задачи соответствует переменная двойственной задачи. Число переменных равно числу ограничений.
Каждой переменной прямой задачи соответствует ограничение двойственной задачи.
Коэффициенты при некоторой переменной в ограничениях прямой задачи становятся коэффициентами левой части соответствующего ограничения двойственной задачи, а коэффициент при той же переменной в выражении для целевой функции прямой задачи становится постоянной правой части этого же ограничения двойственной задачи.
Остальные условия двойственной задачи:
Прямая задача в стандартной форме |
Двойственная задача | ||
Целевая функция |
Ограничения |
Переменные | |
Максимизация |
min |
не ограничены в знаке | |
Минимизация |
max |
не ограничены в знаке |
Примеры.
а) Прямая задача:
при ограничениях:
Приведем к стандартной форме:
x4 – остаточная переменная
n = 4 переменные, m = 2 ограничения
y1, y2 – переменные в двойственной задаче, (x) – целевая функция.
(по правилам 2)
при ограничениях:
y1, y2 – не ограничены в знаке
y10,y2 - не ограничена в знаке
б) Если в исходной задаче - min, как изменятся условия двойственной задачи.
Тогда получим:
2. а) Прямая задача
при ограничениях:
Стандартная форма:
При ограничениях:
Двойственная задача:
б) Если в исходной прямой задаче функция min, то в двойственной max.
Теорема.
Для любой пары допустимых решений прямой и двойственной задач
2. В точке, соответствующей оптимальным решениям обеих задач, значения у целевых функций в задачах max и min совпадают.
Эта теорема основная теорема двойственности.
Неважно в данном случае, какая из задач прямая. Важно то, что надо учитывать направление оптимизации.
Оптимальное решение одной из задач можно получить из данных симплекс-таблицы для оптимального решения другой задачи. Продемонстрируем это на примере.
Прямая задача
при ограничениях
Стандартная форма:
Отсюда,
Двойственная задача:
Стандартная форма двойственной задачи:
Целевая функция
Решаем эти задачи симплекс-методом независимо друг от друга. Сначала прямую. Оптимальную таблицу получаем через три итерации.
Начальная симплекс-таблица:
Базисные переменные |
x1 |
x2 |
x3 |
x4 |
R |
Решение |
|
x4 |
1 |
2 |
1 |
1 |
0 |
10 |
|
R |
2 |
-1 |
0 |
3 |
1 |
8 |
|
|
-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 |
|
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 |
|
-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 |
|
0 |
0 |
0 |
-26/5 |
-12/5 |
0 |
26/5-M |
12/5-M |
-M |
54 |
Для двойственной задачи решение выглядит так:
Решение
Запишем утверждение, чтобы связать решения этих задач:
Для данной прямой задачи
х4 и R начальные базисные переменные,
левые части.
Ограничения двойственной задачи, соответствующее переменным:
Пусть двойственная задача выступает в роли прямой, а прямая служит двойственной для нее.
Из -уравнения: