Алгоритм метода Гомори решения целочисленных оптимизационных моделей.




Рассмотрим полностью целочисленную оптимизационную модель:

 

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

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

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

(7.1)

 

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

Таблица 7.1

Б.П. А СП
- … -
b b … b
...
b b … b
...
b b … b
= b b … b

 

Для решения целочисленной оптимизационной модели используется следующий алгоритм:

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

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

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

, (7.2)

которое включается в систему ограничений.

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

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

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

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

 

Пример 7.1. Некоторая фирма покупает оборудование стоимостью 25 ден. ед. Оборудование должно быть размещено на площади не превышающей 10м .Фирма может заказать оборудование двух типов: машины А стоимостью 6 ден. ед., требующие производственную площадь 2м (с учетом проходов) и обеспечивающие производительность за смену 5 ед. изделий и машины типа В стоимостью 7 ден. ед., занимающие площадь 3м и обеспечивающие производительность за смену 6 ед. изделий. Требуется рассчитать оптимальный вариант приобретения оборудования, обеспечивающий при данных ограничениях максимальную производительность.

Решение. Пусть – количество машин типа А; – количество машин типа В.

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

Найти план приобретения оборудования , при котором целевая функция

и который удовлетворяет ограничениям:

 

6 + 7 ≤ 25,

2 + 3 ≤ 10,

и - целые числа.

 

 

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

 

 

Б.П. А СП
- -
=
=
  =     -1 2

Таблица 7.2 Таблица 7.3

Б.П. А С.П.
- -
=   6 7
=   2
=   -5 -6

 

 

Таблица 7.4

БП СП

 

В таблице 7.4 содержится оптимальный, но нецелочисленный план . Среди нецелых свободных членов выбираем , так как это число имеет наибольшую дробную часть равную . По второй строке формируем правильное отсечение: . Находим дробные части: . Правильное отсечение принимает вид:

. Преобразуем полученное неравенство в эквивалентное уравнение, вводя неотрицательную переменную , - целое.

(7.3)

На основе таблицы 7.4 составляем таблицу 7.5 путем присоединения строки для уравнения (7.3).

 

 

Таблица 7.5

БП СП
- -

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

этом столбце минимальное симплексное отношение которое соответствует третьей строке. Эта строка и будет разрешающей.

Таблица 7.6

БП СП
  -1 2
  -2

 

Выполнив симплексное преобразование с элементом «1», приходим к таблице 7.7,

Таблица 7.7

БП СП
   
 
 
 

 

в которой опорный план оказался и оптимальным, и целочисленным.

Таким образом, оптимальным будет вариант, при котором приобретается 3 машины типа А и 1 машина типа В. При этом все денежные средства будут израсходованы , но 1 м производственной площади останется неиспользованным .Максимальная производительность за смену при этом будет равна 21единице изделий.

 

 

Литература

1. Кузнецов А.В., Сакович В.А., Холод Н.И. – Высшая математика: Математическое программирование. – Мн.: Выш. шк., 1994.

2. Кузнецов А.В., Костевич Л.С., Холод Н.И. – Руководство к решению задач по математическому программированию. - Мн.: Выш. шк., 2001.

3. Холод Н.И. и др. Экономико – математические методы и модели. – Мн.: БГЭУ, 2000.

 

 

ОГЛАВЛЕНИЕ

Предисловие ……………………………………………………….. 3

Введение …………………………………………………………… 4

1. Оптимизационные модели ……………………………………..6

1.1. Общая формулировка оптимизационной модели …… 6

1.2. Примеры линейных отимизационных моделей ……… 8

1.3. Графический способ решения линейных оптими-

зационных моделей …………………………………………… 14

2. Свойства решений линейных оптимизационных моделей … 21

3. Симплексный метод ………………………………………… 25

3.1. Понятие о симплексном методе ……………………… 25

3.2. Построение начального опорного плана ……………. 26

3.3. Признак оптимальности опорного плана ……………..29

4. Двойственность линейных оптимизационных моделей …… 31

4.1. Понятие двойственности. Построение двойственных

моделей. ……………………………………………………………... 36

4.2. Соответствие между переменными пары взаимно

двоственных линейных оптимизационных моделей …………… 38

4.3. Теоремы двойственности ………………………………… 47

Тест №1 ……………………………………………………………... 53

5.Транспортные модели ………………………………………… 59

5.1. Математическая модель транспортной задачи …………. 59

5.2. Признак разрешимости транспортной модели …………. 61

5.3. Построение начального опорного плана ……………… 63

5.4. Метод потенциалов построения оптимального опорного

плана ……………………………………………………………… 64

Тест № 2 ……………………………………………………………… 70

6. Модели теории игр …………………………………………… 76

6.1. Предмет теории игр. Основнные понятия …………….. 76

6.2. Модели матричных игр …………………………………. 77

6.2.1. Модели матричных игр и их решение в чистых

стратегиях …………………………………………………………… 77

6.2.2. Модели матричных игр со смешанными страте-

гиями. Свойства смешанных стратегий ………………………… 82

6.2.3. Решение моделей матричных игр сведением к

паре взаимно двойственных линейных оптимизационных моде-

лей ………………………………………………………………….. 85

6.3. Модели статистических игр ………………………… 95

6.3.1. Общие понятия статистических игр ……………… 95

6.3.2. Правила выбора оптимальных стратегий ………… 97

Тест № 3 ………………………………………………………………

7. Целочисленные оптимизационные модели ……………… 104

7.1. Формулировка целочисленной оптимизационной модели.

Примеры. Методы решения ………………………………………….104

7.2. Алгоритм метода Гомори решения целочисленных

оптимизационных моделей ……………………………………… 106

Литература …………………………………………………………….109

 

 

Учебное издание

 

 

Булдык Георгий Митрофанович

Доктор педагогических наук

Профессор

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-02-16 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: