рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Постановка задачи ЦЛП

Реферат Курсовая Конспект

Выберите учебное заведение

Постановка задачи ЦЛП

Постановка задачи ЦЛП - раздел Образование, Конспект лекций МЕТОДЫ ОПТИМИЗАЦИИ Задача Целочисленного Программирования (Цлп) Формулируется Так Же, Как И Зада...

Задача целочисленного программирования (ЦЛП) формулируется так же, как и задача ЛП, но включается дополнительное требование, состоящее в том, что значения переменных, составляющих оптимальное решение, должны быть целыми неотрицательными числами:

(22)

Симплекс-метод не гарантирует целочисленности решения задачи (22), поэтому для отыскания оптимального целочисленного решения задачи ЦЛП требуются специальные методы. Один из таких методов, приводящий к целочисленному решению за конечное число шагов, предложен американским математиком Р. Гомори [1,2]. Идея метода следующая.

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

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

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Конспект лекций МЕТОДЫ ОПТИМИЗАЦИИ

Государственное образовательное учреждение высшего профессионального образования... Омский государственный технический университет...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Постановка задачи ЦЛП

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Омск 2007
УДК 007(075) ББК 32.81я73 З-96 Рецензенты: О.В. Кириченова, канд. физ.-мат. наук, доц. ОмГПУ; О.П. Диденко, канд. пед. н

Общие рекомендации к графическому решению задач ЛП
1. Графически могут решаться [1]: a) задачи, заданные в произвольной форме, содержащие не более двух переменных; b) задачи, заданные в канонической форме, с числом свободных перем

Симплекс-метод
Рассмотрим задачу ЛП в канонической форме: (12) ……………

Алгоритм симплекс-метода для задачи на минимум
Шаг 0. Подготовительный этап. Приводим задачу ЛП к специальной форме (15). Шаг 1. Составляем симплекс-таблицу, соответствующую специальной форме:

Метод искусственного базиса
Симплекс-метод применяется для решения задач ЛП, представленных в специальной форме: (16) Характерная особенность задачи

Двойственный симплекс-метод
Метод работает с теми же симплексными таблицами, что и прямой симплекс-метод для задачи на минимум. Сначала определяется переменная, подлежащая выводу из базиса, а затем переменная,

Теоремы двойственности
Двойственность является одним из фундаментальных понятий в теории ЛП. Исключительно важную роль играют следующие утверждения, получившие названия теорем двойственности [1,3]. Первая тео

Алгоритм метода Гомори
Шаг 1. Симплекс-методом находим оптимальное решение задачи (22) без учета условия целочисленности. Если задача не имеет решения, то неразрешима и исходная задача ЦЛП. В этом случае алгоритм

Постановка задачи
Классическая транспортная задача ЛП формулируется следующим образом. Имеется m пунктов производства (поставщиков) и n пунктов потребления (потребителей) однородного продукта. Заданы в

Построение опорного плана транспортной задачи
Методы решения транспортной задачи сводятся к простым операциям с транспортной таблицей, которая имеет вид: …

Метод северо-западного угла
Рассмотрим «северо-западный угол» незаполненной таблицы, то есть клетку, соответствующую первому поставщику и первому потребителю. Возможны три случая: Если

Метод потенциалов
Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке цикла совершает поворот на