Набор средств для линейного программирования GNU: Часть 1: Введение в линейную оптимизацию

Найдите лучшее решение для сложных численных задач

Набор средств для линейного программирования GNU это мощный, проверенный инструмент для решения численных задач с множественными ограничениями. Данная статья посвящена описанию GLPK, клиентской служебной программы glpsol, и языку GNU MathProg, предназначенным для решения задач оптимизации операций для Giapetto's Woodcarving, Inc., вымышленного производителя игрушек.

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

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



01.02.2007

Введение

"Линейное программирование - инструмент для решения задач оптимизации. В 1947 году Джордж Данциг (George Dantzig) разработал эффективный метод, симплексный алгоритм, для решения задач линейного программирования. После разработки симплекс-алгоритма линейное программирование стало использоваться для решения задач оптимизации в различных сферах, от банковского дела до образования, лесной и нефтегазовой промышленности и грузоперевозок. В отчете по исследованию 500 наиболее успешных фирм 85% респондентов отметили, что используют в работе линейное программирование."

Цит. по Исследование Операций: Приложения и Алгоритмы, Издание четвертое, Вейн Л. Уинстон (Wayne L. Winston) (Томсон, 2004 г.); для ссылки см. Ресурсы ниже.

Для решения проблем линейного программирования существует множество инструментов. Хорошо известны специализированные инструменты, но многие специалисты по ПО с открытым программным кодом могут быть не знакомы с бесплатным GLPK.

Серия состоит из трех статей, иллюстрирующих возможности и использование GLPK, и данная статья, первая в серии, вкратце описывает GLPK, а затем демонстрирует возможности и применение языка GNU MathProg в GLPK.

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

Набор средств для линейного программирования GNU

Набор средств для линейного программирования GNU (GLPK) это библиотека (стандартных) программ, использующих широко известные алгоритмы исследования операций для решения задач линейного программирования. Программы реализуют такие алгоритмы, как симплекс, метод ветвей и границ, внутренней точки одновременного решения прямой и двойственной задач, и другие. Для получения дополнительной информации, обратитесь к руководству по GLPK, включенному в загрузку GLPK. (Для загрузки GLPK, см. раздел Ресурсы, где указана ссылка на страницу GLPK на gnu.org.)

GLPK это не программа -- он не может быть запущен и не имеет функции main(). Вместо этого клиент вводит данные задачи в программу алгоритма, посредством GLPK API и получает обратно результаты. Клиентом GLPK по умолчанию является программа glpsol, которая взаимодействует с этим API. Обычно программа вроде glpsol называется решающей программой, а не клиентом, поэтому далее Вам будет встречаться именно этот термин.


Язык моделирования GNU MathProg

Язык моделирования GNU MathProg прост и удобен для описания задач линейного программирования. В общем виде описание задачи состоит из:

  • Переменные решения задачи.
  • Функция цели (objective function). Имя функции является стандартным в теории исследования операций.
  • Ограничительные условия задачи.
  • Параметры задачи (данные).

Начнем с простого примера с двумя переменными: Giapetto's Woodcarving, Inc.


Giapetto's Woodcarving Inc.

Данная задача взята из Исследования Операций:

Giapetto's Woodcarving Inc. производит два вида деревянных игрушек: солдатики и паровозики. Солдатики продаются по цене $27 за штуку, при затратах сырья на $10 на их производство. Каждый произведенный Giapetto солдатик увеличивает переменные Трудовые затраты и Непроизводственные затраты на $14. Паровозики продаются по цене $21 за штуку, при затратах сырья на $9 на их производство. Каждый произведенный Giapetto паровозик увеличивает переменные Трудовые затраты и Непроизводственные затраты на $10. Производство деревянных солдатиков и паровозиков требует двух типов квалифицированного труда: плотничные работы и отделка. При производстве солдатика затрачивается один час на плотничные работы и 2 часа на отделку. При производстве паровозика затрачивается один час на плотничные работы и один час на отделку. Каждую неделю Giapetto может получать все необходимое количество сырья, но только 100 часов по отделке и 80 часов плотничных работ. Спрос на паровозики не ограничен, но не более 40 солдатиков покупается еженедельно. Giapetto нужно максимально повысить еженедельный доход (выручка от продаж (revenues) - издержки (costs)).

