Математическая постановка задачи целочисленного программирования

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

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

Математическая формулировка задачи линейного целочисленного программирования следующая: найти такое решение (план):

.

при котором линейная функция:

принимает максимальное или минимальное значение при ограничениях:

— целые числа, .

Рассмотрим примеры задач целочисленного программирования.

Пример 1. Задача о рюкзаке. Пусть имеется предметов, которые турист хочет уложить в рюкзак, собираясь в поход. Однако известно, что он сможет унести не более кг веса, а рюкзак вмещает дм3 вещей по объему. Веса предметов известны:; их объемы также известны:. С точки зрения туриста, полезность предметов в походе различна, и ее можно выразить в некоторых условных единицах полезности: — это полезность предметов соответственно. Турист хочет положить в рюкзак такой набор вещей, который удовлетворял бы ограничениям по весу и объему и имел бы наибольшую полезность.

Составим математическую модель этой задачи. Обозначим:

.

Требуется определить максимум функции:

.

при ограничениях по весу и объему:

Пример 2. Задача о назначении. Имеется n исполнителей, которые могут выполнять m различных работ. Известна полезность, связанная с выполнением i-м исполнителем j-ой работы,. Необходимо назначить исполнителей на работы так, чтобы добиться максимальной полезности, при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должен быть закреплен только один исполнитель.

Составим математическую модель этой задачи. Обозначим:

.

Требуется определить максимум функции:

.

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

Пример 3. Задача о раскрое материалов.

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

Обозначим — число единиц материала, раскраиваемыхым способом, и — число изготавливаемых комплектов изделий.

Экономико-математическая модель задачи следующая: найти такое решение.

.

при котором функция:

.

принимает максимальное значение и при этом выполнены требования:

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

Методы целочисленной оптимизации можно разделить на три основные группы:

• 1) методы отсечения;
• 2) комбинаторные методы;
• 3) приближенные методы.

Остановимся более подробно на некоторых из этих методов.