ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ В ДЕРЕВООБРАБОТКЕ

Общие сведения

При построении математических моделей различных объектов иногда оказывается, что к некоторым переменным следует предъявить дополнительные требования дискретности или цело-численности. С моделями таких задач мы, по существу, уже сталкивались. Так, при рассмотрении задачи формирования производственной программы мебельной фабрики (параграф 3.1) следовало бы потребовать, чтобы значения переменных х,, х2, х3, полученные по результатам решения, были целыми числами, поскольку они означают число изготавливаемых шкафов, столов и стульев. Аналогично при построении математической модели задачи оптимизации режимов рамного пиления древесины (подпараграф 4.1.2) отмечалось, что значения толщины пил и шага их зубьев должны быть выбраны из ряда стандартных значений.

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

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

  • (4.67)
  • (4.68)
  • (4.69)
  • (4.70)
  • (4.71)

х, + х2 —> шах; 4х, + Зх2 < 12;

*2 ^ Ь8;

х, >0; х2 > 0;

х,, х2 — целые.

Опуская условие (4.71), найдем сначала решение задачи (4.67)— (4.70), являющейся обычной задачей линейного программирования. На рис. 4.21 дана ее геометрическая интерпретация. Четырехугольник ОАВС является областью допустимых решений задачи. Прямая У описывается уравнением Х( + х2 = с, где с — некоторая константа. Для всех точек этой прямой значение целевой функции постоянно и равно с. При перемещении прямой в направлении стрелок значение целевой функции возрастает. Очевидно, что оптимальному решению соответствует точка В, являющаяся точкой пересечения прямых АВ и СИ. Из этого условия отыскиваются ее координаты:

(4.72)

Решив систему (4.72), получаем оптимальное решение ЗЛП: х, опт = 1,65;

•*2 опт

А'

Геометрическая интерпретация особенностей задач

Рис. 4.21. Геометрическая интерпретация особенностей задач

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

Для получения решения исходной задачи, содержащей дополнительно условие целочисленное™ (4.71), попробуем сначала округлить решение, полученное выше для ЗЛП (4.67)—(4.70). Имеем Х = 2; х2 = 2. Это точка Е, координаты которой, очевидно, не удовлетворяют даже ограничениям (4.68) и (4.69). Оптимальное решение исходной задачи надо искать среди целочисленных точек, принадлежащих ОДР. Они на рис. 4.21 выделены. Вычислив для каждой из них значение целевой функции, легко убедиться, что оптимальным решением будет точка х, = 2; х2 = 1, для которой значение целевой функции равно 3.

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

Задачи математического программирования, в которых ко всем или к некоторым переменным предъявляют дополнительное требование целочисленности, называют задачами целочисленного программирования. В первом случае говорят о полностью целочисленной задаче, во втором — о частично целочисленной задаче математического программирования. Для задач, в которых переменные должны принимать дискретные, но не целочисленные значения, существует способ сведения их к задачам целочисленного программирования. Часто здесь используют нормирование переменных. Так, значения толщины пил для приведенного выше примера можно задать в десятых долях миллиметра и получить для них целочисленные значения 20; 22; 25 и 32.

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

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