Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Метод отсечения (метод Гомори)

Читайте также:
  1. G ГРАЖДАНСКО-ПРАВОВОЙ МЕТОД ПРАВОВОГО РЕГУЛИРОВАНИЯ Метод правового регулирования, характеризуется
  2. G ГРАЖДАНСКО-ПРАВОВОЙ МЕТОД ПРАВОВОГО РЕГУЛИРОВАНИЯ Метод правового регулирования, характеризуется
  3. I. Метод
  4. I. Моделирование как метод познания.
  5. II Методы расчета и переоценки ВВП
  6. II процессуальные и организационно-методические основания
  7. II. Метод синтаксического анализа по непосредственно составляющим.
  8. II. Три точки зрения дизайнера на вещь и методы их реализации
  9. III. Социально-психологические методы.
  10. III. Трансформационный метод.
  11. Meтoдикa oбyчeния rpaмoтe кaк cocтaвнaя чacть мeтoдики пpeпoдaвaния pyccкoro языкa. Главные объекты методики обучения грамоте
  12. REM Метод простой итерации

Постановка задачи целочисленного программирования (ЗЦП)

Целочисленное программирование.

ЗЦЛП формируется следующим образом:

Найти такое решение (план) Х=(х1х2… хn), при котором линейная ф-ция:

n

Z=∑cjxj принимает max или min значение, при ограничениях:

j=1

n

∑ aijхj=bi, i=1,2, …m;

j=1

xj≥0, j=1,…n; xj- целые числа.

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

- методы отсечения;

- комбинаторные;

- приближенные;

 

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

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

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

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

 

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

Алгоритм решения ЗЛЦП, предложенный Гомори, основан на симплексном методе и использует способ построения правильного отсечения.

Неравенство, сформированное по i-тому уравнению системы ограничения оптимального решения, имеет вид:

βi - αim+1 xm+1-…- αm xn≤0 (1),

где {βi}, { αim+1}, { αm} – не целые компоненты коэффициентов.

Целой частью числа а называется наибольшее число [α], не превосходящее α; дробной частью числа а является числа α =α-[α]. Например для

α =2⅓; [α]=2, α =2⅓ -2=1/3,для

 

α = -2⅓; [α]= -3, α = -2⅓-(-3)=2/3

<== предыдущая лекция | следующая лекция ==>
| Метод отсечения (метод Гомори)

Дата добавления: 2014-01-06; Просмотров: 108; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.161.3.96
Генерация страницы за: 0.008 сек.