Обобщим важную информацию и условия данной задачи:

  1. Есть два виде деревянных игрушек: солдатики и паровозики.
  2. Солдатик продается по цене $27 при затратах сырья на $10 на его производство и увеличивает переменные Трудовые затраты и Непроизводственные затраты на $14.
  3. Паровозик продается по цене $21 при затратах сырья на $9 на его производство и увеличивает переменные Трудовые затраты и Непроизводственные затраты на $10.
  4. При производстве солдатика затрачивается один час на плотничные работы и 2 часа на отделку.
  5. При производстве паровозика затрачивается один час на плотничные работы и один час на отделку.
  6. Не более 100 часов по отделке и 80 часов плотничных работ доступны еженедельно.
  7. Спрос на паровозики не ограничен, но не более 40 солдатиков покупается еженедельно.

Цель: найти количество солдатиков и паровозиков, производство которых позволит максимально увеличить прибыль.


Моделирование

При моделировании задачи линейного программирования сначала определяются переменные решения, поскольку они будут меняться с каждой итерацией симплекс-алгоритма и определять значение функции цели и, следовательно, оптимального решения. В задаче о Giapetto функция цели - прибыль, которая является функцией от двух переменных - количество солдатиков и количество паровозиков, производимых еженедельно. Поэтому имеем две переменные решения:

  • x1: количество солдатиков, производимых еженедельно
  • x2: количество паровозиков, производимых еженедельно

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

уравнение1


Обратите внимание, что прибыль линейно зависит от x1 и x2 -- это линейная задача.

На первый взгляд может показаться, что максимальное увеличение прибыли достигается простым увеличением значений x1 и x2. Пожалуй, если б жизнь была настолько проста, мы бы все начали производство солдатиков и паровозиков и переехали бы на Карибы! К несчастью, существуют определенные ограничения, задающие пределы для выбираемых переменных решения (в противном случае модель окажется, скорее всего, неверна).

Вспомните условия данной задачи. Первые три определяют переменные решения и функцию цели. Четвертое и шестое говорят о том, что производство солдатиков требует затрат времени на плотничные работы и отделку. Ограничением здесь является то, что Giapetto имеет конечное число часов на плотничные работы и на отделку. Это ограничивающее условие! Давайте проанализируем его для большей ясности.

При производстве одного солдатика затрачивается один час на плотничные работы и 2 часа на отделку, и Giapetto имеет не более 100 часов по отделке еженедельно, поэтому не может производить более 50 солдатиков в неделю. Подобным образом ограничение числа часов на плотничные работы ограничивает количество производимых солдатиков 80 шт. в неделю. Обратите внимание, что первое ограничение более строгое, чем второе. Первое ограничение фактически является подусловием второго, тем самым, делая его (второе ограничение) излишним.

В предыдущем абзаце рассмотрено, как моделировать задачу оптимизации, но анализ не завершен, поскольку не были рассмотрены все необходимые переменные. Это не является окончательным решением задачи Giapetto. Итак, как же подойти к данной задаче?

Начните с анализа ограничивающих факторов для определения ограничивающих условий. Во-первых, что ограничивает количество часов на отделку? Поскольку и солдатики, и паровозики требуют времени на отделку, и те, и другие должны приниматься во внимание. Предположим, произведено 10 солдатиков и 20 паровозиков. Необходимое количество часов на отделку будет 10 раз по 2 часа (для солдатиков) плюс 20 раз по 1 часу (для паровозиков), что в сумме составит 40 часов на отделку. Общее ограничение, выраженное через переменные решения, выглядит следующим образом:

уравнение2


Существует множество пар (x1,x2), удовлетворяющих данному неравенству, поэтому оно не определяет наилучшее сочетание для предприятия Giapetto.

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

уравнение3


Отлично! Есть еще одно дополнительное ограничение для данной задачи. Помните еженедельный спрос на солдатиков? Согласно описанию задачи, может быть произведено не более 40 солдатиков в неделю:

уравнение4


Спрос на паровозики не ограничен, поэтому для них не устанавливается ограничений. Модель завершена и состоит из следующих уравнений:

уравнение5
уравнение6
уравнение7
уравнение8
уравнение9


Обратите внимание на последнее условие. Оно гарантирует, что значение переменных решения всегда положительны. Задача не требует этого явным образом, но это важно (и очевидно).

