Набор средств для линейного программирования GNU: Часть 2: Проблемы средней сложности в линейном программировании

Как привести в порядок почтовое отделение и извлечь максимальную пользу из вредной диеты

Данная статья продолжает серию публикаций, посвященных набору средств для линейного программирования GNU и клиентской служебной программе glpsol с языком моделирования GNU MathProg. В данной части Вы изучите способы создания простой мультипеременной и объявления двумерных параметров на примере задачи о диете. Затем Вы познакомитесь с выражениями MathProg и целочисленными переменными решения при работе над задачей распределения ресурсов почтового отделения.

Родриго Серон, , IBM

Родриго Серон Феррейра де Кастро (Rodrigo Ceron Ferreira de Castro) - штатный специалист по программному обеспечению в Центре Технологий Linux компании IBM. В 2004 году он окончил Государственный Университет в Кампинас, Бразилия (UNICAMP) и получил премию Государственного Технического Института и почетное свидетельство Инженерно-Технического Совета. Он неоднократно выступал на конференциях, посвященных проблемам ПО с открытым программным кодом, в Бразилии и других странах.



02.02.2007

Данная статья является второй в серии из трех частей, посвященных набору средств для линейного программирования 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 должна быть минимизирована:

Уравнение 1

Следующий шаг - написание неравенств для ограничений. Обратите внимание, что есть минимальное количество калорий, шоколада, сахара и жира, получение которого должна обеспечивать данная диета. Каждое из этих четырех требований является ограничением; они могут быть записаны следующим образом:

Уравнение 2
Уравнение 3

Обратите внимание, что ананасовый творожный пудинг и газированная вода не содержат шоколад.

Уравнение 4
Уравнение 5

И, наконец, ограничения по знаку:

Уравнение 6

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


Решение 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):

Уравнение 7
Уравнение 8
Уравнение 9
Уравнение 10
Листинг 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: количество сотрудников, приступающих к работе в воскресенье

Функция цели, требующая минимизации, это количество нанятых служащих, представленная как:

Уравнение 11

Каковы ограничения? Для каждого дня есть ограничение на минимальное требуемое количество служащих, работающих в этот день. Рассмотрим, например, понедельник. Кто работает по понедельникам? Первичный (частичный) ответ, который приходит в голову - "люди, приступившие к работе в понедельник" Но кто еще? Принимая во внимание, что служащие должны работать 5 дней подряд, приступившие к работе в воскресенье также будут работать в понедельник (вспомните описание задачи). По той же причине можно заключить, что служащие, вышедшие на работу в субботу, пятницу и четверг, также будут работать в понедельник.

Это ограничение гарантирует, что по меньшей мере 17 служащих будут работать в понедельник.

Уравнение 12

Аналогично:

Уравнение 13
Уравнение 14
Уравнение 15
Уравнение 16
Уравнение 17
Уравнение 18

Не забудьте, кроме того, ограничения по знаку:

Уравнение 19

Решение 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 решения целочисленной задачи.

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

В третьей и последней части обсуждается задача максимизирования прибыли производителя парфюмерных товаров, и рассматриваются двоичные переменные решения (переменные двоичного выбора) на примере задачи о расстановке игроков баскетбольной команды.

Ресурсы

Научиться

Получить продукты и технологии

  • Создайте свой новый проект для Linux с пробным ПО IBM, доступным для загрузки напрямую с developerWorks.

Обсудить

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux, Open source
ArticleID=193856
ArticleTitle=Набор средств для линейного программирования GNU: Часть 2: Проблемы средней сложности в линейном программировании
publish-date=02022007