Зенкевич Н.А. Практикум по исследованию операций

Подождите немного. Документ загружается.

6.2. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ СРЕДСТВАМИ LINGO 161

@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;

@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;

@FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:

U( J) >= U( K) + X ( K, J) -

( N - 2) * ( 1 - X( K, J)) +

( N - 3) * X( J, K)

);

@FOR( LINK: @BIN( X));

! Для первого и последнего пункта выполняется ...;

@FOR( CITY( K)| K #GT# 1:

U( K) <= N - 1 - ( N - 2) * X( 1, K);

U( K) >= 1 + ( N - 2) * X( K, 1)

);

END

Примечание: #NE# - логический оператор, который равен ИСТИНА если оба опе-

ранда не равны и ЛОЖЬ в противном случае. #GT# - логический оператор, который

равен ИСТИНА если левый операнд строго больше чем правый операнд и ЛОЖЬ в

противном случае. #AND# - логический оператор, который равен ИСТИНА если для

обоих операндов выполняется ИСТИНА и ЛОЖЬ в противном случае.

Приоритеты операторов Операторы

Высокий уровень #NOT#

#NE# #GT#

Низкий уровень #AND#

Решая эту модель в пакете LINGO мы получаем значение целевой функции 6610.000.

6.2.7 Решение модели о минимизации сети

Подробно задача о минимизации сети рассмотрена в главе 3.2.

162 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ

В данном разделе рассмотрим следующую задачу: необходимо доставить сообщение

из Атланта (база) в города Чикаго, Цинциннати, Хьюстон, Лос-Анжелес, Монреаль так

чтобы пройти минимальный путь. Задана матрица расстояний между городами.







0 702 454 842 2396 1196

702 0 324 1093 2136 764

454 324 0 1137 2180 798

842 1093 1137 0 1616 1857

2396 2136 2180 1616 0 2900

1196 764 798 1857 2900 0;







В пакете LINGO модель запишется следующим образом:

MODEL:

SETS:

CITY / 1.. 6/: U; ! U( I) = номер города I;

! U( 1) = 0;

LINK( CITY, CITY):

DIST, ! Матрица расстояний;

X; ! X( I, J) = 1 если мы используем путь между городами I, J;

ENDSETS

DATA: ! Матрица расстояний может не быть симметричной;

! Город с номером 1 рассматривается как исходная точка;

!В: Атл Чи Цин Хъю ЛА Мон ;

DIST = 0 702 454 842 2396 1196 !из Атл;

702 0 324 1093 2136 764 !из Чи;

454 324 0 1137 2180 798 !из Цин;

842 1093 1137 0 1616 1857 !из Хъю;

2396 2136 2180 1616 0 2900 !из ЛА;

1196 764 798 1857 2900 0; !из Мон;

ENDDATA

! Размер модели: модель может работать медленнее при количестве пунктов N >= 8;

N = @SIZE( CITY);

! Минимизация общего расстояния между городами;

MIN = @SUM( LINK: DIST * X);

6.3. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ MAPLE163

! Для K-го города, кроме базы, ... ;

@FOR( CITY( K)| K #GT# 1:

@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;

@FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:

U( J) >= U( K) + X ( K, J) -

( N - 2) * ( 1 - X( K, J)) +

( N - 3) * X( J, K); );

);

