Исследование операций

Размещено на http://www.allbest.ru/

Исследование операций

Основные формы и задачи ЛП

• Общая задача ЛП (ОЗЛП):

Целевая функция

Система ограничений

• Стандартная (симметричная) задача ЛП:

Целевая функция

Система ограничений (k=m, l=n)

Целевая функция

Система ограничений (k=0, l=n)

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

Каноническая форма - основные варианты симплекс-метода разработаны для этой формы.

Указанные три формы ОЗЛП эквивалентны - каждая из них может с помощью несложных преобразований м.б. приведена к любой из них. Любую задачу ЛП можно привести к каноническому виду.

Способы перехода к каноническому виду

1) Сведение задач минимизации к задачам максимизации:

2) Переход от ограничений - неравенств к ограничениям - равенствам.

3) Замена отрицательных переменных неотрицательными

Симплекс - алгоритм

Задача должна быть приведена к канонической форме. Определить начальное базисное решение (опорный план), приравнивая к 0 (n-m) переменных (небазисных). По необходимости применить искусственные переменные.

Тогда опорный план - X=(x₁, x₂, …, x_m,0,… 0)=(b₁, b₂, …, b_m,0,… 0).

Ему соответствует значение целевой функции:

Z=c₁b₁+c₂b₂+ … + c_mb_m=

Шаг 1. Опорный план исследуется на оптимальность для определения напправления его улучшения. Для этого строится нулевое приведенное уравнение на основе z:

При этом базисные переменные выражаются через свободные и подставляются в выражение для целевой функции, а также приводятся подобные коэффициенты при переменных x_j.

,

Коэффициенты a_0j - оценки оптимальности соответствующих небазисных переменных.

Характеристика оптимальности опорного плана производится по правилам:

1. Если a_0j ? 0, j=1, n, то опорный план - оптимальный. Данное условие является признаком оптимальности опорного плана.

2. Если a_0j < 0, для некоторого j и все соответствующие a_ij ? 0 (i=1, m), то значение целевой функции не ограничено сверху на множестве планов.

3. Если a_0j < 0 для некоторых индексов j и для каждого из этих существует хотя бы одно a_ij > 0, то можно перейти к новому опорному плану, при котором z увеличивается.

Шаг 2. Выбираем новый опорный план (новый базис). Из числа небазисных переменных выбирается та, увеличение которой приводит к улучшению z:

x_k, .

Т.е. выбирается так как переменная x_k, у которой в нулевом приведенном уравнении наибольший по модулю отрицательный коэффициент a_0j. Столбец симплекс-таблицы с переменной x_k называют ведущим или разрешающим столбцом.

Если такой переменной нет, то найденный опорный план - оптимальный и вычисления завершаются.

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

Для этого в разрешающем k-м столбце, соответствующем переменной, включаемой в новый базис, отыскивается такая строка l, у которой a_lk > 0 и отношение коэффициента b_l в правой части ограничения к разрешающему элементу a_lk - минимально:

ограничение линейный программирование канонический

Базисную переменную x_l следует исключить из базиса. Вместо нее в базис будет введена переменная x_k. Строку симплекс-таблицы с переменной x_l называют ведущей или разрешающей строкой.

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

Шаг 4. Переход к новому базису. Переход к новому виду системы ограничений относительно нового базиса с помощью подстановок или на основе формул Жордана-Гаусса:

Все элементы симплекс-таблицы пересчитываются по формулам Жордана-Гаусса, которые также называют правилом прямоугольника или треугольника:

1. в разрешающей строке (i=l) все элементы строки делят на разрешающий элемент a_lk;

2. во всех остальных строках элементы пересчитываются следующим образом:

Рисунок 1 - Правило прямоугольника (треугольника)

Перейти к Шагу 1.

Вычислительный процесс удобно фиксировать в симплекс-таблицах:

Список литературы

1. ГОСТ 2.105-95. Общие требования к текстовым документам. - Взамен ГОСТ 2.105-79, ГОСТ 2.906-71; введ. 1996-07-01.

2. Типовые оптимизационные задачи исследования операций, Исмагилова Э.М., Кабальнов Ю.С., Каримов Р.Р., Лапшина В.Б, Уфа, 2004.

3. Введение в исследование операций, Хемди А. Таха, Вильямс, М., 2005.

Размещено на Allbest.ru