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

Раздел Образование
/
Алгоритм решения ЗЛЦП

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

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

Алгоритм решения ЗЛЦП

Алгоритм решения ЗЛЦП - раздел Образование, Курс лекций Основные понятия и определения 1.симплексным Методом Решить Задачу Без Учета Условия Целочисленности, Если В...

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

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

3.Неравенство, определяющее правильное отсечение введением дополнительной, неотрицательной целочисленной переменной, преобразовать в равносильное уравнение и включить его в систему ограничений.

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

Пример: При решении некоторой оптимизационной задачи симплексным методом получено некоторое базисное решение:

х₁=2 – 1х₄ + 4х₅

3 3 3

х₂=8 – х₅

х₃=18+х₄+х₅

Z=25 1 – 2x₄ – 1x₅

3 3 3

X=(2; 8; 18; 0; 0) Z=25 1

3 3

Это базисное решение оптимизировано.

Однако решение Х не удовлетворяет условию целочисленности, т.к. по первому уравнению с переменной x₁=2/3-1/3x₄+4/3x₅, получившей нецелочисленное значение в оптимальном решении(2/3).

Составляем правильное отсечение, в виде дополнительного ограничения.

2/3 + 1/3 х₄– 4/3 х₅≤0 (1)

Обращаем внимание на то, что берем дробную часть свободного члена с тем же знаком, который он имеет в уравнении, а дробные части коэффициентов при не основных переменных х₄ и х₅ – с противоположными знаками.

Так как дробные части:

2/3 = 0+2/3 =2/3

1/3 = 0+1/3 =1/3

-4/3 = -2+2/3 =2/3,

тогда последнее неравенство в соответствии c (1) запишется в виде:

2/3+1/3х₄-2/3х₅≤0 (2)–правильное отсечение.

Введя дополнительную целочисленную переменную х₆ ≥ 0, получим равносильное неравенству (2) ,уравнение:

2/3+1/3х₄-2/3х₅+х₆=0

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

Развернуть

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

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

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

Курс лекций Основные понятия и определения

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ... МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ... Г С БОРОВСКИЙ...

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

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

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

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

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

Общая постановка задачи линейного программирования.
Обозначим Хj (j = 1,2, … , n) –число единиц продукции Pj; bi (i = 1,2,…, m) запас ресурса Si; aij – число единиц ресурса S

Решение.
X1, X2– число единиц видов изделий соответственно А и В. № п/п Алгоритм Конкретное соответствие данной задаче

Геометрическая интерпретация решения ЗЛП.
Графический метод решения ЗЛП состоит из следующих этапов: На координатной плоскости Х1ОХ2 строится область допустимых решений (ОДР). Она представляет собой мно

Отыскание опорного и оптимального решения ЗЛП с использованием табличного алгоритма с заменой базисных переменных.
Алгоритм составления симплексных таблиц (СТ), рассмотрим на примере решения задачи отыскания max. Пример 2.6 Линейная функция: F=2x1+3x

Выполнить самостоятельно.
В соответствии с индивидуальным заданием №1 решить задачу максимизации с использованием симплексных таблиц. Вариант задания выбирается по номеру зачетной книжки: -предпоследняя цифра - № с

ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ №1
0,1,2 3,4,5,6 7,8,9 f(x)=3x1-2x2; 2x1+x2

Постановка задачи целочисленного программирования (ЗЦП)
ЗЦЛП формируется следующим образом: Найти такое решение (план) Х=(х1х2… хn), при котором линейная ф-ция: n Z=∑cj

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

Метод множителей Лагранжа.
Другой способ определения условного экстремума осуществляется с построения вспомогательной функции Лагранжа, которая достигает max для тех же х1,х2,…,хn, что и целе

Методы определения экстремума унимодальной функции.
Унимодальная функция – функция, в интервале исследования имеющая только один экстремум. А) Методы определения экстремума функции одной переменной.

Методы определения локального экстремума функции нескольких переменных
а) Метод Гаусса – Зейделя Метод поочередного изменения параметров (переменных), или метод покоординатного спуска (подъема). Суть метода: поочеред

Алгоритм метода
Случайно выбираемся точка с некоторыми координатами. Затем по формуле (1) рассчитывается следующая точка. Алгоритм остана