Введение в линейное программирование
Описание задачи на языке LP: примеры
http://lpsolve.sourceforge.net/5.5/lp-format.htm
http://lpsolve.sourceforge.net/5.5/formulate.htm
Пример 1. Как воспользоваться lp_solve.
Найти минимум ( x1 + 2 x2 ) при ограничениях
x1 >= 1
x2 >= 1
x1 + x2 >= 3
Дополнительное ограничение
x1 - целое число.
Проще всего решить графически на листочке.
Вот как решиться с помощью lp_solve:
1) Включаем Total Commander;
Переходим в свою директорию;
Создаём текстовый файл с описанием задачи: prob1.lp
для этого в Total Commander
нажимаем одновременно Shift F4
и вводим имя файла: prob1.lp
В файле записываем условие задачи:
min: x1 + 2 x2;
x1 >= 1;
x2 >= 1;
x1 + x2 >= 3;
int x1;
2) Запускаем lp_solve.
Для этого набираем в Total Commander cmd
– появляется чёрное окошко,
в котором можно набирать команды.
Чтобы отладить задачу и показать результат на экране,
вводим команду
lp_solve prob1.lp
Получаем ответ:
Value of objective function: 4.00000000
Actual values of the variables:
x1 2
x2 1
Если ошибиться в формате файла, lp_solve напечатает
на экране будет сообщение об ошибке и номер строки.
Попробуйте показать более подробные сведения:
lp_solve -S3 prob1.lp
Как сохранить решение в файл?
lp_solve prob1.lp > prob1.res
или lp_solve -S3 prob1.lp > prob1.res
Каждое ограничение получает своё имя.
Добавлены комментарии: /* comment */
Файл prob2.lp
/* Objective function: maximize */
max: 143 x + 60 y;
/* Constraints */
Cost: +120 x +210 y <= 15000;
Area: +x +y <= 75;
Storage: +110 x +30 y <= 4000;
Сохраняем задание в файл prob2.lp
и набираем
lp_solve -S3 prob2.lp
Value of objective function: 6315.62500000
Actual values of the variables:
x 21.875
y 53.125
Actual values of the constraints:
Cost 13781.2
Area 75
Storage 4000
В этом примере 4 переменных,
из них 2 целые: описываются внизу как int
Файл prob3.lp
min: -x1 - 2 x2 + 0.1 x3 + 3 x4;
r_1: +x1 +x2 <= 5;
r_2: +2 x1 -x2 >= 0;
r_3: -x1 +3 x2 >= 0;
r_4: +x3 +x4 >= 0.5;
x3 >= 1.1;
int x3, x4;
* Запустите lp_solve -S3 prob2.lp
* Удалите требование целочисленности x3 и x4 и запустите lp_solve -S3 prob2.lp
Сравните результаты:
целевая функция,
значения переменных,
левые части неравенств r_1, … r_4.
Пример 4. Использование целых переменных: задача об укладке рюкзака
Крестьянин везёт на продажу арбузы, дыни и яблоки.
Допустимый суммарный вес: 15
Помогите ему собрать груз максимальной стоимости.
Объекты Количество Вес Стоимость
Арбузы 1 - 3 4.3 45
Дыни 0 - 6 2 20
Яблоки 0 - 20 0.4 3
Файл prob4.lp
max: 45 a + 20 d + 3 y;
weight: 4.3 a + 2 d + 0.4 y <= 15;
int a, d, y;
Попробуйте другие значения; посмотрите, как меняется ответ.
Решите задачу без использования линейного программирования.
Смотрите обсуждение: “Задача о рюкзаке”
http://informatics.mccme.ru/moodle/course/view.php?id=9
Пример 5. Бинарные (двоичные) переменные
Бинарные (двоичные) переменные могут иметь значения 0 или 1, "да" или "нет".
Файл prob5.lp
min: -x1 -2 x2 +0.1 x3 +3 x4;
r_1: +x1 +x2 <= 5;
r_2: +2 x1 -x2 >= 0;
r_3: -x1 +3 x2 >= 0;
r_4: +x3 +x4 >= 0.5;
bin x3, x4;
Бинарные переменные удобны для описания,
что элемент входит или не входит в какое-то множество:
игрок участвует или не участвует в матче.
См. задачу о баскетбольной команде.
Пример 6. Неограниченные (свободные) переменные
По усолчанию lp_solve считает все переменные неотрицательными.
Можно описать переменную как “free” --
так мы разрешаем ей быть отрицательной.
Файл prob6.lp
max: x1 + 2x2 - 4x3 -3x4;
x1 + x2 <= 5;
2x1 - x2 >= 0;
-x1 + 3x2 >= 0;
x3 + x4 >= 0.5;
x3 >= 1.1;
x3 <= 10;
free x2, x4;