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

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

Основные свойства ЗЛП

Основные свойства ЗЛП - раздел Информатика, Методические указания по дисциплине Математические методы исследования операций Информационные управляющие системы и технологии Для Злп Справедлива Следующая Теорема. Теорема (О Существовании Реше...

Для ЗЛП справедлива следующая теорема.

Теорема (о существовании решения). Если допустимое множество X ЗЛП не пусто, а значение её конечно, то эта задача имеет решение.

 

Определение. Множество, образованное пересечением конечного числа полупространств и гипер­плос­костей, если оно не пусто, называется многогранным множеством.

Определение. Многогранником называется ограниченное многогранное множество.

Множество допустимых решений ЗЛП представляет собой многогранное множество.

Теорема. Пусть допустимое множество X ЗЛП max cTx, xX является многогранником. Тогда ЦФ cTx достигает своего максимума в вершине X. Если функция cTx принимает максимальное значение более чем в одной точке, то она достигает того же значения в любой точке, являющейся их выпуклой линейной комбинацией [5].

 

Из этой теоремы вытекает, что множество оптимальных точек не может быть конечным, если опти­мальная точка не единственна [9].

Алгебраическая запись ЗЛП в канонической форме такова:

Пусть задача (6) имеет допустимые решения и ранг матрицы A равен m (числу ограничений-равенств). Это предположение о ранге практически не является ограничивающим. Этого можно добиться, исключив из системы Ax=b линейно зависимые уравнения.

Кроме того, будем считать, что n>m, т.к. случай n=m не представляет интереса, а соотношение n<m невозможно, так как в этом случае ранг не может быть равен m.

Задачу (6) можно трактовать следующим образом: из всех представлений вектора b в виде линейной комбинации векторов a*j, j=с неотрицательными коэффициентами выбрать такое (если оно сущест­вует), коэффициенты которого максимизируют значение функции cTx. [11]

Система ограничений ЗЛП (6) в векторной форме:

Определение. Базисом ß матрицы A называется набор линейно-независимых столбцов: ß=.

Определение. Базисной матрицей B называется матрица, составленная из столбцов, входящих в базис матрицы A: B.

Матрица B является невырожденной m ×m матрицей.

Определение. Базисным решением, соответствующим ß, называется вектор xRn, в котором:

– xj=0 при a*j ß,

– xjk есть k-я компонента вектора B–1b, где k=1,..,m.

Таким образом, базисное решение x можно найти с помощью следующей процедуры:

– выбрать множество линейно независимых столбцов в матрице A;

– положить все компоненты вектора x, соответствующие столбцам, не входящим в базис ß, равными 0. Эти переменные будем называть небазисными;

– решить m полученных уравнений для определения оставшихся m компонент вектора x. Они будут называться базисными переменными.

Определение. Решение x будем называть допустимым базисным решением (ДБР), если оно является базисным и все его компоненты неотрицательны.

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

Определение. ДБР называется невырожденным, если оно имеет точно m положительных компонент (координат). Если число положительных компонент меньше m, то решение называется вырожденным.

Теорема. Вектор x=(x1, x2,…, xn)T тогда и только тогда является допустимым базисным решением задачи (6), когда точка x=(x1, x2,…, xn)T является вершиной его многогранного множества X.

Теорема (фундаментальная). Если ЗЛП имеет оптимальное решение (в ограниченной области всегда, а в неограниченной – в зависимости от ограниченности целевой функции ), то оно совпадает, по крайней мере, с одним из ДБР системы ограничений.

 

4. Идея симплекс – метода

Согласно фундаментальной теореме вместо исследования бесконечного множества допустимых решений, необходимо исследовать лишь конечное число ДБР. Таким образом, принципиальная схема решения ЗЛП такова[7]:

– найти все ДБР;

– вычислить для каждого из них соответствующее значение ЦФ z;

– сравнить и определить наилучшее.

Но, в общем случае при больших значениях n и m количество ДБР может быть огромным (порядка Cnm) и практическое осуществление перебора всех ДБР станет невозможным. Эти трудности обусловлены тем, что указанная принципиальная схема связана с беспорядочным пе­ре­бором ДБР, без учета, насколько новое проверяемое ДБР изменяет ЦФ z и приближает ли оно нас к иско­мому оптимуму. Если же указанный перебор ДБР производить целеустремленно, добиваясь на каждом шаге монотонного изменения ЦФ z, т.е. чтобы каждое следующее ДБР было лучше предыдущего (или, по крайней мере, не хуже), то число анализируемых ДБР можно резко сократить.

Основной метод решения ЗЛП – симплекс-метод – базируется на идее последовательного улучше­ния решения. Очевидно, что для реализации этой идеи метод должен включать три основных элемента:

– способ определения исходного ДБР;

– правило перехода к следующему “лучшему” ДБР;

– критерий, по которому можно определить оптимальность найденного решения или необходи­мость его дальнейшего улучшения.

 

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

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

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

Национальный технический университет Украины.. Киевский политехнический институт.. Симплекс метод..

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

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

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

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

Формы ЗЛП
Задача математического программирования вида: называется задачей линейного программирования (ЗЛП). Основн

Эквивалентность различных форм ЗЛП
Все перечисленные формы ЗЛП являются эквивалентными в том смысле, что простыми преобразова­ниями задачу, имеющую одну из форм, легко привести к задаче, имеющей одну из оставшихся форм, причем по оп

Решение
Так как первое ограничение имеет знак “≥”, то в левую часть ограничения вводим избыточную переменную s1. Данное ограничение будет иметь вид: x1 + 2x2

Решение
В этом случае на переменную x2 не накладывается ограничение неотрицательности. Введя две новые неотрицательные переменные x2+≥0, x2–X

Упражнения
1) Укажите, какая из ниже приведенных форм задач является канонической? а) б)

Способ перехода от одного ДБР к другому
Пусть ДБР x0 соответствует преобразованной задаче (13)-(15). Перейдем от него к новому ДБР x1. При этом рассмотрим возможность того, что только одна небазисная переменн

Условие оптимальности ДБР
Определение. Вектор-строка, на которую умножается слева xN в уравнении для ЦФ (13), называется век­тором относительных оценок, т.к. он указывает, в какую сторону

Табличный симплекс-метод
Пусть для исходной ЗЛП задано начальное ДБР, базис которого образуют первые m столбцов матри­цы A. Введем новую переменную z и с помощью элементарных преобразований Жордана-Гаусса преобразуем расши

Z-строка
Текущая z-строка:(-1 –3/2 0 0 0 0 | 0) –(–3/2) × Новая ведущая строка:(-3 3/2 3/2 0 0 0 | 3) =Новая z-строка:(-4 0 3/2 0 0 0 | 3) БП

М - метод
Вернемся к введенной в примере 11.1 линейной модели. В первом и во втором уравнениях нет переменных, выполняющих роль остаточных. Поэтому введем в каждое из уравнений по одной искусственно

Двухэтапный метод
Исторически первым появился М-метод, но он имеет существенный недостаток: возможность появления ошибок в вычислениях, обусловленных очень боль­шой величиной коэффициента М. Например: М=100

Особые случаи, возникающие при применении двухэтапного мтода
  Рассмотрим примеры особых случаев, которые встречаются при решении задачи двухэтапным симплекс-методом. Пример 12.3 (Вырожденность). Пусть

Отсутствие допустимых решений
Если ограничения модели одновременно выполняться не могут, то задача не имеет допустимых решений. Такое решение всегда существует, когда все ограничения типа "≤", поскольку введение

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги