Целочисленное программирование

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

Метод отсекающих плоскостей состоит в построении дополнительных ограничений и применении двойственного симплексного метода. Представление о комбинаторных методах дает широко используемый на практике метод ветвей и границ.

Рассмотрим более подробно один из методов отсекающих плоскостей, известный как метод Гомори. Метод Гомо- ри для линейных задач целочисленного программирования основан на понятии конгруэнтности действительных чисел. Любое действительное число можно представить в виде суммы его целой и дробной частей: х = [х]+{х}, где квадратные скобки означают целую часть, а фигурные – дробную. Например, 7,5 = [7,5] + {7,5} = 7 + 0,5. Неотрицательные числа (для простоты мы будем рассматривать только их) называются конгруэнтными, если равны их дробные части. Если обозначать конгруэнтность чисел символом "=", то, например, ; ; в частности, все целые числа конгруэнтны нулю, поэтому условие целочисленности переменной х можно записать:

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

Пример 3.6. Пусть для приобретения оборудования, размещаемого на производственной площади 38 м2, фирма выделяет 20 млн руб. Имеются единицы оборудования двух типов: типа А стоимостью 5 млн руб., требующее производственную площадь 8 м2 и имеющее производительность 7 тыс. ед. продукции за смену, и типа Б – стоимостью 2 млн руб., занимающее площадь 4 м2 и дающее за смену 3 тыс. ед. продукции. Требуется рассчитать оптимальный вариант приобретения оборудования, обеспечивающий максимум производительности участка

Решение. Сформулируем экономико-математическую модель задачи. Пусть х{, х2 – количество приобретаемых машин типа

А и типа Б соответственно. Тогда целевая функция задачи будет иметь вид

при ограничениях:

Сформулирована задача линейного целочисленного программирования.

Введем дополнительные переменные х3, ж4, с помощью которых исходные неравенства преобразуются в равенства:

из которых следует, что переменные х3, х4 могут принимать только неотрицательные целочисленные значения. Фрагмент симплексной таблицы на последней итерации (без учета целочисленности) приведен в табл. 3.15.

Таблица 3.15

Базисные переменные

План

1

1

0

1

-0,5

7,5

0

1

-2

1,26

29,5

0

0

1

0,25

Отсюда видно, что в оптимальном плане х1 = 1; х2 = 7,5 и максимум целевой функции равен

Для нецелочисленной переменной х2 составляем из приведенной симплексной табл. 3.15 уравнение:

откуда

Так как – целое число, то целой должна быть и правая часть последнего уравнения ("" – символ конгруэнтности):

отсюда можно получить, что

т.е. выражение может быть равно 0,5, или 1,5, или 2,5 и т.д. Следовательно, появляется дополнительное ограничение: , которое путем ввода дополнительной неотрицательной целочисленной переменной х5 преобразуется в равенство, так что система ограничений исходной задачи в каноническом виде содержит три уравнения:

Повторив процесс решения симплексным методом для данной расширенной системы ограничений, получим новый оптимальный план, в котором переменные, входящие в базис, принимают целые значения: . Таким образом, приобретение двух машин типа А и пяти машин типа Б обеспечивает максимум производительности участка, равный 29 тыс. ед. продукции в смену. Заметим, что если бы в качестве плана был выбран вариант, получаемый в результате округления первоначального решения задачи симплексным методом (), то суммарная производительность была бы равна лишь 28 тыс. ед. продукции.

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

Математически такие задачи относятся к тому же типу распределительных задач, что и рассмотренная в параграфе 3.2 транспортная задача, с той особенностью, что в них объемы наличных и требующихся ресурсов для выполнения каждой работы равны единице (), а все переменные либо равны единице, если i-й работник назначен иа j-ю работу, либо равны нулю в других случаях. Исходные данные задачи о назначениях группируются в таблице, которая называется матрицей оценок, а результаты – в матрице назначений.

Задача о назначениях в общем виде может быть сформулирована следующим образом. Имеется п работников, которые могут выполнять п работ, причем использование i-го работника на j-й работе, например, приносит доход сij.

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

Введем переменные:

Задача состоит в том, чтобы найти распределение работников по работам (т.е. найти матрицу назначений), которое максимизирует целевую функцию

(3.22)

при ограничениях

(3.23)

(3.24)

причем равно либо 0, либо 1 (так называемые булевы переменные) для всех

Ограничения (3.23) отражают условие того, что за каждым работником может быть закреплена только одна работа, а ограничения (3.24) означают, что для выполнения каждой работы может быть выделен только один работник.

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

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

Введем переменные:

Требование однократного въезда в города и выезда из них запишется в виде следующих ограничений:

(3.25)

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

(3.26)

Общее число таких ограничений равно (n – 1) • (n – 2), и они, не исключая допустимый маршрут, исключают возможность существования подмаршрутов.

Таким образом, задача о коммивояжере состоит в минимизации целевой функции:

(3.27)

при условиях (3.25), (3.26), где переменные , принимают только неотрицательные целые значения.

К задачам целочисленного программирования приводят также многие оптимальные задачи теории расписаний, в которой рассматриваются методы оптимизации оперативно-календарного планирования. В качестве примера таких задач можно привести задачу определения оптимальной очередности обработки изделий на различных станках или других рабочих местах, задачу составления программы "диспетчер" для управления работой ЭВМ в мультипрограммном режиме и др.

 
< Пред   СОДЕРЖАНИЕ     След >