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

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

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

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

1. Решаем сформулированную задачу как задачу ЛП (обозначим ЛП-1), рассматривая все ее переменные как непрерывные. Пусть W₁ - оптимальное значение ее целевой функции. Допустим в оптимальном решении ЛП-1 некоторые целочисленные переменные принимают дробные значения. Тогда оптимальное решение исходной задачи не совпадает с оптимальным решением ЛП-1. В этом случае W₁ - верхняя граница оптимального значения W исходной задачи.

2. Производим ветвление по одной из целочисленных переменных, имеющих дробное значение в оптимальном решении ЛП-1. Выбор переменной, по котором производим ветвление, осуществляется по ряду правил:

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

4. Производим ветвление в вершине 2 или 3, вводя новое ограничение. Выбор вершины (задачи ЛП) для дальнейшего ветвления осуществляется с помощью специальных правил:

• использование наибольшего оптимального значения целевой функции;
• "последним пришел - первым вышел".

5. Процесс ветвления и решения задач ЛП продолжаем до получения целочисленного решения одной из задач ЛП. Значение W в полученной точке представляет собой нижнюю границу оптимального значения ЦФ исходной задачи ЦП. На этом этапе все вершины (задачи ЛП), для которых оптимальное значение W не превосходит полученной нижней границы ("прозондированные" вершины). Вершина является прозондированной в следующих случаях:

• оптимальное решение, соответствующее данной вершине, целочислено;
• задача ЛП не имеет допускаемого решения;
• оптимальное значение W не превосходит текущей нижней границе.

Ветвление происходит до тех пор, пока остается хотя бы одна непрозондированная вершина. Прозондированная вершина с наилучшим W дает оптимальное решение исходной задачи ЦП.

Процесс ветвления и решения рассматриваемой задачи представлен на рис.4.1. Оптимальное решение - W=32,5 млн. руб.; x₁=4; x₂=5.

Метод ветвей и границ можно применять для решения задач нелинейного программирования.

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

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

Знакомство с задачами раскроя начнем с линейного раскроя.

Пример 4.1. Из 50 шт. бревен длиной 6,5 м необходимо изготовить наибольшее число комплектов, в состав каждого из которых входит 2 шт. детали длиной 2 м и 3 шт. детали длиной 1,25 м.

Есть два подхода к решению задач раскроя:

1. Раскрой делает ЭВМ.
1. Лицо принимающее решение (ЛПР) принимает несколько различных вариантов раскроя, а ЭВМ выбирает лучший из них.

Подход 1. Раскрой делает ЭВМ

Постановка задачи.

1. В качестве показателя эффективности целесообразно взять число комплектов K, которое можно получить из заданного числа заготовок. Возможна другая постановка - качестве показателя эффективности взять число заготовок Z, которое необходимо иметь, чтобы получить заданное цисло комплектов.
1. В качестве управляемых переменных задачи следует взять x_A и x_B - соответственно, число деталей А и В, получаемых из одной заготовки; каждая в год.

3. Целевая функция:

или

4. Ограничения:

4.1. По длине заготовки, м:

4.2. По комплектности, шт.:

где

k - число заготовок.

Таблица 4.1.

1. В качестве показателя эффективности целесообразно взять число комплектов K, которое можно получить из заданного числа заготовок. Возможны другие постановки - взять число заготовок Z, которое необходимо иметь, чтобы получить заданное число комплектов или отходы O.
1. В качестве управляемых переменных задачи следует взять:

x₁ - число заготовок, раскраиваемых по 1 варианту;

x₂ - число заготовок, раскраиваемых по 2 варианту;

x₃ - число заготовок, раскраиваемых по 3 варианту;

x₄ - число заготовок, раскраиваемых по 4 варианту.

3. Целевая функция:

или

или

4. Ограничения:

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

x₁ + x₂ + x₃ + x₄ = k,

где

k - число заготовок.

4.2. По комплектности, шт.:

При решении задачи в первой постановке (k=50)

на ЭВМ получен результат, представленный в табл. 4.2.

Таблица 4.2.

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

Подход, при котором выбирается из ряда разработанных ЛПР вариантов раскроя наилучшее их сочетание, имеет широкое применение в практике раскроя не только линейного, но и плоскостного.

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

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

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

где

Данная постановка отличается от задачи распределения ресурсов линейного программирования

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

Выделяют два метода решения задач с булевыми переменными:

1. Метод полного перебора. Алгоритм метода заключается в следующем:

Фирма выпускает три продукта: A, B, C. На производство единицы продукта A требуется затратить 1,1 ч. труда ИТР, 12,3 ч. физического труда и 3,1 кг сырья. Для единицы продукта B соответствующие показатели равны 2,3 ч., 4,2 ч и 2,4 кг, для продукта C - 1,3 ч, 5,1 ч. и 1,2 кг. Ресурсы составляют 120 ч. труда ИТР, 640 ч. физического труда и 450 кг сырья. При оптовых закупках покупателю предоставляются скидки, так что прибыли от продажи продукции изменяются как показано в табл. 2.12. Например, если продается 120 ед. продукта A, то первые 40 ед. приносят по 63,2 руб. прибыли; следующие 60 - по 54,4 руб., а остальные 20 - по 48,3 руб. Сформулируйте задачу линейного программирования, решение которой определяет наиболее доходный производственный план.

