Методы условной оптимизации: Рекомендации к выполнению лабораторных и практических работ. Шипилов С.А. - 23 стр.

  2. СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

                        2.1. Целочисленная задача ЛП

      Задачи оптимизации, в результате решения которых искомые переменные
должны быть целыми числами, называются задачами целочисленного програм-
мирования. В том случае, когда ограничения и целевая функция представляют
собой линейные зависимости, задачу называют целочисленной задачей ЛП. Ог-
раничимся рассмотрением последней задачи.
      Значительная часть экономических задач ЛП требует целочисленного
решения, например, распределение производственных заданий между предпри-
ятиями, раскрой материалов, распределение транспорта по рейсам, а также
производство неделимой продукции. Если единица составляет малую часть все-
го объема производства, то оптимальное решение находят обычным симплекс-
ным методом, округляя его до целых единиц, исходя из смысла задачи. В про-
тивном случае округление может привести к решению, далекому от оптималь-
ного целочисленного решения или вообще недопустимому.
      Для решения целочисленных задач ЛП разработаны специальные методы:
         • метод сечения Гомори [1, 5, 9], в основе которого лежит описанный
           выше симплексный метод;
         • метод ветвей и границ [5].
      Рассмотрим решение задачи целочисленного ЛП с помощью табличного
процессора Excel.
      Пример
      Пусть в рассмотренном выше примере решения задачи распределения
ресурсов, изготавливаемые виды продукции P1 и P2 являются неделимыми (на-
пример, предметы мебели- полки, стулья). Простое округление, полученного
ранее решения, т.е. P1 =3,91≈ 4 и P2 =1,74≈ 2 как легко убедиться из рис. 1 при-
водит к выходу за пределы ОДР.
      Для решения поставленной задачи перейдем к исходному листу рабочей
книги приведенному на рис.2 и выберем команду СервисПоиск решения. В
открывшемся диалоговом окне Поиск решения необходимо добавить еще од-
но ограничение целочисленности для ячеек, содержащих искомое количество
производимой продукции. Для этого нажимаем кнопку Добавить и в диалого-
вом окне Добавление ограничения (рис.10) указываем, что $B$3:$C$3 –
целые (в том же выпадающем списке, откуда выбирается символ для ограни-
чения).




             Рис.10. Диалоговое окно Добавление ограничения

                                                                             23