Студопедия — Лабораторная работа №8. Метод Гомори для решения задач целочисленного линейного программирования
Студопедия Главная Случайная страница Обратная связь

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

Лабораторная работа №8. Метод Гомори для решения задач целочисленного линейного программирования






< c, x> ® m,

A x = b, (4. 2)

x ³ 0

xi Î целые, iÎ {1, 2, 3,..., n}=[1..n].

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

Шаг 1. Отбросим условие целочисленности

< c, x> ® m,

A x = b, (4. 3)

xi ³ 0, iÎ {1, 2, 3,..., n}=[1..n],

получим задачу линейного программирования (4.3).

Шаг 2. Решим задачу (4.3) одним из алгоритмов симплекс-метода. Если полученное оптимальное оптимальное решение X целочисленное (т.е. xi целые для всех iÎ [1..n]), то алгоритм прекращает работу, иначе переходим к шагу 3.

Шаг 3. Если задача решалась симплекс-методом, значение базисных переменных xi записано в столбце b симплекс-таблицы, внебазисные переменные равны нулю. Среди элементов столбца b ищем нецелочисленные. Если таких несколько, то обычно берется такое i0, что i0= argmax{b(i)| iÎ [1..m]}, составляется дополнительное ограничение (отсечение Гомори):

å {- frac (a(i0 , j)) ´ x(i)| jÎ [,..n] £ - frac (b(i0)), (4.4)

где frac(a) - дробные части числа a.

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

 

Пример.

 

x1 + x2 ® max,

2 x1 + x2 £ 2,

x1 +2 x2 £ 2,

xi ³ 0, xi - целые, i=1, 2.

 

Занесем данные в симплекс-таблицу:

Xb b X1 X2 Y1 Y2
Y1 2 2 1 1 0
Y2 2 1 2 0 1
d 0 -1 -1 0 0

Решив эту задачу без условия целочисленности, получим симплекс-таблицу.

Xb b X1 X2 Y1 Y2
X1 0.67 1 0 0.67 -0.33
X2 0.67 0 1 - 0.33 0.67
d 1.33 0 0 0.33 0.33

 

Из этой таблицы получаем X1=0.67, X2=0.67, т.е. решение не целочисленное, строим дополнительное ограничение по первой строке (можно и по второй): -0.67Y1 - 0.67Y2 £ -0.67.

Приводим его к каноническому виду -0.67Y1 - 0.67Y2 + Y3 = -0.67

и приписываем к симплекс-таблице:

 

Xb b X1 X2 Y1 Y2 Y3
X1 0.67 1.0 0 0.67 - 0.33 0
X2 0.67 0 1 -0.33 -0.67 0
Y3 -0.67 0 0 -0.67 -0.67 1
d 1.33 0 0 0.33 -0.33 0

 

Решаем двойственным симплекс-методом:

 

Xb b X1 X2 Y1 Y2 Y3
X1 0 1.0 0 0 -1 1
X2 1 0 1 0 1 0
Y1 1 0 0 1 1 1
d 1.33 0 0 0 0 0.5

 

Получим целочисленное решение X1= 0, X2=1, Y1=1, Y2=0, Y3=0, Y1, Y2, Y3 - дополнительные переменные. Ответ: X1= 0, X2=1.

Задание 8

 

Решить задачу из лабораторной работы N13 " Лабораторного практикума по методам оптимизации", добавить к условиям задачи условия целочисленности. Исходной таблицей для метода Гомори взять последнюю симплекс-таблицу лабораторных работ 14-15. Если в ней получено целочисленное решение, то задание скорректировать у преподавателя.

 

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

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

< c, x> ® max,

A x = b, (4. 5.)

x ³ 0,

xi - целые, i Î [1..n].

Для ее решения применим метод ветвей и границ.







Дата добавления: 2014-12-06; просмотров: 1104. Нарушение авторских прав; Мы поможем в написании вашей работы!



Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

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

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

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

Различия в философии античности, средневековья и Возрождения ♦Венцом античной философии было: Единое Благо, Мировой Ум, Мировая Душа, Космос...

Характерные черты немецкой классической философии 1. Особое понимание роли философии в истории человечества, в развитии мировой культуры. Классические немецкие философы полагали, что философия призвана быть критической совестью культуры, «душой» культуры. 2. Исследовались не только человеческая...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит...

ИГРЫ НА ТАКТИЛЬНОЕ ВЗАИМОДЕЙСТВИЕ Методические рекомендации по проведению игр на тактильное взаимодействие...

Реформы П.А.Столыпина Сегодня уже никто не сомневается в том, что экономическая политика П...

Виды нарушений опорно-двигательного аппарата у детей В общеупотребительном значении нарушение опорно-двигательного аппарата (ОДА) идентифицируется с нарушениями двигательных функций и определенными органическими поражениями (дефектами)...

Studopedia.info - Студопедия - 2014-2024 год . (0.01 сек.) русская версия | украинская версия