2020-05-13
145
1 Теоретические сведения
Задачи линейного программирования с целочисленными значениями переменных xj называются задачами целочисленного программирования. Решение задач целочисленного программирования принципиально отличается от решения задач линейного программирования с непрерывными переменными. Непрерывные задачи, записанные в виде симплекс-таблицы, обладают признаками наличия допустимого и полученного оптимального решения. Для задач целочисленного программирования таких признаков нет.
Постановка задачи целочисленного линейного программирования применительно, например, к распределению ресурсов между объектами отличается от постановки задачи линейного программирования с непрерывными переменными дополнительным условием целочисленности переменных:
С = 
®max (min), (1.1)
£ ri, (1.2)
dj £ xj £ Dj, (1.3)
xj ― целые числа, (1.4)
где i =1, 2,…, m; j =1,2,…, n.
Методы решения задач целочисленного программирования основываются, например, на сокращённом переборе вариантов решений по алгоритму ветвей и границ.
Задача целочисленного программирования сначала решается симплекс-методом, как и непрерывная задача линейного программирования. На основе полученного решения составляются дополнительные ограничения для переменной xj, которой в непрерывном решении принимается дробное значение:
xj £[ xj *],
xj ³[ xj *]+1,
где [ xj *] ― целая часть нецелочисленного значения переменной xj * в оптимальном решении. Затем решаются ещё две задачи линейного программирования, в каждую из которых входят исходные и одно из дополнительных ограничений.
Если полученное решение новых задач не удовлетворяет условию целочисленности, то на основе каждой из задач составляются аналогично две новые задачи и т. д. Значение целевой функции одного из полученных целочисленных решений принимается за граничное значение C гр. Решение других задач продолжается до тех пор, пока не будет получено:
1) на одной из ветвей несовместная система ограничений, тогда дальнейшие вычисления по этой ветви прекращаются;
2) на одной из ветвей целочисленное решение, тогда значение целевой функции сравнивается с верхним граничным значением в задаче поиска максимума целевой функции или с нижним граничным значением в задаче поиска минимума целевой функции; если полученное значение хуже, то оно отбрасывается, если лучше ― то принимается как граничное;
3) на одной из ветвей нецелочисленное решение и значение целевой функции хуже граничного, тогда дальнейшие вычисления по этой ветви прекращаются.
Таким образом, для получения целочисленного решения методом ветвей и границ решается большое число задач линейного программирования, причем в каждом очередном ветвлении число дополнительных ограничений для переменных увеличивается на единицу. Оптимальное целочисленное решение выбирается в результате сравнения всех допустимых целочисленных решений.
Например, требуется решить задачу целочисленного программирования:
C =7 x 1+3 x 2®max,
5 x 1+2 x 2£20,
8 x 1+4 x 2£38,
x 1, x 2³0,
x 1, x 2 ― целые числа.
Схема решения методом ветвей и границ представлена на рисунке 1.1.
 |
Рисунок 1.1 ― Схема решения задачи
Графическое решение задачи 1 симплекс-методом показано на рисунке 1.2. Максимальное значение целевой функции C 1=29,5 достигается при значениях переменных x 1=1, x 2=7,5. Значение переменной x 2 не удовлетворяет условию целочисленности.
 |
Рисунок 1.2 ― Графическое решение задачи 1
На основе полученных результатов решения задачи 1 составляются дополнительные ограничения для переменной x 2 и решаются симплекс-методом ещё две задачи.
Задача 2
C =7 x 1+3 x 2®max;
5 x 1+2 x 2£20;
8 x 1+4 x 2£38;
x 1³0, 0£ x 2£7.
Задача 3
C =7 x 1+3 x 2®max;
5 x 1+2 x 2£20;
8 x 1+4 x 2£38;
x 1³0, x 2³8.
Графическое решение задач 2 и 3 симплекс-методом показано на рисунке 1.3. Получены целочисленные значения переменной x 2 и нецелочисленные значения переменной x 1.
 |
