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

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

Целочисленное или дискретное программирование

Читайте также:
  1. I. Программирование на CF Pascal
  2. PPUZKK 4230-программирование и прогнозирование урожаев зерновых культур и картофеля
  3. PPUZKK 4230-программирование и прогнозирование урожаев зерновых культур и картофеля
  4. VII.Модульное программирование.
  5. Алгоритмизация и программирование
  6. Введение в программирование для Windows
  7. Введение в программирование на языке Pascal Работа с величинами. Ввод-вывод Выражения. Линейные алгоритмы
  8. Вопрос33. Нелинейное программирование. Метод Лагранжа.
  9. Дискретное представление информации: кодирование цветного изображения в компьютере (растровый подход). Представление и обработка звука и видеоизображения.
  10. Информатика и программирование

 

 

Ограничения от целочисленной задачи называются ослабленной задачей.

 

 

Метод Гомори

(1)

(

(2) (

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

В неравенстве (3) обозначено … последнее значение полученное в симплекс таблице, а - дробная часть

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

Решается система (2)-(3) и опять проверяется значение на целочисленность. Если решений слишком много, то неравенство (3) определяется как наибольшая дробная часть

 

Метод ветвей и границ (branches and boundaries – B&B)

 

Мы разбиваем исходную задачу, на две задачи. Такой процесс называется дихотомией (ветвление). Оптимальное решение может находиться либо в ЛП1 или в ЛП2.

Задача ЛП1 удовлетворяет условиям целочисленности. Мы говорим, что задача ЛП1 прозондирована.

Задача ЛП2

Последовательность решения

Зададим нижнюю границу -

Последовательность

1. Зондирование или ослабление границ
Задача называется задачей ЛПi. Зондируем решаем и можем прийти к:

a. Оптимальное решение не может улучшить значение текущей границы.

b. ЛПi имеет решение лучше, чем исходная задача.

c. ЛПi не имеет решения.

 

a. …

b. Если задача ЛПi не прозондирована, то переходим к шагу 2.

2. Ветвление

Выбираем одну из переменных исключаем из простанства допустимых решений


 

17.10.12




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




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