Теперь GLPK может решить данную модель (поскольку GLPK хорошо решает задачи оптимизации линейного программирования).


Немного теории

Давайте рассмотрим область решения задачи. Имея две переменные решения, оно имеет два измерения.

Рисунок 1. Неограниченное пространство Giapetto
Неограниченное пространство Giapetto

Решения (x1,x2) вне первого квадранта (где все значения положительны) были отвергнуты. Обратите внимание, тем не менее, что область решения все еще не ограничена (это был бы случай, при котором я бы отправился на Карибы!)

По мере написания ограничений это неограниченная область решений приобретает границы. С Уравнением 6, приведенным выше, результат более интересен.

Рисунок 2. Пространство Giapetto с учетом ограничения для часов на отделку
Пространство Giapetto с учетом ограничения для часов на отделку

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

После введения ограничения, выраженного в Уравнении 7, область решения уменьшается.

Рисунок 3. Пространство Giapetto с учетом ограничения для часов на отделку и плотничные работы
Пространство Giapetto с учетом ограничения для часов на отделку и плотничные работы

Обратите внимание, что область решения становится меньше, что означает наличие в ней меньшего числа пар решений (x1,x2). После введения ограничения, выраженного в Уравнении 8, результат становится еще меньше.

Рисунок 4. Область допустимых решений задачи Giapetto
Область допустимых решений задачи Giapetto

Область решения становится меньше. Область решения, удовлетворяющая всем ограничениям, называется областью допустимых значений (ОДЗ). На рисунке 4 показана ОДЗ для задачи Giapetto. Любая пара (x1,x2), из этой области является потенциальным решением задачи.

Вопрос теперь стоит следующим образом: какая из этих пар делает прибыль Giapetto наибольшей?


Использование GLPK для решения модели

GLPK превосходный инструмент для решения подобной задачи. Математическая формулировка задачи Giapetto должна быть написана на языке GNU MathProg. Ключевые элементы для объявления следующие:

  • Переменные решения
  • Функция цели
  • Ограничения
  • Набор данных задачи

Следующая программа приводит решение задачи Giapetto с помощью MathProg. Порядковые номера строк не являются частью программного кода, а приведены для удобства обращения к нему.

Листинг 1. Первое решение задачи Giapetto: giapetto.sol
  1  # 
  2  #  задача Giapetto 
  3  # 
  4  #  данная программа отыскивает оптимальное решение для максимизации прибыли Giapetto 
  5  # 
  6  
  7   /* переменные решения */ 
  8   var x1 >=0; /*солдатики (soldier) */ 
  9   var x2 >=0; /* паровозики (train) */
  10 
  11   /* функция цели */ 
  12   maximize z: 3*x1 + 2*x2; 
  13 
  14   /*ограничения */ 
  15   s.t. Finishing : 2*x1 + x2 <= 100;
  16   s.t.Carpentry : x1 + x2 <= 80; 
  17   s.t. Demand : x1 <= 40;
  18 
  19   end;

Строки 1 - 5 это комментарии. Символ # в конце строки обозначает начало комментария. Комментарии в стиле C (/* */) также могут быть использованы (как показано в строке 7), и могут работать даже в середине объявления.

Первый шаг MathProg -объявление переменных решения. Строки 8 и 9 объявляют переменные x1 и x2. Объявление переменной решения начинается с зарезервированного слова var. Для упрощения введения ограничения по знаку (см. неравенство 9), MathProg позволяет вводить ограничение >= 0 в описание переменной решения, как в строках 8 и 9. Каждое выражение в GNU MathProg должно заканчиваться точкой с запятой (;). Вспомните, что x1 обозначает количество солдатиков, а x2 обозначает количество паровозиков. Эти переменные могли бы быть названы солдатики и паровозики, но это бы привело в замешательство математиков, читающих этот учебник.

Строка 12 содержит объявление функции цели. Линейные задачи могут быть на максимизацию или минимизацию. Помните, математическая модель Giapetto реализует задачу максимизации, поэтому зарезервированное слово maximize, а не minimize является подходящим. Функция цели носит имя z и равна 3x1 + 2x2. Обратите внимание, что:

  • Символ двоеточие (:) разделяет имя функции цели и ее описание.
  • Символ звездочка (*) обозначает умножение, аналогично, символы плюс (+), минус (-), и прямой слэш (/) обозначают сложение, вычитание и деление, как Вы и ожидали.