Рисунок 1.3 ― Графическое решение задач 2 (слева) и 3 (справа)
Теперь дополнительные ограничения принимаются для переменной x 1. Значение целевой функции в задаче 2 превосходит значение целевой функции в задаче 3, поэтому вычисления продолжаются по ветви с задачей 2 (см. рисунок 1.1).
Задача 4
C =7 x 1+3 x 2®max;
5 x 1+2 x 2£20;
8 x 1+4 x 2£38;
0£ x 1£1, 0£ x 2£7.
Задача 5
C =7 x 1+3 x 2®max;
5 x 1+2 x 2£20;
8 x 1+4 x 2£38;
x 1³2, 0£ x 2£7.
Графическое решение задач 4 и 5 симплекс-методом показано на рисунке 1.4. Получены целочисленные значения переменных и вычисления по ветвям с задачами 4 и 5 прекращаются. Наибольшее значение целевой функции, полученное при решении задачи 5, принимается за граничное значение: C гр= C 5=29.
 |
Рисунок 1.4 ― Графическое решение задач 4 (слева) и 5 (справа)
Значение целевой функции в задаче 3 превосходит граничное значение, поэтому вычисления продолжаются по ветви с задачей 3 (см. рисунок 1.1).
Задача 6
C =7 x 1+3 x 2®max;
5 x 1+2 x 2£20;
8 x 1+4 x 2£38;
x 1=0, x 2³8.
Задача 7
C =7 x 1+3 x 2®max;
5 x 1+2 x 2£20;
8 x 1+4 x 2£38;
x 1³1, x 2³8.
Графическое решение задач 6 и 7 симплекс-методом показано на рисунке 1.5. Получены целочисленные значения переменных в задаче 6. Область допустимых решений для ограничений в задаче 7 отсутствует и задача не имеет решения. Вычисления по ветвям с задачами 6 и 7 прекращаются.
 |  |
