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 |
| 7,5 | 29,5 | ||
| 1,2 | 29,4 | ||
| 0,75 | 29,25 | ||
| Нет решения |
Оптимальным принимается решение задачи 5, которое по значениям переменных дальше от непрерывного решения, чем в задаче 4.
Задачи ЦП решаются с использованием функции intlinprog в Matlab, начиная с версии 2014 г. [1].
2 Задание и методические указания
Медицинским центром планируется закупать оборудование для оказания платных услуг пациентам (таблицы 2.1, 2.2). Количество закупаемого оборудования xj вида j не менее dj. На закупку оборудования выделяется не более r 1 финансовых средств. Стоимость единицы оборудования составляют r 1 j. Среднее число пациентов в очереди за услугой составляет mj. Ежедневное количество оказываемых услуг на единице оборудования составляет sj. Средний неудовлетворённый спрос на услугу не должен превышать r 2 j. Вклад услуги в прибыль медицинского центра составляет cj. Требуется оптимизировать количество закупаемого оборудования по критерию максимальной прибыли от услуг.
Таблица 2.1 ― Исходные данные для планирования закупок оборудования
| Вид оборудования, j | Минимальное количество оборудования, dj | Среднее число пациентов в очереди, mj | Прибыль от услуги, cj | Ограничения | Затраты, rij З Затраты | ||
| Финансовые средства, r 1 | Неудовлетворённый спрос на услугу, r 2 j | Стоимость оборудования, r 1 j | Количество услуг на единице оборудовании, sj | ||||
| Число условных единиц | |||||||
| 1 Рентгеновский аппарат | d 1 | c 1 | 64´106 | 6,04´106 | |||
| 2 Ультразвуковой сканер | d 2 | c 2 | 1,65´106 | ||||
| 3 Эхокардиограф | d 3 | c 3 | 3,41´106 | ||||
| 4 Компьютерный томограф | d 4 | c 4 | 27,3´106 | ||||
| 5 Гастрофиброскоп | d 5 | c 5 | 0,26´106 | ||||
| Примечание ― Неудовлетворённый спрос услуги вычисляется по формуле r 2 j = mj – sjxj, где xj ― число единиц оборудования. |
Таблица 2.2 ― Варианты задания
| Вариант | ||||||||||||||||
| c 1 | ||||||||||||||||
| c 2 | ||||||||||||||||
| c 3 | ||||||||||||||||
| c 4 | ||||||||||||||||
| c 5 | ||||||||||||||||
| Значения d 1, d 2,, d 3, d 4, d 5 выбирать самостоятельно. |
Методические указания по выполнению практической работы:
а) изучить лекции по математическому программированию;
б) сформулировать ответы на контрольные вопросы;
в) изучить рекомендуемую литературу по теме занятия;
г) выполнить задание:
1) выполнить формальную постановку задачи целочисленного линейного программирования, содержащую критерий оптимизации с ограничениями и граничными условиями;
2) представить описание синтаксиса функции intlinprog в табличной форме с комментариями;
3) обосновать выбор варианта синтаксиса функции intlinprog для решения поставленной задачи;
4) составить программу решения задачи оптимизации с использованием функции intlinprog и графического интерфейса пользователя Matlab;
5) решить задачу для исходных данных, указанных в таблицах 2.1 и 2.2;
6) результаты решения задачи представить в табличной форме (таблица 2.3).
д) представить отчёт о работе в электронном виде преподавателю на очередном практическом занятии, ответить на контрольные вопросы.
Примечание ― В случае отсутствия версии Matlab с функцией intlinprog составить алгоритм и программу Matlab решения задачи методом ветвей и границ.
Таблица 2.3 ― Рекомендуемая форма представления результатов оптимизации количества закупаемого оборудования
| Вид оборудования, j | Количество оборудования: | Ограничения: | Среднее число пациентов в очереди, mj | Количество услуг на единице оборудовании, sj | Неудовлетворённый спрос: | Стоимость оборудования: | Прибыль: | |||||||
| минимальное, dj | оптимальное, xj | финансовые, r 1 | неудовлетворённый спрос, r 2 j | минимальное количество оборудования, r 2 j П | оптимальное количество оборудования, r 2 j О | единицы, r 1 j | минимального количества, r 1 j П | оптимального количества, r 1 j О | от услуги, cj | минимальное количество оборудования, cj П | от оптимальное количество оборудования, cj О | |||
| d 1 | c 1 | |||||||||||||
| d 2 | c 2 | |||||||||||||
| d 3 | c 3 | |||||||||||||
| d 4 | c 4 | |||||||||||||
| d 5 | c 5 | |||||||||||||
| å= | å= | å= | å= |
Интерфейсом пользователя предусматривается импортирование в рабочее пространство Matlab таблицы исходных данных (таблица 2.1) из архива по задаваемому адресу или ввод исходных данных в интерактивном режиме, ввод задания в форме, предусматриваемой синтаксисом функции intlinprog, представление результатов оптимизации в форме, предусматриваемой синтаксисом функции intlinprog, экспорт результатов оптимизации в архив по задаваемому адресу.
Отчёт о работе должен содержать титульный лист, задание, формальную постановку задачи целочисленного линейного программирования, содержащую критерий оптимизации с ограничениями и граничными условиями, описание синтаксиса функции intlinprog, представление исходных данных и задания в форме, предусматриваемой синтаксисом функции intlinprog, текст программы Matlab с комментариями, результаты оптимизации в форме таблицы 2.3, выводы.
3 Рекомендуемая литература
1 Исаев Г.А. Решение задач целочисленного, смешанного и булева программирования в среде Matlab [Электронный ресурс]. — Электрон., текстовые дан. — Режим доступа: https://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 Пояснить графом методику решения задачи целочисленного программирования методом ветвей и границ.