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

Размещено на http://www.allbest.ru/

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

1. Постановка и модель целочисленной задачи

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

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

Постановка целочисленной задачи звучит также, как и постановка основной задачи линейного программирования и добавляется только одно условие - целочисленность хj.

Пусть некоторое предприятие имеет n видов производственных ресурсов. Порядковый номер ресурсов - i, т.е. i = 1, 2, …, m. Наличие каждого вида ресурсов известно и обозначается bi. Предположим, что предприятие может производить m видов продукции. Порядковый номер продукции - j, т.е. j = 1, 2, …, n. Необходимо определить какое количество единиц продукции каждого вида надо производить (xj), чтобы получить максимум этой продукции в стоимостном выражении, если известно, что затраты на производство единицы продукции каждого вида ресурса равны aij единиц, а цена реализации - cj. Единицы производимой продукции должны принимать целые значения. Тогда модель задачи будет выглядеть следующим образом:

I) Ж = с1х1 + с2х2 + … + сnхn max.

II) a11х1 + а12х2 + … + а1nхn ? b1,

a21х1 + а22х2 + … + а2nхn ? b2,

………………………………

am1х1 + аm2х2 + … + аmnхn ? bm.

III) хj ? 0 и хj - целые, j = 1, 2, …, n.

Методы решения задач линейного программирования не гарантируют целочисленности решения.

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

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

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

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

Дополнительное ограничение отсекает часть области, содержащую нецелочисленное оптимальное решение.

Вновь полученную задачу решают методом линейного программирования. Процесс построения сечений и решения задачи повторяется до получения целочисленного оптимального решения.

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

Предположим, что на каком-то шаге мы получили таблицу с оптимальным вариантом решения задачи (таблица 2).

Таблица 2 - Оптимальный вариант для исходной задачи без ограничения по целочисленности

Предположим, что в полученном оптимальном варианте среди переменных хj есть дробное значение. Составим дополнительное ограничение по целочисленности этой переменной.

Обозначим через ij целое число, не превосходящие коэффициенты и свободный член в строке, в которой находится переменная хj с дробным значением.

Для каждого коэффициента и свободного члена составим разность бij = aij - вij (если само aij целое, то вij = aij и бij =0).

Очевидно, что все значения бij ? 0.

Возьмем бij в качестве коэффициентов нового дополнительного ограничения:

бi1x1 + бi2у1 + … + бinxn ? бi

Запишем это дополнительное ограничение в виде равенства введя дополнительную переменную si ? 0:

si = бi1x1 + бi2x2 + … + бinxn - бi.

Далее составляется расширенная симплекс-таблица, т.е. в таблицу с оптимальным вариантом вводится дополнительная строка, в которой записывается дополнительное ограничение (таблица 3), после чего вычисления продолжаются.

Таблица 3 - Вариант решения для исходной задачи с добавленным ограничением

Далее задача решается симплекс-методом с получением допустимого и оптимального варианта. В случае необходимости в таблицу вводятся еще ограничения.

Замечание: при работе с линейными целочисленными задачами оптимизации необходимо иметь ввиду: 1) условие целочисленности распространяется только на основные переменные хj, а дополнительные переменные (остаток ресурсов) и целевая функция (выход продукции в стоимостном выражении) не обязательно должны принимать целые значения; 2) условие целочисленности может только «ухудшить» результат решения задачи; 3) существует ряд задач, которые без дополнительных ограничений сразу являются целочисленными или вовсе не могут быть решены с условием целочисленности, но из постановки задачи это сложно увидеть заранее.

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

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

Задача о ранце. Общий вес ранца заранее ограничен. Необходимо определить какие предметы положить в ранец, чтобы общая полезность отобранных предметов была максимальна, если вес каждого предмета известен.

Примем, что х1, х2, …, хn - предметы, с1, с2, …, сn - ценность каждого предмета, а1, а2, …, аn - масса каждого предмета (или какой-то характерный важный размер). Ранец может выдержать общую массу не более b. Если предмет кладется в ранец, то ему присваивается значение, равное единице, если нет, то равное нулю. В итоге получим линейную целочисленную задачу оптимизации:

I)

II)

III) хj = {0,1}, j = 1, 2.

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

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

Пусть х1 и х2 - количество приобретаемых машин типа А и типа Б соответственно, тогда модель задачи будет выглядеть следующим образом:

I) Ж = 7х1 + 3х2 max.

II) 5х1 + 2х2 ? 20,

8х1 + 4х2 ? 38.

III) хj ? 0 и хj - целые, j = 1, 2.

Решая задачу в MS Excel без ограничения целочисленности, получим, что Z = 29,5, при х1 = 1 и х2 = 7,5.

Если же изначально при добавлении ограничений в соответствующем диалоговом окне в MS Excel дополнительно еще раз выбрать ячейки, соответствующие переменным величинам, и задать их целыми числами, то после активизации поиска решения ответ будет выглядеть так: Z = 29, при х1 = 2 и х2 = 5. Таким образом, приобретение двух машин типа А и пяти машин типа Б обеспечивает максимум производительности участка, равный 29 тыс. единиц продукции в смену. Заметим, что если бы в качестве пана был выбран вариант, получаемый в результате простого округления первоначального решения (т.е. х1 = 1 и х2 = 7), то суммарная производительность оказалась бы равной всего 28 тыс. единиц продукции.

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

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

- задача о назначениях. С ее помощью можно получить ответ на вопросы типа: как распределить рабочих по станкам, чтобы общая выработка была наибольшей или затраты на заработную плату наименьшими; как наилучшим образом распределить экипажи самолетов; как назначить людей на различные должности и т.д. Математически такие задачи относятся к транспортным задачам, с той особенностью, что в них объемы наличных и требующихся ресурсов для выполнения каждой работы равны единице (aj = bi = 1), а все переменные xij либо равны единице, если i-ый работник назначен на j-ую работу, либо равны нулю в других случаях. Исходные данные задачи о назначениях группируются в таблице, которая называется матрицей оценок, а результаты - в матрице назначений. При решении задачи о назначениях используют алгоритмы и методы решения транспортных задач;

- задача о коммивояжере. Она относится к задачам предыдущего вида и может быть сформулирована следующим образом: имеется n городов, пронумерованных числами от 1 до n. Коммивояжер, выезжая из города 1, должен побывать в каждом городе ровно один раз и вернуться в исходный пункт при этом известны расстояния cij между городами (i = 1,n, j = 1,n, i ? j). Требуется найти самый короткий маршрут.

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

Размещено на Allbest.ru