Рисунок 1.5 ― Графическое решение задач 6 (слева) и 7 (справа)
Результаты решения задач сведены в таблицу 1.1.
Таблица 1.1 ― Результаты решения задачи оптимизации
| Номер задачи | x 1 | x 2 | C |
| 1 | 1 | 7,5 | 29,5 |
| 2 | 1,2 | 7 | 29,4 |
| 3 | 0,75 | 8 | 29,25 |
| 4 | 1 | 7 | 28 |
| 5 | 2 | 5 | 29 |
| 6 | 0 | 9 | 27 |
| 7 | 1 | 8 | Нет решения |
Оптимальным принимается решение задачи 5, которое по значениям переменных дальше от непрерывного решения, чем в задаче 4.
Задачи ЦП решаются с использованием функции intlinprog в Matlab, начиная с версии 2014 г. [1].
2 Задание и методические указания
Диагностическим центром оказывается четыре вида платных услуг пациентам (таблицы 2.1, 2.2). Планируемое количество xj услуг вида j (число пациентов, которым оказывается услуга вида j) не менее dj. Вклад услуги вида j в прибыль диагностического центра составляет cj. Оказание услуг обеспечивается двумя видами ресурсов. Для оказания услуги вида j необходимо rij единиц ресурса вида i. Количество ресурсов вида i ограничено значением ri. Требуется оптимизировать количество услуг по критерию максимальной прибыли.
Таблица 2.1 ― Планируемые показатели услуг
| Вид услуги, j | Планируемое минимальное количество услуг, dj | Прибыль от услуги, cj | Располагаемые ресурсы, ri | Затраты ресурсов на одну услугу вида j, rij | ||
| Фонд рабочего времени, r 1 | Фонд оплаты труда, r 2 | Трудоёмкость услуги, r 1 j | Оплата труда специалистов за услугу, r 2 j | |||
| Число условных единиц | ||||||
| 1 | d 1 | c 1 | 45744 | 35283 | 470 | 459 |
| 2 | d 2 | c 2 | 363 | 338 | ||
| 3 | d 3 | c 3 | 121 | 140 | ||
| 4 | d 4 | c 4 | 98 | 90 | ||
Таблица 2.2 ― Варианты задания
| Вариант | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| c 1 | 347 | 348 | 349 | 350 | 351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 |
| c 2 | 435 | 434 | 433 | 432 | 431 | 430 | 429 | 428 | 427 | 426 | 425 | 424 | 423 | 422 | 421 | 420 |
| c 3 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 |
| c 4 | 49 | 48 | 47 | 46 | 45 | 44 | 43 | 42 | 41 | 40 | 39 | 38 | 37 | 36 | 35 | 34 |
| Значения d 1, d 2,, d 3, d 4 выбирать самостоятельно. | ||||||||||||||||
Методические указания по выполнению практической работы:
а) изучить лекции по математическому программированию;
б) сформулировать ответы на контрольные вопросы;
в) изучить рекомендуемую литературу по теме занятия;
г) выполнить задание:
1) выполнить формальную постановку задачи целочисленного линейного программирования, содержащую критерий оптимизации с ограничениями и граничными условиями;
2) представить описание синтаксиса функции intlinprog в табличной форме с комментариями;
3) обосновать выбор варианта синтаксиса функции intlinprog для решения поставленной задачи;
4) составить программу решения задачи оптимизации с использованием функции intlinprog и графического интерфейса пользователя Matlab;
5) решить задачу для исходных данных, указанных в таблицах 2.1 и 2.2;
6) результаты решения задачи представить в табличной форме (таблица 2.3).
д) представить отчёт о работе в электронном виде преподавателю на очередном практическом занятии, ответить на контрольные вопросы.
Примечание ― В случае отсутствия версии Matlab с функцией intlinprog составить алгоритм и программу Matlab решения задачи методом ветвей и границ.
Таблица 2.3 ― Рекомендуемая форма представления результатов оптимизации количества диагностических услуг
| Вид услуги, j | Количество услуг: | Ограничения: | Трудоёмкость: | Оплата труда: | Прибыль: | |||||||||
| минимальное, dj | оптимальное | фонд рабочего времени, r 1 | фонд оплаты труда, r 2 | одной услуги, r 1 j | минимального количества услуг, r 1П | оптимального количества услуг, r 1О | одной услуги, r 2 j | минимального количества услуг, r 2П | оптимального количества услуг, r 2О | от одной услуги, cj | от минимального количества услуг, cj П | от оптимального количества услуг, cj О | ||
| Число условных единиц | ||||||||||||||
| 1 | d 1 |
|
|
| c 1 | |||||||||
| 2 | d 2 |
| c 2 | |||||||||||
| 3 | d 3 |
| c 3 | |||||||||||
| 4 | d 4 |
| c 4 | |||||||||||
|
| å= | å= |
| å= | å= | å= | å= | |||||||
Интерфейсом пользователя предусматривается импортирование в рабочее пространство Matlab таблицы исходных данных (таблица 2.1) из архива по задаваемому адресу или ввод исходных данных в интерактивном режиме, ввод задания в форме, предусматриваемой синтаксисом функции intlinprog, представление результатов оптимизации в форме, предусматриваемой синтаксисом функции intlinprog, экспорт результатов оптимизации в архив по задаваемому адресу.
Отчёт о работе должен содержать титульный лист, задание, формальную постановку задачи целочисленного линейного программирования, содержащую критерий оптимизации с ограничениями и граничными условиями, описание синтаксиса функции intlinprog, представление исходных данных и задания в форме, предусматриваемой синтаксисом функции intlinprog, текст программы Matlab с комментариями, результаты оптимизации в форме таблицы 2.3, выводы.
3 Рекомендуемая литература
1 Исаев Г.А. Решение задач целочисленного, смешанного и булева программирования в среде Matlab [Электронный ресурс]. — Электрон., текстовые дан. — Режим доступа: http://www.math.spbu.ru/kio/lectures/intlinprog.pdf. — Загл. с экрана.
Контрольные вопросы и задания
1 Дать формальную постановку задачи целочисленного программирования.
2 Представить графическое решение задачи целочисленного программирования:
E =0,4 x 1+ x 2®max;
11 x 1+4,5 x 2£49,5;
5 x 1+19 x 2£94;
x 1, x 2 ― целые числа.
3 Классифицировать методы решения задачи целочисленного программирования.
4 Пояснить графом методику решения задачи целочисленного программирования методом ветвей и границ.