Строки 15, 16, и 17 описывают ограничения. Хотя указание s.t. не требуется в начале строки для объявления ограничения, это улучшает читабельность кода

Три ограничения Giapetto названы Finishing (Отделка), Carpentry (Плотничные работы), и Demand (Спрос). Каждый из них описан как математическая модель. Символы <= и >= обозначают неравенство. Не забывайте ; в конце каждого объявления.

Каждый файл GNU MathProg должен заканчиваться строкой end;, как показано в строке 19.

Теперь glpsol может использовать этот файл как входные данные. Но, подождите минуту, где же раздел данных нашей задачи? Ну, поскольку данная задача столь проста, все данные напрямую включены в функцию цели и объявления ограничений в виде коэффициентов при переменных решения в объявлениях. Например, в функции цели коэффициенты 3 и 1 являются частью данных задачи. Когда я перепишу эту задачу с использованием набора данных, Вам станет ясно, как работает программа, поэтому сейчас не волнуйтесь по этому поводу.

Хорошим стилем программирования являются использование расширения .mod для входных файлов MathProg и перенаправление решения в файл с расширением .sol. Это не требование -- Вы можете использовать любое имя файла и его расширение. Для данного примера файл Giapetto MathProg для ввода - giapetto.mod, а для вывода - giapetto.sol. теперь запустите glpsol в выбранном терминале:

glpsol -m giapetto.mod -o giapetto.sol

В данной командной строке использованы два параметра glpsol:

  • Параметр -m сообщает glpsol, что входные данные написаны на GNU MathProg.
  • Параметр -o сообщает glpsol, что выходные данные необходимо переслать в файл giapetto.sol.

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