Таблица 2.12.

Леспромхоз, имеющий лесопильный и фанерный цеха, столкнулся с проблемой наиболее рационального использования выделенной лесосеки. Чтобы получить 2,5 м³ коммерчески реализуемых комплектов пиломатериалов, необходимо израсходовать 2,5 м³ еловых и 7,5 м³ пихтовой древесины. Для изготовления 100 м² фанеры требуется 5,1 м³ еловых и 10,2 м³ пихтовой древесины. Выделенная лесосека содержит 80 м³ еловых и 180 м³ пихтовой древесины. Согласно условиям поставок, в течении планируемого периода необходимо произвести по крайней мере 10 м³ пиломатериалов и 1200 м² фанеры. Доход с 1 м³ пиломатериалов составляет 80,2 руб., а со 100 м² фанеры - 302,5 руб. Оптимизировать использование лесосеки.

Мебельное предприятие выпускает три вида наборов мебели, книжные полки и тумбу под телевизоры. Характеристики каждого вида продукции приведены в табл. 2.13. При условии получения максимальной прибыли объем товарной пилопродукции должен составить не менее 459,31 тыс. руб. Ситуация со сбытом продукции сложилась следующая. Книжными полками рынок насыщен поэтому торговые организации уменьшили объем договоров до 10 тыс. шт. Тумбы для телевизоров могут быть реализованы в объемах от 4 до 7 тыс. шт., наборы мебели 2 - от 7 до 10 тыс. шт. Спрос на наборы мебели 1 и 3 неограничен и требуется не менее 10 тыс. шт. Предприятие имеет технологическое оборудование, число единиц которого и нормы затрат времени оборудования каждой группы на изготовление единицы каждого вида продукции приведены в табл. 2.13. Предприятие работает в две смены с эффективным временем работы каждой машины в 3945 ч. (коэффициент сменности 1,9). Оптимизировать производственную программу предприятия.

Таблица 2.13.

Таблица 2.14

В леспромхозе производится раскряжевка хлыстов на сортименты. Требуется получить сортименты трех видов - длиной 6, 2,2 и 1,5 м. Длина среднего хлыста 31 м, средний диаметр 0,3 м. План поставки сортиментов, соответственно, 32,4 тыс. м³, 86,3 тыс м³ и 40,3 тыс. м³. Используя карту раскроя хлыстов без учета толщины пропила (табл.2.15) определить оптимальный план раскроя.

Таблица 2.15

Нижний склад производит два вида продукции: обрезную доску и брус. Для изготовления 1 м³ бруса требуется 2,5 м³ сосны или 3,3 м³ ели. Для изготовления 1 м³ доски требуется 3,2 м³ сосны или 3,5 м³ ели. Максимальные суточные запасы сосны - 250 м³, ели - 330 м³. Суточный спрос на брус - 110 м³, на доску - 150 м³ при оптовых ценах за 1 м³ бруса - 241 руб., за 1 м³ доски - 352 руб. Определить оптимальные объемы выпуска бруса и доски.

Лесхоз для кормления животных использует два вида корма. В дневном рационе животного должно содержаться не менее 6 единиц вещества A и 12 единиц B. Какое количество корма надо расходовать ежедневно на одного животного, чтобы затраты были минимальны (по данным табл. 2.16).

Таблица 2.16

Леспромхоз имеет древесину трех видов в количествах: 1 - 1,12 тыс. м³, 2 - 0,52 тыс. м³, 3 - 0,73 тыс. м³, для изготовления изделий A, B, C и D. Нормы расхода древесины в м³ на изготовление единицы каждого изделия и прибыль от реализации единицы изделия даны в табл. 2.17. Определить, сколько изделий каждого вида должно произвести предприятие, чтобы общая прибыль от реализации всех изделий была максимальной?

Производство двух видов лесопродукции должно пройти три операции. Затраты времени на каждой операции на одно изделие, прибыль от реализации одного изделия в табл. 2.18. Сколько изделий каждого вида должно произвести предприятие, чтобы получить максимум прибыли, причем число изделий A должно быть не менее 10, а B - не более 70 единиц.

Таблица 2.19

Предприятию задана программа по изготовлению четырех видов изделий в количествах: вида A - 495, B - 265, C - 378, D - 162. На предприятии имеется три группы станков с различной производительностью. Задается суммарное допустимое время работы за этот период для каждой группы станков: первой - 80 ч., второй - 100 ч., третьей - 150 ч. Нормы времени (в часах) на изготовление одного изделия на каждом станке и данные об издержках (в рублях) на изготовление каждого изделия на станках различных групп приводятся в табл. 2.20. Требуется так распределить изготовление изделий по группам станков, чтобы была обеспечена заданная программа по изготовлению изделий и чтобы общие издержки были минимальны?

Таблица 2.20