20

министерство сельского хозяйства российской федерации

Федеральное государственное образовательное учреждение высшего профессионального образования «БАШКИРСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ»

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

ЕН.Ф.01.02 ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ

Лабораторное занятие № 6. Целочисленное линейное программирование

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Направление подготовки дипломированного специалиста

080500 Менеджмент

Специальность 080502 Экономика и управление на предприятии

(в аграрном производстве)

Уфа 2010

УДК 519.86

ББК 65.23

Л 12

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

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

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

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

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

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

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

ОГЛАВЛЕНИЕ

Введение

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

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

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

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

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

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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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