Студопедия — Лабораторная работа №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; просмотров: 1103. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

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

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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Ведение учета результатов боевой подготовки в роте и во взводе Содержание журнала учета боевой подготовки во взводе. Учет результатов боевой подготовки - есть отражение количественных и качественных показателей выполнения планов подготовки соединений...

Сравнительно-исторический метод в языкознании сравнительно-исторический метод в языкознании является одним из основных и представляет собой совокупность приёмов...

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

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

Медицинская документация родильного дома Учетные формы родильного дома № 111/у Индивидуальная карта беременной и родильницы № 113/у Обменная карта родильного дома...

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

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