![Закрыть [x]](http://dw1.s81c.com/i/c.gif){kind=small}
Данная статья является второй в серии из трех частей, посвященных набору средств для линейного программирования GNU (GLPK). Для знакомства с GLPK прочитайте первую часть серии, "Набор средств для линейного программирования GNU, Часть 1: Введение в линейную оптимизацию."
Данная задача взята из Исследования Операций: Приложения и Алгоритмы, Издание четвертое, автор Вейн Л. Уинстон (Томсон, 2004 г.); для справки см. Ресурсы.
Моя диета требует, чтобы вся пища, которую я ем, принадлежала к одной из четырех "основных пищевых групп": шоколадный кекс, мороженое, газированная вода и творожный пудинг. В настоящий момент следующие четыре вида продуктов доступны для потребления: шоколадное пирожное с орехами, шоколадное мороженое, кола и ананасовый творожный пудинг. Одно пирожное стоит $0.50, одна порция мороженого стоит $0.20, одна бутылка колы стоит $0.30, и один кусок пудинга стоит $0.80. Каждый день я должен получать не менее 500 калорий, 6 унций (1 унция = 28,35 грамм) шоколада, 10 унций сахара и 8 унций жира. Содержание питательных веществ на единицу для каждого вида пищи приведено в таблице ниже. Удовлетворите мои потребности в питании с наименьшими затратами.
Для обобщения важной информации по задаче:
Стоимость пищи за единицу
- Шоколадное пирожное с орехами (Brownie): $0.50
- Шоколадное мороженое: $0.20 (1 порция)
- Газированная вода: $0.30 (1 бутылка)
- Ананасовый творожный пудинг: $0.80 (1 кусок)
Ежедневные потребности в пище
- 500 калорий
- 6 унций шоколада
- 10 унций сахара
- 8 унций жира
Содержание питательных веществ на единицу для каждого вида пищи
- Шоколадное пирожное с орехами : 400 калорий, 3 унции шоколада, 2 унции сахара, 2 унции жира
- Шоколадное мороженое (1 порция): 200 калорий, 2 унции шоколада, 2 унции сахара, 4 унции жира
- Газированная вода (1 бутылка): 150 калорий, 0 унций шоколада, 4 унции сахара, 1 унция жира
- Ананасовый творожный пудинг (1 кусок): 500 калорий, 0 унций шоколада, 4 унции сахара, 5 унций жира
Моделирование задачи о диете должно быть легче после решения задачи Giapetto в Части 1. Сначала давайте определим переменные решения.
Цель - удовлетворить ежедневные потребности в питании при минимальных затратах на него. Следовательно, переменные решения - это количество еды каждого типа, которое необходимо приобрести:
Переменные Еда
-
x1: количество шоколадных пирожных с орехами -
x2: количество порций шоколадного мороженого -
x3: количество бутылок газированной воды -
x4: количество кусков ананасового творожного пудинга
Теперь функция цели может быть записана в виде функции от переменных решения.
Стоимость диеты (сумма затрат на нее) z должна быть
минимизирована:
Следующий шаг - написание неравенств для ограничений. Обратите внимание, что есть минимальное количество калорий, шоколада, сахара и жира, получение которого должна обеспечивать данная диета. Каждое из этих четырех требований является ограничением; они могут быть записаны следующим образом:
Обратите внимание, что ананасовый творожный пудинг и газированная вода не содержат шоколад.
И, наконец, ограничения по знаку:
Попробуйте вообразить ОДЗ данной задачи. Задача имеет четыре переменных. Итак, область имеет четыре координатных оси. Это сложно изобразить на чертеже, поэтому используйте Ваше воображение. Вначале решение может находиться в любом месте нашего четырехмерного пространства. С каждым новым ограничением область решения уменьшается, принимая форму многогранника.
Решение GNU MathProg задачи о диете
Примечание: Нумерация строк в Листинге 1 приведена лишь для удобства обращения к программе.
Листинг 1. Решение GNU MathProg задачи о диете
1 #
2 # Diet problem
3 #
4 # This finds the optimal solution for minimizing the cost of my diet
5 #
6
7 /* sets */
8 set FOOD;
9 set NEED;
10
11 /* parameters */
12 param NutrTable {i in FOOD, j in NEED};
13 param Cost {i in FOOD};
14 param Need {j in NEED};
15
16 /* decision variables: x1: Brownie, x2: Ice cream, x3: soda, x4: cake*/
17 var x {i in FOOD} >= 0;
18
19 /* objective function */
20 minimize z: sum{i in FOOD} Cost[i]*x[i];
21
22 /* Constraints */
23 s.t. const{j in NEED} : sum{i in FOOD} NutrTable[i,j]*x[i] >= Need[j];
24
25 /* data section */
26 data;
27
28 set FOOD := Brownie "Ice cream" soda cake;
29 set NEED := Calorie Chocolate Sugar Fat;
30
31 param NutrTable: Calorie Chocolate Sugar Fat:=
32 Brownie 400 3 2 2
33 "Ice cream" 200 2 2 4
34 soda 150 0 4 1
35 cake 500 0 4 5;
36
37 param Cost:=
38 Brownie 0.5
39 "Ice cream" 0.2
40 soda 0.3
41 cake 0.8;
42
43 param Need:=
44 Calorie 500
45 Chocolate 6
46 Sugar 10
47 Fat 8;
48
49 end;
|
В строках 8 и 9 описаны два множества: FOOD (Пища) и NEED (Потребность), но элементы этих множеств объявлены в
разделе данных в строках 28 и 29. Множество FOOD содержит
четыре заданных типа продуктов.
Поскольку пробел разделяет элементы множества друг от друга, элемент Ice cream необходимо заключать в двойные кавычки (вместо
менее привлекательного варианта icecream, к примеру).
Если Вы хотите использовать символы не ASCII в именах в MathProg, используйте
двойные кавычки даже при отсутствии пробелов.
Возвращаемся в раздел Модель. Множество NEED (Потребность)
содержит четыре диетические потребности. В строках 12, 13 и 14 описаны параметры
задачи: Need (Потребность), Cost (Стоимость), и NutrTable (Таблица
питательности). Для каждого элемента множества FOOD
имеется стоимость. Для каждой питатедльной потребности есть соответствующее значение
в множестве NEED. Пепробуйте использовать индексные
переменные с разными именами для каждого множества соответственно, это неплохая
идея, особенно при отладке программы. В данно случае для множества FOOD используется индекс i, а
для множества NEED индекс j.
Переметры Cost (стоимость) и Need (Потребность) в разделе данных описаны в строках 37 - 47.
Таблица питательности, описанная в строке 12 и заполненная данными в строках 31 - 35,
имеет два измерения, поскольку каждый вид продукта имеет несколько значений
питательности.Следовательно, таблица питательности NutrTable это таблица соответствий между множествами FOOD (Пища) и
NEED (Потребность). Обратите внимание, что порядок строк и столбцов тот
же, что и порядок элементов в каждом из множеств, а имена индексных переменных
встречаются в строках 12, 13 и 14.
В данном примере индекс i используется для обозначения
строк, а j для обозначения столбцов, как и ожидается
большинством математиков, читающих данный учебник. Синтаксис объявления двумерных
параметров (до N столбцов и M строк) следующий:
Листинг 2. Синтаксис объявления двумерных параметров
param label : J_SET_VAL_1 J_SET_VAL_2 ... J_SET_VAL_N :=
I_SET_VAL_1 param_1_1 param_1_2 ... param_1_N
I_SET_VAL_2 param_2_1 param_2_2 ... param_2_N
... ... ... ... ...
I_SET_VAL_M param_M_1 param_M_2 ... param_M_N; |
Не забудьте поставить := в конце первой строки и ; в конце последней строки.
В строке 17 объявляются переменные решения и указывается, что каждая из них не может
принимать отрицательное значение. Это очень простое описание, поскольку массив x описывается автоматически с элементами множества FOOD.
Функция цели в строке 20 минимизирует общую стоимость пищи и определяется как общая
сумма каждой переменной решения (количество пищи), помноженная на стоимость за
единицу пищи. Обратите внимание, что индекс i
используется в множестве FOOD.
В строке 23 объявляются все четыре ограничения. Запись отличается краткостью и
изяществом, поэтому обратите на нее внимание! Описание слева от знака двоеточия
(:) поручает GLPK создать ограничение для каждой
потребности множества NEED: const[Calorie],const[Chocolate], const[Sugar], и const[Fat].
Каждое из этих ограничений принимает каждую потребность в питании и добавляет
значение объема каждого типа пищи, помноженного на количество потребности, которое
он может удовлетворить на единицу пищи; общее значение должно быть больше или равно
минимальной потребности данной составляющей для сбалансированной диеты.
В расширенном виде это объявление будет выглядеть следующим образом (i используется в множестве FOOD):
Листинг 3. Выходные данные glpsol для данной задачи
Problem: diet
Rows: 5
Columns: 4
Non-zeros: 18
Status: OPTIMAL
Objective: z = 0.9 (MINimum)
No. Row name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 z B 0.9
2 const[Calorie]
B 750 500
3 const[Chocolate]
NL 6 6 0.025
4 const[Sugar] NL 10 10 0.075
5 const[Fat] B 13 8
No. Column name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 x[Brownie] NL 0 0 0.275
2 x['Ice cream']
B 3 0
3 x[soda] B 1 0
4 x[cake] NL 0 0 0.5
Karush-Kuhn-Tucker optimality conditions:
KKT.PE: max.abs.err. = 1.82e-13 on row 2
max.rel.err. = 2.43e-16 on row 2
High quality
KKT.PB: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
High quality
KKT.DE: max.abs.err. = 5.55e-17 on column 3
max.rel.err. = 4.27e-17 on column 3
High quality
KKT.DB: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
High quality
End of output
|
Эти данные показывают, что минимальная стоимость и оптимальное значения диеты равно $0.90. Какое условие ограничило это решение?
Во втором разделе отчета сказано, что введены ограничения по максимальному потреблению шоколада и сахара, поэтому эта диета имеет минимальные требуемые объемы шоколада и сахара. Предельное значение сообщает, что если бы ограничение по шоколаду было снижено на одну единицу (5 унций вместо 6), функция цели изменилась бы на 0.025 (и вместо 0.9 стала бы 0.875). Аналогично, при изменении ограничения по сахару на одну единицу функция цели изменилась бы на 0.075. Это имеет смысл: меньше ешь - меньше платишь. Важно провести проверку этих существенных предельных значений и полученных объемов. Например, если Вам сообщается, что оптимальным является потребление 200 фунтов шоколада и при этом Вы получите 0 калорий, это должно показаться Вам несколько подозрительным (и, возможно, приятным).
В третьем разделе приведены оптимальные значения переменных решения: 3 порции мороженого и одна бутылка газированной воды. Шоколадные пирожные с орехами и ананасовый творожный пудинг имеют крайние значения, поскольку их значение на грани ограничения по знаку. Это крайнее значение сообщает, что, если бы значение шоколадных пирожных с орехами могла быть равным -1, функция цели изменилась бы на 0.275, но, конечно, это не проходит к постановке данной задачи.
Задача взята из "Исследования Операций":
Почтовому отделению требуется различное количество служащих, занятых полный рабочий день, в разные дни недели [приведены ниже]. Согласно уставу профсоюза, каждый служащий, занятый полный рабочий день, должен работать 5 дней подряд, а затем иметь 2 выходных дня. Например, служащий, занятый с понедельника по пятницу, должен иметь выходные дни в субботу и воскресенье. Почтовому отделению нужно удовлетворить свои ежедневные потребности, используя только служащих с полным рабочим днем Минимизируйте количество служащих, которых нужно нанять.
Обобщение важной информации по задаче:
- Каждый сотрудник, занятый полный рабочий день, работает 5 дней подряд и берет затем два выходных дня
- День 1 (Понедельник): требуется 17 служащих
- День 2 : требуется 13 служащих
- День 3 : требуется 15 служащих
- День 4 : требуется 19 служащих
- День 5 : требуется 14 служащих
- День 6 : требуется 16 служащих
- День 7 (Воскресенье) : требуется 11 служащих
Почтовому отделению для удовлетворения его потребностей необходимо сделать количество принимаемых на работу сотрудников минимальным.
Начнем с определения переменных решения для данной задачи. Вы можете попробовать решить ее с 7 переменными, по одной на каждый день недели, со значением равным количеству служащих, работающих каждый день недели. Хотя это кажется решением задачи на первый взгляд, оно не может удовлетворить ограничению о 5-ти дневной непрерывной рабочей неделе, согласно которому служащий работает 5 дней подряд, поскольку то, что служащий работает в данный день не означает, что он работает на следующий день.
Правильный подход должен гарантировать, что служащий, приступивший к работе в i-ый день, будет также работать и четыре следующих дня,
поэтому правильным будет использовать xi для
обозначения количества служащих, приступивших к работе в i-ый день. Руководствуясь данным подходом, удовлетворить ограничению о 5-ти
дневной непрерывной рабочей неделе намного проще. Имеем следующие переменные
решения:
-
x1: количество сотрудников, приступающих к работе в понедельник -
x2: количество сотрудников, приступающих к работе во вторник -
x3: количество сотрудников, приступающих к работе в среду -
x4: количество сотрудников, приступающих к работе в четверг -
x5: количество сотрудников, приступающих к работе в пятницу -
x6: количество сотрудников, приступающих к работе в субботу -
x7: количество сотрудников, приступающих к работе в воскресенье
Функция цели, требующая минимизации, это количество нанятых служащих, представленная как:
Каковы ограничения? Для каждого дня есть ограничение на минимальное требуемое количество служащих, работающих в этот день. Рассмотрим, например, понедельник. Кто работает по понедельникам? Первичный (частичный) ответ, который приходит в голову - "люди, приступившие к работе в понедельник" Но кто еще? Принимая во внимание, что служащие должны работать 5 дней подряд, приступившие к работе в воскресенье также будут работать в понедельник (вспомните описание задачи). По той же причине можно заключить, что служащие, вышедшие на работу в субботу, пятницу и четверг, также будут работать в понедельник.
Это ограничение гарантирует, что по меньшей мере 17 служащих будут работать в понедельник.
Аналогично:
Не забудьте, кроме того, ограничения по знаку:
Решение GNU MathProg задачи о почтовом отделении
Примечание: Нумерация строк в Листинге 4 приведена лишь для удобства обращения к программе.
Листинг 4. Решение задачи о почтовом отделении
1 #
2 # Post office problem
3 #
4 # This finds the optimal solution for minimizing the number of full-time
5 # employees to the post office problem
6 #
7
8 /* sets */
9 set DAYS;
10
11 /* parameters */
12 param Need {i in DAYS};
13
14 /* Decision variables. x[i]: No. of workers starting at day i */
15 var x {i in DAYS} >= 0;
16
17 /* objective function */
18 minimize z: sum{i in DAYS} x[i];
19
20 /* Constraints */
21
22 s.t. mon: sum{i in DAYS: i<>'Tue' and i<>'Wed'} x[i] >= Need['Mon'];
23 s.t. tue: sum{i in DAYS: i<>'Wed' and i<>'Thu'} x[i] >= Need['Tue'];
24 s.t. wed: sum{i in DAYS: i<>'Thu' and i<>'Fri'} x[i] >= Need['Wed'];
25 s.t. thu: sum{i in DAYS: i<>'Fri' and i<>'Sat'} x[i] >= Need['Thu'];
26 s.t. fri: sum{i in DAYS: i<>'Sat' and i<>'Sun'} x[i] >= Need['Fri'];
27 s.t. sat: sum{i in DAYS: i<>'Sun' and i<>'Mon'} x[i] >= Need['Sat'];
28 s.t. sun: sum{i in DAYS: i<>'Mon' and i<>'Tue'} x[i] >= Need['Sun'];
29
30 data;
31
32 set DAYS:= Mon Tue Wed Thu Fri Sat Sun;
33
34 param Need:=
35 Mon 17
36 Tue 13
37 Wed 15
38 Thu 19
39 Fri 14
40 Sat 16
41 Sun 11;
42
43 end;
|
Строка 9 содержит объявление множества DAYS (Дни), а его
элементы (дни недели, начиная с понедельника) объявлены в строке 32 в разделе
данных.
Строка 12 содержит объявление параметра Need (Потребность)
для каждого дня из множества DAYS (Дни). Строки 34 - 41
определяют значения этого параметра: минимальное количество сотрудников, необходимое
на каждый день недели.
Строка 15 содержит объявление переменных решения как массива из семи переменных,
описанных в множестве DAYS (Дни), обозначающие количество
людей, начинающих работать в указанный день.
В строках 22 - 28 описаны ограничения для каждого дня недели. Обратите внимание, что было бы слишком утомительно указывать семь неравенств как суммы пяти переменных решения, не обязательно идущих по порядку, поскольку в некоторых ограничениях индексы могут перекрывать (overlap) индекс 7. GNU MathProg дает возможность программисту использовать выражения для упрощения этой операции.
Каждое ограничение есть сумма всех переменных решения, за исключением двух, не
задействованных в назначенный день (вместо специального включения пяти остальных).
Это выражение приводится в фигурных скобках ({}), что
определяет индексы для суммирования. Синтаксис выражения следующий:
{index_variable in your_set:
your_expression}
В выражении может использоваться логическое сравнение. В этом случае ограничение для
понедельника будет иметь вид: i<>'Tue' and
i<>'Wed', что означает " для
i отличного от Tue(Вт) и
для i отличного от Wed
(Ср)." Аналогично для других ограничений.
В выражениях также может использоваться логическое сравнение (==).
Листинг 5. Решение задачи о почтовом отделении glpsol
Problem: post
Rows: 8
Columns: 7
Non-zeros: 42
Status: OPTIMAL
Objective: z = 22.33333333 (MINimum)
No. Row name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 z B 22.3333
2 mon NL 17 17 0.333333
3 tue B 15 13
4 wed NL 15 15 0.333333
5 thu NL 19 19 0.333333
6 fri NL 14 14 < eps
7 sat NL 16 16 0.333333
8 sun B 15.6667 11
No. Column name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 x[Mon] B 1.33333 0
2 x[Tue] B 5.33333 0
3 x[Wed] NL 0 0 < eps
4 x[Thu] B 7.33333 0
5 x[Fri] NL 0 0 0.333333
6 x[Sat] B 3.33333 0
7 x[Sun] B 5 0
Karush-Kuhn-Tucker optimality conditions:
KKT.PE: max.abs.err. = 3.55e-15 on row 6
max.rel.err. = 2.37e-16 on row 6
High quality
KKT.PB: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
High quality
KKT.DE: max.abs.err. = 5.55e-17 on column 1
max.rel.err. = 2.78e-17 on column 1
High quality
KKT.DB: max.abs.err. = 5.55e-17 on row 6
max.rel.err. = 5.55e-17 on row 6
High quality
End of output
|
Минуточку! Никто не может заставить 1.33333 служащих приступить к работе в понедельник! Помните о необходимости проверки с точки зрения здравого смысла. Это одна из них.
GLPK необходимо принять во внимание, что переменные решения целочисленные. К счастью, в MathProg имеется отличный способ объявления целочисленных переменных. Просто измените строку 15 следующим образом:
var x {i in DAYS} >=0, integer;
Это очень просто. Ответ в выъодных данных glpsol для
целочисленного решения проблемы выглядят несколько иначе:
Листинг 6. Выходные данные glpsol для целочисленного решения задачи о почтовом отделении
Reading model section from post-office-int.mod...
Reading data section from post-office-int.mod...
50 lines were read
Generating z...
Generating mon...
Generating tue...
Generating wed...
Generating thu...
Generating fri...
Generating sat...
Generating sun...
Model has been successfully generated
lpx_simplex: original LP has 8 rows, 7 columns, 42 non-zeros
lpx_simplex: presolved LP has 7 rows, 7 columns, 35 non-zeros
lpx_adv_basis: size of triangular part = 7
0: objval = 0.000000000e+00 infeas = 1.000000000e+00 (0)
7: objval = 2.600000000e+01 infeas = 0.000000000e+00 (0)
* 7: objval = 2.600000000e+01 infeas = 0.000000000e+00 (0)
* 10: objval = 2.233333333e+01 infeas = 0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
Objective function is integral
+ 10: mip = not found yet >= -inf (1; 0)
+ 19: mip = 2.300000000e+01 >= 2.300000000e+01 0.0% (9; 0)
+ 19: mip = 2.300000000e+01 >= tree is empty 0.0% (0; 17)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 0.0 secs
Memory used: 0.2M (175512 bytes)
lpx_print_mip: writing MIP problem solution to `post-office-int.sol'...
|
Обратите внимание на запись о нахождении целочисленного оптимального решения задачи (INTEGER OPTIMAL SOLUTION FOUND), и, прежде чем оно было найдено, GLPK рассчитал оптимальное решение для упрощенной задачи (задачи, не требующей, чтобы переменные были целочисленными) (OPTIMAL SOLUTION FOUND).
Листинг 7. Целочисленное решение задачи о почтовом отделении
Problem: post
Rows: 8
Columns: 7 (7 integer, 0 binary)
Non-zeros: 42
Status: INTEGER OPTIMAL
Objective: z = 23 (MINimum) 22.33333333 (LP)
No. Row name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 z 23
2 mon 18 17
3 tue 13 13
4 wed 15 15
5 thu 19 19
6 fri 14 14
7 sat 16 16
8 sun 20 11
No. Column name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 x[Mon] * 1 0
2 x[Tue] * 2 0
3 x[Wed] * 3 0
4 x[Thu] * 7 0
5 x[Fri] * 1 0
6 x[Sat] * 3 0
7 x[Sun] * 6 0
End of output
|
В первом разделе сказано, что найденное решение оптимальное целочисленное, и что значение 23, найденное для функции цели, минимально. Почтовое отделение будет вынуждено нанять 23 служащих на полный рабочий день для удовлетворения cвоих потребностей. Также указано и оптимальное значение функции цели для упрощенной задачи (не рассматривающей переменные решения как целочисленные).
Пропустите второй раздел отчета, мы к нему еще вернемся. В третьем разделе приведены значения переменных решения. Эти значения целочисленные и минимизируют функцию цели задачи.
Теперь поговорим о втором разделе. В нем показаны значения ограничений. Некоторые из
них ограничены снизу, и Вы можете ожидать появление крайнего или неявного значения.
однако, не имеет смысла говорить о крайнем значении в целочисленных задачах. Область
допустимых значений целочисленной задачи не является непрерывной. Другими словами,
ОДЗ не является многогранником, а состоит из целочисленных пар (x1, x2, ..., xn) внутри или на
гранях фактически существующего многогранника для упрощенной задачи. Это означает,
что ОДЗ состоит из отдельных дискретных точек в пространстве, и, следовательно,
снятие одного из ограничений может (или не может) дать лучшее решение в пределах
нового многогранника.
Чтобы лучше понять обсуждаемую проблему, изучите простую ОДЗ:
Рисунок 1. ОДЗ для целочисленной задачи
Голубые точки, помеченные как x целочисленные пары (x1,x2). Это целочисленная область
допустимых значений двумерного множестваx1 X
x2, ограниченного условиями x1
>= 0, x2 >= 0, и
x1 + x2 <= 4. Если бы
функция цели для этого простого случая была функцией максимизации maximize z = x1 - x2, очевидно,
оптимальным решением была бы пара (2,0), и условие было
бы ограниченным (поскольку оптимальное решение лежит на прямой, заданной условием).
Если бы условие было изменено на единицу, x1 +
x2 <= 5, ОДЗ также была бы иной.
Рисунок 2. ОДЗ для другой целочисленной задачи
Оптимальным решением все еще была бы точка (2,0), хотя
теперь доступно больше целочисленных точек.
Таким образом, смягчение ограничения целочисленной задачи не обязательно влечет за собой изменение решения, поскольку ОДЗ дискретна и не непрерывна.
Другой вопрос, который Вы можете задать: "Связано ли оптимальное решение целочисленной задачи с оптимальным решением той же упрощенной (не целочисленной) задачи ?" Ответ на этот вопрос дает алгебра, на принципах которой построен симплекс-алгоритм, но объяснение механизмов его работы не входит в перечень проблем, рассматриваемых в данной статье. Просто знайте, что оптимальным решением нецелочисленной задачи всегда является одна из вершин многогранника. Всегда!
В первой ОДЗ, приведенной выше, оптимальным решением была правая вершина области
решений, треугольник, образованный всеми ограничениями. Функция цели возрастает в
направлении косой производной к функции цели. В простом случае косая производная к
x1 - x2, равна (1,-1). По этой причине оптимальное решение это самая
дальняя точка грани многогранника от центра оси координат с направляющим вектором
(1,-1). Поскольку целочисленное решение может лежать
только на грани или внутри многогранника, наилучшим результатом является нахождение
решения на вершине. В этом частном случае оптимальное решение и целочисленной и не
целочисленной задач одно и то же, но так бывает не всегда. Почему? Потму что эта
точка с целочисленными координатами не может находиться на том же удалении от начала
координат, что и точка решения с нецелочисленными координатами. Для других, не
настолько удачных случает, лучшая точка с целочисленными координатами будет
находиться внутри многогранника, и функция цели будет иметь значение хуже, чем для
нецелочисленной задачи, как Вы могли заметить на примере задачи о почтовом
отделении.
Помните, что в данном исследовании использовалась простая задача нахождения максимального значения с двумя переменными. В таком же исследовании для задачи нахождения минимального значения отыскивается точка минимизирующая значение функции цели, точка, ближайшая к началу координат (находящаяся в противоположном направлении к направлению косой производной к функции цели).
На примере задачи о диете Вы изучили, как формулировать простую задачу с несколькими переменными, как объявлять переметры с двумя переменными в GNU MathProg, и как интерпретировать решение задачи минимизации.
При решении задачи о постовом отделении мы ввели выражения MathProg и только
целочисленные переменные решения. Вы узнали, как интерпретировать выходные данные
glpsol решения целочисленной задачи.
Наконец, я обсудил визуальное представление области допустимых значений для целочисленной задачи и ее отношение к функции цели для целочисленных значений и для соответствующих задач без ограничения по целочисленности.
В третьей и последней части обсуждается задача максимизирования прибыли производителя парфюмерных товаров, и рассматриваются двоичные переменные решения (переменные двоичного выбора) на примере задачи о расстановке игроков баскетбольной команды.
Научиться
- Оригинал статьи: "The
GNU Linear Programming Kit, Part 2: Intermediate problems in linear
programming"
- Получите RSS поддержку для учебников по GLPK данной серии. (Узнайте больше о RSS поддержке контента
developerWorks.)
- Прочитайте все публикации данной серии по GLPK
- Задачи, рассматриваемые в данной статье взяты с
разрешения из книги
Исследование Операций: Приложения и Алгоритмы. Издание четвертое
, Вейн Л. Уинстон (Wayne L. Winston), Томсон 2004 г.
-
Он-лайн документация по GLPK
предоставляет дополнительную информацию о GLPK, получении ПО и
вступлении в общество GLPK.
- Подпишитесь на рассылку справочной
информации по GLPK или на рассылку с описанием
ошибок GLPK .
- Найдите больше информации для разработчиков Linux в
Разделе Linux на
developerWorks.
- Будьте в курсе технических событий и web-трансляций developerWorks.
Получить продукты и технологии
-
Закажите SEK для Linux, набор из двух DVD с новейшим пробным ПО IBM для
Linux от DB2®, Lotus®, Rational®, Tivoli® и WebSphere®.
- Создайте свой новый проект
для Linux с пробным ПО IBM, доступным для загрузки напрямую с developerWorks.
Обсудить
- Примите участие на форумах Linux и
Open Source.
Родриго Серон Феррейра де Кастро (Rodrigo Ceron Ferreira de Castro) - штатный специалист по программному обеспечению в Центре Технологий Linux компании IBM. В 2004 году он окончил Государственный Университет в Кампинас, Бразилия (UNICAMP) и получил премию Государственного Технического Института и почетное свидетельство Инженерно-Технического Совета. Он неоднократно выступал на конференциях, посвященных проблемам ПО с открытым программным кодом, в Бразилии и других странах.
Содержание
Теги
КнопкаПопулярные теги отображает самые распространенные теги для данной области контента (например: Java, Linux, WebSphere).
Кнопка Мои теги отображает Ваши теги для данной области контента (например: Java, Linux, WebSphere).
Популярные теги статьи |
Мои теги статьиПерейти к списку тегов
Популярные теги статьи |
Мои теги статьи