@SUM( CITY( J)| J #GT# 1: X( 1, J)) >= 1;

@FOR( LINK: @BIN( X); );

@FOR( CITY( K)| K #GT# 1:

@BND( 1, U( K), 999999);

U( K) <= N - 1 - ( N - 2) * X( 1, K); );

END

Примечание: @BIN( переменная) эта функция накладывает ограничения на пере-

менную, которая может быть только бинарной, т.е. имеет значение 0 или 1.

@BND( нижняя граница, переменная, верхняя граница)- накладывает ограничения

на переменную. Переменная может быть ≥ нижний границы интервала и ≤ верхней

границы.

Решение этой модели является минимальное расстояния равно 4000.000.

6.3 Решение оптимизационных задач с использовани-

ем Maple

Пакет символьных вычислений Maple позволяет решать оптимизационные задачи. На-

пример, находить решение в задачах линейного программирования.

Рассмотрим задачу:

164 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ

min F = min(4x

+ 15x

+ 12x

+ 2x

);

+ 3x

+ x

≥ 1,

+ 3x

+ x

− x

≥ 1;

, x

≥ 0.

Используем пакет Simplex, в ходящий с Maple, этот пакет позволяет проделывать

рутинные операции при решение линейных оптимизационных задач с использованием

симплекс-метода.

Запишем нашу задачу в пакете Maple.

Рис.6.3.1. Рабочее окно Maple с задачей линейного программ ирования.

Строка with(simplex): говорит о том, что при работе используется пакет Simplex.

Функция simplex[minimize] - ищет минимум в задаче линейного программирования.

Варианты записи функции minimize:

• minimize(f, C)

• minimize(f , C, vartype)

Параметры:

• f - линейная функция, целевая функция,

6.3. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ MAPLE165

• C - множество (список) линейных ограничений,

• vartype - (опционально) NONNEGATIVE or UNRESTRICTED (неотрицательные

решения или без ограничений)

Функция subs(x=a,expr) подставляет значения x = a в выражение expr.

Решая задачу линейного программирования получаем ответ F = 6, x

= 0, x

2/7, x

= 1/3, x

= 0.

Рассмотрим новую задачу:

max

= max(3x

+ 2x

);

+ 2x

≥ 12,

+ 2x

≤ 10;

+ 2x

= 6;

, x

≥ 0.

Приведем систему к такому виду, чтобы все неравенства имели знак ≤. Для пере-

вода неравенств в пакете Simplex для этих целей служит функция convert(C, std), где

C - множество линейных уравнений или неравенств. Для перевода равенств в неравен-

ства со знаком ≤ используется функция standardize(C). На рис. 2 представлен результат

действия этих функций.

Рис.6.3.2. Решение задачи линейного программирования

В задаче ищется максимум функции F , для нахождения которого воспользуемся

функцией maximize пакета Simplex, параметры которой аналогичны параметрам функ-

ции minimize.

Решение этой задачи представлено на рис.6.3.3.

166 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ

Рис.6.3.3. Решение задачи линейного программирования

Ответом в данной задаче линейного программирования является

F = 9, x

= 3, x

= 0.

Ответы

1.2.1 F=2300, X = {60, 25}. 1.2.2 F=1800, X = {100, 200}, 1.3.3. F=2600, X={80,

80}. 1.2.4 F=40000, X={20, 10}. 1.2.75 F=142, X={10, 12}. 1.2.6 F=14, X= {6, 4}. 1.2.7

F=818,181 X={60, 60, 30, 30, }. 1.2.8 F=10, X = {2, 0}. 1.2.9 Неразрешима. 1.3.10. F=16,

X={3, 5}. 1.2.11 Неразрешима. 1.2.12 F=15, X={4, 1}. 1.2.13 F=9, X = {5

, 1

}. 1.2.14

F=1, X = {0, 1}, 1.3.15. F=−2

, X={

, 4}.

1.3.1 z=22

, X = {

}. 1.3.2 z=-37, X = {

} 1.3.3. z=3, X={0,

, 16}.

1.3.4. z=450, X={90}. 1.3.5 z=6, X={

, 5

}. 1.3.6 z=12,8, X={0,5, 0,4, 4,5}. 1.3.7 z=-9,

X={0,

}. 1.3.8 z=7

, X={

, 0}. 1.3.9 z=7, X={4

, 2

}. 1.3.10 z=15, X={

, 0}.

1.4.1 z=

102

, X = {

}. 1.4.2 z=-14, X = {3,

, 4} 1.4.3. z=16, X={2, 2, 2}. 1.4.4.

z=5, X={2, 1}. 1.4.5 z=−2

, X={

, 0}. 1.4.6 z=−6

, X={3

}. 1.4.7 z=

, X={1

}. 1.4.8 z=6, X={4, 3}. 1.4.9 z=12, X={1, 3}. 1.4.10 z=6

, X={1

, 2

}. 1.4.11 z=9,

X={5

, 1

}. 1.4.12 Неразрешима. 1.4.13 z=24, X={12, 0}. 1.4.14 z=

, X={1

, 4

}. 1.4.15

, X={

}. 1.4.16 z=6, X={0,

, 0}.

1.6.7 z=10, X = {2, 4}. 1.6.8 z=-20, X = {4, 24, 7} 1.6.9. z=-2,4, X={0,2, 1, 0, 0, 0,4}.

1.6.10. Неразрешима. 1.6.11 z=−0, 5, X={0, 0,3, 0,3, 0,16, 0}. 1.6.12 z=-6, X={1,5, 1, 0, 0,

0,5}. 1.6.13 Неразрешима. 1.6.14 z=-15,5, X={1, 5, 0, 1, 5, 2, 0}. 1.6.15 z=-8,5, X={0, 2,5,

1, 0, 1,5} 1.6.16 z=-6,2, X={0, 0,2, 0, 1, 0}. 1.6.17 Неразрешима. 1.6.18 z=-6,5, X={2,5,

3,5, 0, 1,5, }. 1.6.19 z=-2, X={

, 0,

, 0}. 1.6.20 z=-5, X={0,71, 1,107, 0,92, 0}. 1.6.21

z=-0,204, X={0, 0,42, 0,26, 0, 0,102}. 1.6.22 z=-1, X={1, 0, 3, 0,5, 0}.

2.5.1 250 2.5.2 310 2.5.3 432 2.5.4 190 2.5.5 345 2.5.6 1880 2.5.7 1055 2.5.8 225 2.5.9

1190 2.5.10 715 2.5.11 2280 2.5.12 700 2.5.13 4880 2.5.14 3700 2.6.1 50.

2.6.2 53. 2.6.3 51. 2.6.4 67. 2.6.5 36. 2.6.6 71. 3.3.1 9.

3.3.2 12. 3.3.3 9 3.3.4 7 3.3.5 16 3.3.6 28 3.3.7 11

4.1.1 F=16; X={0, 4}. 4.1.2 F=6; X={0, 3}. 4.1.3 F=16; X={2, 0}. 4.1.4 F=22; X={2,

1}. 4.1.5 F=4; X={0, 1}. 4.1.6 F=5; X={1, 2}. 4.1.7 F=3; X={0, 3}. 4.1.8 F=10; X={4, 3}.

167

168 Глава 6. ИСПОЛЬЗОВАНИЕ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ

4.1.9 F=22; X={2, 1} 4.1.10 F=11; X={6, 5} 4.1.11 F=6; X={4, 2} 4.1.12 F=2; X={0, 2}

4.1.13 F=12; X ={3, 2} 4.1.14 F=2; X={1, 1}. 4.1.15 F=2; X={1, 1}. 4.1.16 F=2; X={1,

1}. 4.1.17 F=48; X={18, 14}. 4.1.18 F=16; X={2, 1}. 4.1.19 F=6; X={2, 2}. 4.1.20 F=5;

X={3, 2}. 4.1.21 F=12; X={1, 2}. 4.1.22 F=5; X={3, 1}. 4.1.23 F=3; X={1, 2}. 4.1.24

F=10; X={1, 1}. 4.1.25 F=32; X={4, 0}. 4.1.26 F=28; X={8, 4}. 4.1.27 F=10; X={1, 1}.

4.1.28 F=3; X={0, 3}.

4.2.1 102. 4.2.2 26. 4.2.3 147 4.2.4 117 4.2.5 116 4.2.6 104 4.2.7 91 4.2.8 80 4.2.9 109

4.2.10 92 4.2.11 139 4.2.12 126 4.2.13 85 4.2.14 147

5.8.1 95. 5.8.2 130. 5.8.32 450. 5.8.4 300. 5.8.5 9. 5.8.6 49. 5.8.7 20. 5.8.8 1,18.

5.8.9 1,45. 5.8.11 7, путь (1 → 2 → 6). 5.8.12 4, путь (1 → 2 → 7). 5.8.13 5, путь

(1 → 3 → 4 → 6), 5.8.14 (3,1,5,2,4), 5.8.15 (2,6,4,5,3,1), 5.8.16 (3,1,5,4,6,2),

Литература

[1] Петросян Л. А., Зенкевич Н. А. Теория игр. — М.: изд-ва ВШ и

”

Книжный дом

”

Университет“, 1998.—300 с.

[2] Таха Х. Введение в исследование операций: в 2-х книгах . Т.1–2. — М.: Мир, 1985.—

479 с.; издание 6-ое — М.,

”

Вильямс“, 2001, 846 с.; издание 7-ое — М.,

”

Вильямс“,

2005, 312 с.

[3] Вагнер Г. Основы исследования операций.Т.1–3. — М.: Мир, 1972–1973.—632 с.

[4] Форд Л., Фалкерсон Д. Потоки в сетях. — М.: Мир, 1966.—230 с.

[5] Гейл Д. Теория линейных экономических моделей. — М.: Мир, 1969.—342 с.

[6] Ху Т. (1974). Целочисленное программирование и потоки в сетях — М.: Мир, 1974.

[7] Романовский И. В. Алгоритмы решения экстремальных задач. — М.: Наука, 1977.

[8] Схрейвер А. Теория линейного и целочисленного программирования. Т.1–2, — М.:

Мир, 1991.

[9] Беллман Р., Гликсберт И., Гросс О. Некоторые вопросы математической теории

процессов управления. — М: ИЛ, 1962.

[10] Зайченко, Ю. П. Шумилова, С. А. Исследование операций. Сборник задач.

Киев: Вища школа. Изд-во при Киев.ун-те, 1984.—224 с.

[11] Вентцель Е. С. Исследова ние операций. — М: Советское радио. 1972.—552 с.

[12] Матросов А. В. Maple 6. Решение задач высшей математики и механики. — СПб.:

”

БХВ-Петербург“. 2001.—528 с.:ил. — М: Советское радио. 1972.—552 с.

169

170 Литература

[13] Васильев Ф. П. Иваницкий А. Ю. Линейное программирование. — М.:изд-во

”

Фак-

ториал Пресс“. 2003.—352 с.

[14] Саати Т. Л. Математические методы исследования операций. — М.:Воениздат.

1963.—420 с.