Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Методы отсечения. Метод Гомори

Читайте также:
  1. A. гностическим методам
  2. Amp;Сравнительная характеристика различных методов оценки стоимости
  3. C) Методы стимулирования поведения деятельности
  4. E) мировоззренческая, гносеологическая, методологическая.
  5. I ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ
  6. I. Из истории развития методики развития речи
  7. I. ОБЩИЕ МЕТОДИЧЕСКИЕ УКАЗАНИЯ
  8. I. Определение эпидемического процесса и методологическое обоснование разделов учения об эпидемическом процессе.
  9. I. Определение эпидемического процесса и методологическое обоснование разделов учения об эпидемическом процессе.
  10. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ

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

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

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

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

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

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

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

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

Один из алгоритмов решения задачи линейного целочисленного программирования (4.41) – (4.44), предложенный Гомори, основан на симплексном методе и использует достаточно простой способ построения правильного отсечения.

Пусть задача линейного программирования (4.41) – (4.43) имеет конечный оптимум и на последнем шаге ее решения симплексным методом получены следующие уравнения, выражающие базисные переменные x1, x2,..., xj,..., xm через свободные переменные xm+1, xm+2,..., xm+i,..., xn оптимального решения

x1 = b1 – a1,m+1ּ xm+1 -... – a1,m+iּ xm+i -... – a1,nּ xn

x2 = b2 – a2,m+1ּ xm+1 -... – a2,m+iּ xm+i -... – a2,nּ xn

.......

xi = bi – ai,m+1ּ xm+1 -... – ai,m+iּ xm+i -... – ai,nּ xn (4.45)

.......

xm = bm – am,m+1ּ xm+1 -... – am,m+iּ xm+i -... – am,nּ xn

так, что оптимальным решением задачи (4.41) – (4.43) является

X* = (b1, b2,..., bi,..., bm, 0, 0,..., 0), в котором, например, bi – нецелая компонента. В этом случае можно доказать, что неравенство1)

{bi} – {ai,m+1}ּxm+1 -... – {ai,m+i}ּxm+i -... – {ai,n}ּ xn ≤ 0 (4.46)

сформированное по i-му уравнению системы (4.45), обладает всеми свойствами правильного отсечения.

--------------------------------------------------------------------------------------------------------

1) – в неравенстве (4.46) символ { } означает дробную часть числа. Целой частью числа а называется наибольшее число [a], не превосходящее а, а дробной частью числа – число {а}, равное разности между этим числом и его целой частью, то есть, {а} = а - [a].

Например, для а = 2 имеем [a] = 2, {а} = 2 - 2 = ;

для а = - 2 имеем [a] = -3 {а} = - 2 - (-3) = ;

--------------------------------------------------------------------------------------------------------

Для решения задачи целочисленного линейного программирования

(4.41) – (4.44) методом Гомори используется следующий алгоритм:

1. Симплексным методом решить задачу (4.41) – (4.43) без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для решения задачи целочисленного программирования (4.41) – (4.44). Если первая задача (4.41) – (4.43) неразрешима (то есть, не имеет конечного экстремума или условия ее противоречивы), то и вторая задача

(4.41) – (4.44) также неразрешима.

2. Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с наибольшей целой частью и по соответствующему уравнению системы (4.45) сформировать правильное отсечение (4.46).

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

{bi} – {ai,m+1}ּxm+1–... –{ai,m+i}ּxm+i –... – {ai,n}ּxn + xn+1 = 0 (4.47)

и включить его в систему ограничений (4.42).

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

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

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

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

Пример 4.1. Для приобретения оборудования по сортировке зерна фермер выделяет 34 ден.ед. Оборудование должно быть размещено на площади, не превышающей 60 кв. м. Фермер может заказать оборудование двух видов: менее мощные машины типа А стоимостью 3 ден.ед., требующие производственную площадь 3 кв. м. (с учетом проходов) и обеспечивающие производительность за смену 2 т. зерна, и более мощные машины типа В стоимостью 4 ден.ед., занимающие площадь 5 кв.м. и обеспечивающие производительность за смену 3 т. сортового зерна.

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

Решение. Обозначим через х1, х2 количество машин, соответственно, типа А и В, через Ф – общую производительность. Тогда математическая модель задачи примет вид: Ф = 2 x1 + 3 x2 → max (4.1.1)

при ограничениях: 3 x1 + 5 x2 ≤ 60,

3 x1 + 4 x2 ≤ 34, (4.1.2)

x2 ≤ 8,

х1≥ 0, х2 ≥ 0, (4.1.3)

х1, х2 - целые числа., (4.1.4)

Приведем задачу к каноническому виду, введя дополнительные неотрицательные переменные х3, х4, х5 . Получим систему уравнений:

3 x1 + 5 x2 + х3 = 60,

3 x1 + 4 x2 + х4 = 34, (4.1.5)

x2 + х5 = 8,

хj≥ 0, j=1, 2, …, 5.

Решаем задачу симплексным методом. Для наглядности решение проиллюстрируем графически (рис. 4.2).

 

       
 
   
х1
 

 

 


Рис. 4.2.

На рис. 4.2 OKLM–область допустимых решений задачи (4.1.1) –(4.1.3), ограниченная прямыми (1), (2), (3) и осями координат; L(2/3; 8) – точка оптимального, но нецелочисленного решения задачи (4.1.1)–(4.1.3); (4) - прямая, отсекающая это нецелочисленное решение; OKNM – область допустимых решений расширенной задачи (4.1.1) – (4.1.3), (4.1.4); N(2; 7) – точка оптимального целочисленного решения.

I шаг. Базисные переменные х3, х4, х5; свободные переменные х1, х2.

х3 = 60 - 3 x1 - 5 x2 ,

х4 = 34 - 3 x1 - 4 x2,

х5 = 8 - x2,

Ф = 2 x1 + 3 x2 ,

Первое базисное решение Х1 = (0; 0; 60; 34; 8) – допустимое. Соответствующее значение линейной функции Ф1 = 0.

Условие оптимальности не выполнено, максимум Ф не достигнут. Переводим в базисные переменную x2, которая входит в выражение линейной функции с наибольшим положительным коэффициентом. Находим максимально возможное значение x2, которое «позволяет» принять система ограничений, из условия минимума соответствующих отношений x2 = min (60/5; 34/4; 8/1) = 8,

то есть, разрешающим является третье уравнение. При x2 = 8 в этом уравнении х5= 0, и в свободные переходит переменная х5, переменная x2 - в базисные.

II шаг. Базисныепеременные х2 , х3 , х4; свободные переменные х1 , х5.

х2 = 8 – x5

х3 = 20 - 3 x1 + 5 x5 ,

х4 = 2 - 3 x1 + 4 x5 ,

Ф = 24 +2 x1 - 3 x5 .

Х2 = (0; 8; 20; 2; 0); Ф2 = 24. Условие оптимальности не выполнено, максимум Ф не достигнут. Переводим в базисные переменные х1 , а в свободные х4 , так как x1 = min (∞; 20/3; 2/3) = 2/3,

III шаг. Базисныепеременные х1 , х2 , х3; свободные переменные х4 , х5.

х1= 2/3 – 1/3∙x4 +4/3∙x5 ,

х2 = 8 - x5 ,

х3 = 18 + x4 + x5 ,

Ф = 76/3 – 2/3 ∙x4 -1/ 3 ∙x5 .

Х3 = (1; 8; 18; 0; 0); Ф2 = 76/3.. Условие оптимальности выполнено, максимум Ф достигнут, задача решена.




Дата добавления: 2014-12-15; просмотров: 171 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.01 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав