_s/λ₁]=—l и [a_s/λ₂]=—l. Столбец

     α₀ изменяется следующим образом:

         

     Следовательно, чем меньше λ, тем сильнее лексикографически  уменьшится

     нулевой столбец. Значение λ следует выбирать так, чтобы, во-первых,

     ведущий элемент стал равным —1 и, во-вторых, чтобы λ давало максимальное

     уменьшение  столбцу α₀. Правило формулируется следующим образом.

     Шаг 0. Пусть строка с номером v является производящей.

     Шаг 1. Пусть α_s, — лексикографически минимальный столбец среди

     столбцов  с α_vj< 0.

     Шаг 2. Для каждого с α_vj< 0 , пусть μ_i

     —наибольшее целое, такое ,что α_s<α_j/μ

     _j

     Шаг 3. Пусть [μ_j=-a_vj/λ_j]. Тогда

         

     Шаг 4. Положить λ = max λ_j  для а_vj < 0.

     Правило выбора λ, описанное выше, позволяет  сделать ведущий элемент

     равным  —1, при этом будет сохраняться  двойственная допустимость таблицы и в

     то  же время нулевой столбец будет  максимально лексикографически  уменьшаться.

     Следует заметить, что отсечение Гомори не является самым «сильным» возможным

     неравенством. Оно также может быть «сильнее»  или «слабее» самого

     производящего неравенства. Например, пусть производящей строкой будет

     X= -4-3 (-x₁) – 5 (-x₂)                                             (12)

     Если  использовать λ=2, то получим отсечение

     S= -2-2 (-x₁) – 3 (-x₂)≥0                                           (13)

     Для λ=3 имеем

     S= -2-1 (-x₁) – 2 (-x₂)≥0                                            (14)

     Для λ=4

     S=-1-1 (-x₁)-2 (-x₂)≥0

     (15)

     Как видно, неравенство (14) сильнее, чем (12), (12) сильнее, чем (13), а (13)

     сильнее, чем (15).

     Другое  замечание касается того, что если величина λ, получаемая указанным

     выше  способом, может быть увеличена так, чтобы [a₀/λ] и [a

     _j/λ] (а_j > 0) оставались без изменения, то отсечение

     Гомори  можно усилить, несмотря на то, что  нулевой столбец -уменьшится на ту же

     величину.

     Выпишем производящую строку

         

     Чем больше величина λ, тем меньше абсолютная величина коэффициентов

     отсечения. Естественно, что мы хотели бы иметь  абсолютную величину [a₀

     /λ]  большой, а абсолютные величины [a_j/λ] — малыми. Если

     значение  λ (полученное по приведенному выше правилу) может быть увеличено

     так, чтобы значения [a_j/λ [] и [a₀/λ] не

     изменялись, то используется большее значение для  λ. Тем самым по

     возможности уменьшится абсолютная величина [a_j/λ] для некоторых

     j, и отсечение станет сильнее.

     Например, пусть целевая функция имеет  вид

     X₀= - 20 – x₁- 2x₂ – 3x₂ – x₄ ,

     И производящая строка

     X= -20+ (-7) (-x₁)+ (-8) (-x₂)+ (-15) (-x₃)+18 (-x₄).

     Используя описанную выше процедуру выбора λ, получим λ = 7.

     Соответствующее отсечение

     s = -3 + x₁ + 2x₂ + Зx₃ — 2x₄≥ 0.

     Если  использовать λ = 9 вместо λ = 7, получим  отсечение

     s* = -3 + x₁ + x₂ + 2x₃ — 2x₄ ≥ О,

     являющееся  более сильным .

     Интересная  особенность полностью целочисленного алгоритма состоит в том, что  для

     его использования не обязательно требовать  целочисленности всех а_ij.

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

     максимизировать

         

     при условиях

     x_n+i= a_i0 - ∑a_ijx_j ≥0             (i=1,...,m)

                                               x_j≥0      (j=1,...,n)

     где a ₀₀ и c_j — целые, а_i0 о и а_ij

     могут быть произвольными действительными числами. Таблица 14.1 содержит в

     первых n + 1 строках только целые числа.

         

     Выпишем произвольную производящую строку (опуская  обозначение строки)

         

     Вне зависимости от того, являются ли   a₀ и a_j целыми ли

     действительными, коэффициенты отсечения сегда целые, а ведущий элемент равен

     —1. В результате итерации с таким ведущим элементом первые n+1 строк таблицы

     останутся целочисленными. Заметим, что переменная s — неотрицательная целая. В

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

     чем отличается от описанного выше. Когда в нулевом столбце a_i0

     == 1, . . ., n)становятся неотрицательными  целыми, а остальные элементы  нулевого

     столбца — неотрицательными, то получается оптимальное решение.

     В последних главах были обсуждены  два алгоритма целочисленного

     программирования, первый из которых называется циклическим алгоритмом (λ

     = 1), а второй — полностью целочисленным (λ > 1).

     Задача  о рюкзаке

     Контейнер оборудован m отсеками вместимостью

     для перевозки n видов продукции 

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

     количестве 0, 1, 2, ... единиц. Пусть 

     - расход i-го отсека для перевозки  единицы j-ой продукции. Обозначим  через 

     полезность  единицы j-ой продукции. Требуется найти  план

     перевозки, при котором максимизируется  общая полезность рейса.

     Модель  задачи примет вид:

         

     при ограничениях на вместимости отсеков

         

     условии неотрицательности

         

     условии целочисленности

          - целые .

     Когда для перевозки имеется один отсек  и каждый вид продукции может  быть взят

     или нет, то модель задачи принимает вид:

         

         

          .

          Задача о назначении

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

     полезность  , связанная с

     выполнением i-м исполнителем j-й работы

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

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

     одну  работу и за каждой работой должне быть закреплен только один исполнитель.

     Математическая  модель задачи примет вид:

         

     Каждый  исполнитель назначается только на одну работу:

         

     На  каждую работу назначается только один исполнитель:

         

     Условия неотрицательности и целочисленности

          , .

          Задача коммивояжера

     Коммивояжер должен посетить один, и только один, раз каждый из n городов и

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

     пройденного пути.

     Математическая  модель задачи:

         

         

         

     Условия неотрицательности и целочисленности

          , .

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

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

     замкнутую ломаную, без пересечений в городах-точках.

                                    

                            Заключение.                              

     В данной работе была рассмотрена сущность целочисленного программирования.

     Затронуты специальные методы решения целочисленных  задач. Такие задачи

     возникают при моделировании разнообразных  производственно-экономических,

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

     математики  может быть сформулирован как  целочисленные экстремальные задачи.

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

     разнообразных ситуаций , возникающих в экономике, технике, военном деле и

     других  областях. Эти задачи интересны и  с математической точки зрения. С

     появлением  ЭВМ, ростом их производительности повысился  интерес к задачам

     такого  типа и к математике в целом.