- •Донецкий университет экономики и права
- •Экономико-математические методы и модели: оптимизационные методы и модели
- •Содержание
- •Введение
- •Тема 1 концептуальные аспекты математического моделирования экономики
- •1.1. Понятие модели. Классификация моделей
- •Тема 2 оптимизационные экономико-математические модели
- •2.1. Понятие оптимизационной модели
- •2.2. Примеры постановки оптимизационных задач
- •Вопросы для самоконтроля по темам 1, 2
- •Вопросы для самостоятельного изучения по темам 1, 2
- •Тема 3 задачи линейного программирования и методы их решения
- •3.1. Графический метод решения задач линейного программирования
- •3.2. Симплекс-метод решения задач линейного программирования
- •3.3. Метод искусственного базиса
- •3.4. Специальные случаи решения задач линейного программирования
- •Вопросы для самоконтроля по теме 3
- •Тема 4 теория двойственности и анализ линейных моделей оптимизационных задач
- •4.1. Понятие и экономический смысл двойственной задачи
- •4.2. Двойственный симплекс-метод
- •Вопросы для самоконтроля по теме 4
- •Вопросы для самостоятельного изучения по теме 4
- •Тема 5 целочисленное программирование
- •5.1. Понятие задачи целочисленного программирования
- •5.2. Метод отсекающих плоскостей (Гомори)
- •Вопросы для самоконтроля по теме 5
- •Вопросы для самостоятельного изучения по теме 5
- •Тема 6 нелинейное программирование
- •Вопросы для самостоятельного изучения по теме 6
- •Задания для индивидуальной работы студента
- •Задание 1
- •Задание 2
- •Задание 3
- •Задание 4
- •Питання до екзамену
- •Литература
- •Відповідальний за випуск: завідувач кафедри вищої математики та інформаційних технологій к.Ф-м.Н., доцент л.М. Харламова
- •83048, М. Донецьк, вул. Університетська, 77
5.2. Метод отсекающих плоскостей (Гомори)
Алгоритм метода отсекающих плоскостей можно представить такой последовательностью шагов:
Шаг 1. Решается линейно ослабленная задача. Если все переменные – целые, задача решена, если нет – переходим к шагу 2.
Шаг 2. В заключительной симплекс-таблице выбирается любое ограничение, у которого правая часть дробная (в столбце bi дробное число). По данному ограничению строится отсечение: соответствующее уравнение записывается таким образом, чтобы все коэффициенты при переменных и правая часть ограничения выглядели в виде суммы целых и дробных частей (причем дробная часть должна быть от нуля до единицы); целые части переносятся в левую часть уравнения, а дробные – в правую. Полученная правая часть и будет уравнением отсечения.
Шаг 3. Дополняем последнюю таблицу полученным отсечением и решаем задачу двойственным симплекс-методом. Если вновь получается дробное решение – снова переходим к шагу 2.
Рассмотрим применение этого метода на примере 5.2.
x1,2 – целые.
Базис |
cj |
x1 |
x2 |
S1 |
С.о. |
|
42 |
22 |
0 |
||||
S1 |
0 |
39 |
21 |
12 |
1 |
13/7 |
0 |
-42 |
-22 |
0 |
|
Базис |
cj |
x1 |
x2 |
S1 |
|
42 |
22 |
0 |
|||
x1 |
42 |
13/7 |
1 |
4/7 |
1/21 |
78 |
0 |
2 |
2 |
Полученное решение x1 = 13/7 = 1 6/7 дробное. Выпишем соответствующее уравнение:
Целые части перенесем влево, а дробные – вправо:
.
На основании правой части построим отсечение в виде:
, или:
.
Построенное отсечение обладает двумя свойствами:
1) любая допустимая точка целочисленной задачи удовлетворяет отсечению;
2) текущее оптимальное решение линейно-ослабленной задачи не удовлетворяет отсечению.
Введем данное уравнение в последнюю симплекс-таблицу и решим двойственным симплекс-методом:
Базис |
cj |
x1 |
x2 |
S1 |
S2 |
|
42 |
22 |
0 |
0 |
|||
x1 |
42 |
13/7 |
1 |
4/7 |
1/21 |
0 |
S2 |
0 |
–6/7 |
0 |
–4/7 |
–1/21 |
1 |
78 |
0 |
2 |
2 |
0 |
||
С.о. |
– |
–7/2 |
–42 |
– |
Базис |
cj |
x1 |
x2 |
S1 |
S2 |
|
42 |
22 |
0 |
0 |
|||
x1 |
42 |
1 |
1 |
0 |
0 |
1 |
x2 |
22 |
1,5 |
0 |
1 |
1/12 |
–7/4 |
75 |
0 |
0 |
11/6 |
7/2 |
Решение x2 = 1,5 – дробное; по второму ограничению снова строим отсечение:
Базис |
cj |
x1 |
x2 |
S1 |
S2 |
S3 |
|
42 |
22 |
0 |
0 |
0 |
|||
x1 |
42 |
1 |
1 |
0 |
0 |
1 |
0 |
x2 |
22 |
1,5 |
0 |
1 |
1/12 |
–7/4 |
0 |
S3 |
0 |
–0,5 |
0 |
0 |
–1/12 |
–1/4 |
1 |
75 |
0 |
0 |
11/6 |
7/2 |
0 |
||
С.о. |
– |
– |
–22 |
–14 |
– |
Базис |
cj |
x1 |
x2 |
S1 |
S2 |
S3 |
|
42 |
22 |
0 |
0 |
0 |
|||
x1 |
42 |
–1 |
1 |
0 |
–1/3 |
0 |
8 |
x2 |
22 |
5 |
0 |
1 |
2/3 |
0 |
–7 |
S2 |
0 |
2 |
0 |
0 |
1/3 |
1 |
–4 |
68 |
0 |
0 |
2/3 |
0 |
14 |
||
С.о. |
– |
– |
–2 |
– |
– |
Полученное решение недопустимое, поскольку x1 должен быть неотрицательным, поэтому он должен покинуть базис:
Базис |
cj |
x1 |
x2 |
S1 |
S2 |
S3 |
|
42 |
22 |
0 |
0 |
0 |
|||
S1 |
0 |
3 |
–3 |
0 |
1 |
0 |
–24 |
x2 |
22 |
3 |
2 |
1 |
0 |
0 |
9 |
S2 |
0 |
1 |
1 |
0 |
0 |
1 |
4 |
66 |
2 |
0 |
0 |
0 |
30 |
Таким образом, получили целочисленное решение: (x1 = 0, x2 = 3, z = 66).