Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Модели целочисленного линейного программирования.

Метод Гомори

Цель лабораторного занятия:

Приобретение навыков решения целочисленных задач линейного программирования методом Гомори и с помощью встроенной функции Поиск решения в табличных редакторах Microsoft Excel и OpenOffice.org Calc.

Задачи лабораторного занятия:

1. Нахождение оптимального решения целочисленной задачи ЛП методом Гомори.

2. Нахождение оптимального решения целочисленной задачи ЛП с помощью встроенной функции Поиск решения.

3. Анализ полученных результатов.

4. Оформление отчета.

Содержание

4. Краткие теоретические сведения.

5. Задание.

6. Контрольные вопросы.

Краткие теоретические сведения

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

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

(9)

при ограничениях

, (10)

, (11)

а также дополнительном ограничении

- целые числа (12)

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

 

Метод Гомори

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

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

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

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

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

Далее задача решается с учетом нового ограничения. После этого в случае необходимости добавляется еще одно ограничение и т.д.

 

Алгоритм метода Гомори

1. С помощью симплекс-метода находят решение задачи (9)-(11) без учета требования целочисленности переменных. Если полученное решение целочисленное, то задача (9)-(12) решена. Если задача (9)-(11) неразрешима (т.е. не имеет конечного оптимума или условия ее противоречивы), то и задача (9)-(12) также неразрешима.

2. Если полученное решение нецелочисленное, то составляют дополнительное ограничение для переменной, которая в оптимальном плане задачи (9)-(11) имеет максимальную дробную часть, а в оптимальном плане задачи (9)-(12) должна быть целочисленной. Для составления дополнительного ограничения используется последняя симплекс-таблица. Ограничение имеет вид:

, (13)

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

3. Неравенство (13) заменяют уравнением путем ввода дополнительной переменной и добавляют его к ранее решенной задаче, получают новую задачу. Решают ее симплексным методом, если оптимальный план новой задачи целочисленный, то исходная задача решена. В противном случае составляется новое дополнительное ограничение и т.д., пока не будет получено целочисленное решение задачи.

Задача 9.На приобретение оборудования (станков) для участка цеха выделены 30 т.р. Производственная площадь участка – 70 м2. Имеется возможность закупить станки двух видов: стоимостью 5т.р. и 3т.р. Станок первого вида требует для установки 12 м2 и дает продукции на 8 т.р. в месяц. Станок второго вида требует 6 м2 площади и дает продукции на 2 т.р. в месяц. Определить оптимальный план приобретения оборудования, при котором производительность участка цеха в месяц была бы максимальной.

Решение.

1. Составим математическую модель задачи:

- количество станков первого вида;

- количество станков второго вида;

- целевая функция (производительность участка в месяц в ден.ед.).

Система ограничений:

; .

2. С помощью симплекс-метода найдем решение задачи без учета требования целочисленности переменных. Для этого приведем задачу к каноническому виду, т.е. в системе ограничений введем две дополнительные переменные и :

В качестве базисных переменных можем взять дополнительные переменные и .

Составим симплексную таблицу (таблица 20):

I шаг.

Таблица 20

БП СЧ Оценочное отношение
-8 -2  

 

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

В качестве разрешающего выберем столбец, соответствующий переменной , т.к. ей соответствует наибольший по модулю отрицательный коэффициент (-8).

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

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

Производим пересчет симплекс-таблицы (таблица 21).

II шаг.

Таблица 21

БП СЧ Оценочное отношение
 
 
46  

 

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

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

;

Дополнительное ограничение будет иметь вид:

(фигурные скобки обозначают дробную часть числа).

;

С помощью дополнительной переменной преобразуем данное неравенство в уравнение:

.

и присоединим его к исходной системе ограничений, получим новую задачу. Для ее решения в последнюю симплекс-таблицу исходной задачи добавляем строку, соответствующую введенному ограничению (таблица 22). Находим базисное решение и проверяем его на оптимальность.

Таблица 22

БП СЧ оценка
 
 
  -1  
-5 5/3
 
-12 5/3
-2  

 

План не оптимален (в индексной строке есть отрицательная оценка). Выполним пересчет симплекс-таблицы.

 

Таблица 23

БП СЧ оценка
5/3 1/3 -5/3  
 
-2 -2  
43 2/3 14/3  

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

;

или

Это ограничение добавляем в последнюю симплексную таблицу и решаем новую задачу симплекс-методом.

 

Таблица 24

БП СЧ
5/3 1/3 -5/3
-2 -2
  2/3 1/3 1/3 -1
-2
-2
-3

 

План оптимален и является целочисленным, следовательно оптимальное решение исходной задачи имеет вид:

; .

Замечание: При решении целочисленных задач линейного программирования с помощью встроенной функции Поиск решения в табличных редакторах Microsoft Excel и OpenOffice.org Calc необходимо добавить дополнительное ограничение по целочисленности переменных (рисунок 20, 21).

 

Р и с. 20.

 

Р и с. 21.

 

Задание

1. Методом Гомори найти оптимальное решение задачи 10:

при условиях

 

2. Решить задачу 10 в табличном редакторе Excel c помощью встроенной функции Поиск решения.

Контрольные вопросы

1. Какая задача называется задачей целочисленного программирования?

2. Сформулируйте алгоритм решения задачи целочисленного программирования методом Гомори.

3. Какие решения считаются оптимальными для задач целочисленного программирования?

4. Выполняются ли критерии оптимальности линейного программирования для оптимальных решений задач целочисленного программирования?

5. Как найти решение задачи целочисленного программирования средствами Excel?

 

 

Лабораторная работа №7.

Метод ветвей и границ.

Последнее изменение этой страницы: 2016-07-23

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...