Введение в линейное программирование

 

Описание задачи на языке 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          

 

 

Пример 2.  Задача про фермера

Каждое ограничение получает своё имя.

Добавлены комментарии:  /*  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

 

 

Пример 3. Целые переменные

В этом примере 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;