Листинг 2. Выходные данные glpsol
ceron@curly  ~  $ glpsol  -m  giapetto.mod  -o  giapetto.sol 
Reading  model  section  from  giapetto.real.mod... 
19 lines were read 
Generating z... 
Generating Finishing... 
Generating Carpentry... 
Generating Demand... 
Model has been successfully generated 
lpx_simplex: original LP has 4 rows, 2 columns, 7 non-zeros 
lpx_simplex: presolved LP has 2 rows, 2 columns, 4 non-zeros 
lpx_adv_basis: size of triangular part = 2 
* 0: objval = 0.000000000e+00 infeas = 0.000000000e+00 (0)
* 2: objval = 1.400000000e+02 infeas = 0.000000000e+00 (0) 
OPTIMAL SOLUTION FOUND
Time used: 0.0 secs 
Memory used: 0.1M (151326 bytes) 
lpx_print_sol: writing LP problem solution to `giapetto.sol'...

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

Отлично, но каковы действительные оптимальные значения для переменных решения? Они приведены в файле giapetto.sol:

Листинг 3. Решение задачи Giapetto: giapetto.sol
Problem:    giapetto
Rows:       4
Columns:    2
Non-zeros:  7
Status:     OPTIMAL
Objective:  z = 180 (MAXimum)
                           
No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 z            B            180
2 Finishing    NU           100                         100             1
3 Carpentry    NU            80                          80             1
4 Demand       B             20                          40
                                
No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 x1           B             20             0
2 x2           B             60             0
                                
Karush-Kuhn-Tucker optimality conditions:
                                
KKT.PE: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
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. = 0.00e+00 on column 0
max.rel.err. = 0.00e+00 on column 0
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

Решение разделено на три секции:

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

Мы видим, что для данной конкретной задачи решение OPTIMAL (оптимальное), а максимальная прибыль Giapetto в неделю составляет $180.

Статус ограничения по часам на отделку обозначен как NU (столбец St (статус)). NU значит, что имеется не базисная переменная на верхней границе для этого ограничения. Если Вы знакомы с теорией Исследования Операций постройте симплексную таблицу и проверьте ее. Если нет, ниже приведено краткое практическое объяснение.

Достижение значения ограничения верхней или нижней границы называется граничным условием. Граничное условие препятствует достижению функцией цели большего значения. Представьте его себе как регулятор громкости, к примеру, повернуть который дальше невозможно. Когда это происходит, glpsol показывает состояние ограничения как NU или NL (для верхней и нижней границ соответственно), а также показывает крайнее (marginal) значение, также называемое скрытой ценой (shadow price). Скрытая цена это величина, на которую изменилась бы функция цели, если бы ограничение уменьшили на одну единицу (если бы регулятор громкости можно было повернуть еще немножко). Обратите внимание, что повышение зависит от того, является ли целью минимизация или максимизация. Например, в задаче Giapetto, которая является задачей на максимизацию, крайнее значение равно 1, то есть значение функции цели увеличится на 1, если на 1 час увеличится количество часов на отделку (мы знаем, что речь идет об увеличении на 1 час, а не об уменьшении, поскольку для ограничения количества часов на отделку установлена верхняя граница).

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

Спрос на солдатиков, однако, не ограничен, поэтому его состояние обозначено B, а его изменение не повлечет за собой изменение оптимального значения функции цели.

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

Наконец, значения переменных решения будут выведены в отчете glpsol: x1 = 20 и x2 = 60. Данные значения сообщают Giapetto, что для получения максимальной еженедельной прибыли необходимо производить 20 солдатиков и 60 паровозиков.

Задача Giapetto очень мала. Возможно, Вас интересует вопрос, придется ли Вам объявлять каждую переменную и каждое ограничение по отдельности в задаче с гораздо большим количеством переменных решения и ограничений. А как быть, если Вам хотелось бы ввести в задачу такие данные, как, например, цена реализации одного солдатика? Нужно ли Вам вносить изменения всюду, где встречается данное значение? В следующем разделе рассмотрены все эти вопросы.


Использование разделов Модель и Данные в задаче Giapetto

Модель MathProg обычно имеет разделы Модель и Данные, иногда в двух разных файлах. Таким образом, glpsol может легко решить задачу по одной модели, но с разными наборами данных. Приведенный ниже листинг содержит описание задачи Giapetto гораздо более изящным способом:

Листинг 4. Задача Giapetto с разделами Модель и Данные: giapetto2.mod
1      #
2      # Giapetto's problem
3      #
4      # This finds the optimal solution for maximizing Giapetto's profit
5      #
6
7      /* Set of toys */
8      set TOY;
9
10      /* Parameters */
11      param Finishing_hours {i in TOY};
12      param Carpentry_hours {i in TOY};
13      param Demand_toys     {i in TOY};
14      param Profit_toys     {i in TOY};
15
16      /* Decision variables */
17      var x {i in TOY} >=0;
18
19      /* Objective function */
20      maximize z: sum{i in TOY} Profit_toys[i]*x[i];
21
22      /* Constraints */
23      s.t. Fin_hours : sum{i in TOY} Finishing_hours[i]*x[i] <= 100;
24      s.t. Carp_hours : sum{i in TOY} Carpentry_hours[i]*x[i] <= 80;
25      s.t. Dem {i in TOY} : x[i] <= Demand_toys[i];
26
27
28      data;
29      /* data  section */
30
31      set TOY := soldier train;
32
33      param Finishing_hours:=
34      soldier         2
35      train           1;
36
37      param Carpentry_hours:=
38      soldier         1
39      train           1;
40
41      param Demand_toys:=
42      soldier        40
43      train    6.02E+23;
44
45      param Profit_toys:=
46      soldier         3
47      train           2;
48
49      end;

Вместо двух отдельных файлов задача сформулирована в одном файле с разделом Модель (строки 1-27) и разделом Данные (строки 28-49).

В строке 8 определяется SET (множество). SET это совокупность элементов. Например, если я объявляю математически xi, для всех i в {1;2;3;4}, я говорю, что x - массив с целыми значениями от 1 до 4 и, следовательно, мы имеем x1, x2, x3, x4. В этом случае {1;2;3;4} это множество. Итак, в задаче Giapetto есть множество TOY (Игрушки). Где указана фактическая величина этого множества? В разделе данных файла в строке 31, где определено, что множество TOY (Игрушки) содержит soldier(солдатик) и train(паровозик). Множество не является областью числовых значений. Как это возможно? GLPK обеспечивает это довольно интересным способом. Как - вы узнаете буквально через несколько секунд. Теперь обратите внимание на синтаксис объявления SET в разделе данных:

set label := value1 value2 ... valueN ;

Строки 11, 12 и 13 задают параметры задачи. Имеются три параметра: Finishing_hours (Часы на отделку), Carpentry_hours (Часы на плотничные работы), и Demand_toys (Спрос на игрушки). Эти параметры образуют матрицу данных задачи и используются при вычислении ограничений, как Вы увидите позднее.

Рассмотрим параметр Finishing_hours (Часы на отделку). Он определен для множества Игрушки (TOY), поэтому каждый вид игрушки из множества Игрушки (TOY) будет иметь значение параметра Finishing_hours. Помните, что производство одного солдатика требует 2 часов отделочных работ, а паровозика - 1 часа. Посмотрите на строки 33, 34 и 35. Они содержат определение количества часов на отделку для каждого вида игрушек. Практически, эти строки объявляют, что Finishing_hours[soldier]=2 и Finishing_hours[train]=1. Finishing_hours, таким образом, это матрица из 1 строки и 2 столбцов.

Параметры Часы на плотничные работы и Спрос на игрушки объявляются аналогичным образом. Обратите внимание, что спрос на паровозики неограничен, поэтому в качестве верхней границы в строке 43 указано очень большое число.

В строке 17 объявлена переменная x для каждого i в TOY (в конечном счете x[soldier] и x[train]), и ее значение ограничено условием: оно должно быть равно нулю или больше нуля. Имея множества, объявлять переменные довольно просто, не правда ли?

В строке 20 объявлена функция цели - максимизация от z, которая есть общая прибыль для каждого вида игрушек (их всего два: солдатики и паровозики). Например, для солдатиков прибыль равна количеству солдатиков помноженному, на прибыль с продажи каждого солдатика.

Ограничения в строках 23, 24, и 25 объявлены аналогичным способом. Рассмотрим, например, ограничение по часам на отделку: оно складывается как сумма часов на отделку игрушки каждого вида, помноженное на количество произведенных игрушек указанного вида, для двух видов игрушек (паровозики (trains) и солдатики (soldiers)), и оно должно быть меньше или равно 100. Аналогично, суммарные количество часов на плотничные работы должно быть меньше или равно 80.

Ограничение по спросу немного отличается от двух описанных выше, поскольку определено для каждого типа игрушек отдельно, а не как общее значение для всех типов игрушек. Следовательно, нам необходимо два ограничения: одно для паровозиков, другое для солдатиков, как Вы можете видеть в строке 25. Обратите внимание, что индексная переменная ( {i in TOY} ) указывается до :, таким образом сообщая GLPK о необходимости создания ограничения для каждого типа игрушек в TOY (Игрушки), и уравнение, определяющее каждое ограничения, будет построено согласно записи, приведенной после знака :. В данном случае GLPK создаст

Dem[soldier] : x[soldier] <= Demand[soldier]

Dem[train] : x[train] <= Demand[train]

Решение данной модели должно дать те же результаты, что и решение предыдущей модели:

Листинг 5. Решение задачи Giapetto с моделью с разделом данных: giapetto2.sol
Problem:    giapetto2
 Rows:       5
 Columns:    2
 Non-zeros:  8
 Status:     OPTIMAL
 Objective:  z = 180 (MAXimum)
                                
 No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
 ------ ------------ -- ------------- ------------- ------------- -------------
 1 z            B            180
 2 Fin_hours    NU           100                         100             1
 3 Carp_hours   NU            80                          80             1
 4 Dem[soldier] B             20                          40
 5 Dem[train]   B             60                    6.02e+23
                                
 No. Column name  St   Activity     Lower bound   Upper bound    Marginal
 ------ ------------ -- ------------- ------------- ------------- -------------
1 x[soldier]   B             20             0
2 x[train]     B             60             0
                                
 Karush-Kuhn-Tucker optimality conditions:
                               
KKT.PE: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
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. = 0.00e+00 on column 0
max.rel.err. = 0.00e+00 on column 0
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

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


Заключение

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

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


Загрузка

ОписаниеИмяРазмер
Solutions to the problemsolutions.zip1KB

Ресурсы

Научиться

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

  • Создайте Ваш новый проект для 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=193507
ArticleTitle=Набор средств для линейного программирования GNU: Часть 1: Введение в линейную оптимизацию
publish-date=02012007