Методика решения задачи целочисленного линейного программирования методом Р. Гомори

УДК 519.86

ББК 65.23

Л 12

 

 

Рекомендовано к изданию методической комиссией экономического факультета (протокол № 3 от _25 ноября 2010 г.)

 

Составитель: доцент Шатова В.С.

 

 

Рецензент: доцент кафедры экономики аграрного производства Ханова И.М.

 

 

Ответственный за выпуск:

зав.кафедрой статистики и информационных систем в экономике

д.э.н., профессор Рафикова Н.Т.

 

г. Уфа, БГАУ, кафедра статистики и информационных систем в экономике

 

 

ОГЛАВЛЕНИЕ

 

Введение

1 Цель и задачи………………………………………………………….. 5

2 Методика решения задачи целочисленного линейного

программирования методом Р.Гомори ……………………... 6

2.1 Числовая задача…………………………..………………………...6

2.2 Последовательность решения задачи……………………………6

2.2.1 Построение экономико-математической модели задачи …6

2.2.2 Подготовка задачи к решению симплексным методом… …7

2.2.3 Решение задачи симплексным методом………………………8

2.2.4 Экономический смысл решения…………………………..…17

3 Вопросы для самоконтроля…… …………………………..…….…18

Библиографический список……………………………………………… 19

 

 

ВВЕДЕНИЕ

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

Для решения задач ЦЛП разработаны специальные методы решения, которые можно разделить на три основные группы:

- методы отсечения;

- комбинаторные методы;

- методы ветвей и границ.

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

1) оно должно быть линейным;

2) должно отсекать найденный оптимальный нецелочисленный план;

3) не должно отсекать ни одного целочисленного плана.

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

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

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

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

1. Симплексным методом (прямым или М-методом) решить задачу линейного программирования. Если все компоненты оптимального плана целые, то он является оптимальным планом и для задачи ЦЛП. Если среди компонент оптимального плана есть нецелые, то перейти к п.2.

2. Среди нецелых компонент выбрать компоненту с наибольшей дробной частью, и по соответствующему уравнению системы, содержащей нецелочисленный план, сформировать правильное отсечение.

3. Неравенство правильного отсечения дополнительной неотрицательной целочисленной переменной преобразовать в эквивалентное уравнение и включить его в систему уравнений.

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

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

 

ЦЕЛЬ И ЗАДАЧИ

Цель: Освоить методику решения задач целочисленного линейного программирования.

Задачи: 1 Уяснить формулировку задач, относящихся к классу задач целочисленного линейного программирования.

2 Освоить алгоритм Р.Гомори решения задач целочисленного линейного программирования.

3 Решить задачу целочисленного линейного программирования методом Р.Гомори.

4 Сформулировать краткие выводы по результатам решения задачи.

 

Программное обеспечение: пакет экономических расчетов PER.

 

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

Числовая задача

Для приобретения оборудования по сортировке зерна выделено 34 млн руб. Оборудование должно быть размещено на площади, не превышающей 60м². Заказывается оборудование двух типов: А и В, характеристика которых дана в таблице 1.

 

Таблица 1 – Характеристика оборудования

 

Показатели	Тип оборудования
А	В
Занимаемая площадь, м2
Стоимость 1 машины, млн руб.
Производительность в смену, т

 

Составить оптимальный план приобретения оборудования, обеспечивающий максимум обшей производительности. Оборудования типа В приобретается не более 8 штук.