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

Раздел Информатика
/
Условие оптимальности ДБР

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

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

Условие оптимальности ДБР

Условие оптимальности ДБР - раздел Информатика, МетодичЕСКИЕ УКАЗАНИЯ по дисциплине Математические методы исследования операций Информационные управляющие системы и технологии Определение. Вектор-Строка, На Которую Умножается Сле...

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

Обозначим этот вектор через d_N. Его j-ый элемент определяется так:

Если относительная оценка (d_N)_j, то небазисной переменной (x_N)_j положительна или равна нулю, но значение ЦФ не увеличивается при увеличении (x_N)_j, начиная с нуля [11].

Теорема (условие оптимальности).Для ДБР x⁰ операция замещения, при которой (x_N)_p вводится в базис, изменяет значение ЦФ на величину

где

Если d_N≥0, то x⁰ оптимально.

ЗЛП будем называть невырожденной, если все ее ДБР не вырождены. Справедлива теорема, обратная последней теореме.

Теорема. Пусть ЗЛП является невырожденной, а x⁰ – ДБР, являющееся ее решением. Тогда d_N≥0.

В том случае, если ЗЛП не является невырожденной, предыдущая теорема приобретает вид:

Теорема. Для того, чтобы ДБР x⁰ являлось решением исходной ЗЛП, необходимо и достаточно существование такого базиса для x⁰, для которого d_N≥0.

Теорема. Если некоторому ДБР исходной задачи соответствует задача, для которой существует небазисная переменная (x_N)_p такая, что (d_N)_p<0 и (a_N)_*p≤0, то целевая функция исходной задачи не ограничена на множестве допустимых решений (θ не ограничено сверху и можно сколько угодно увеличивать целевую функцию).

Пример 7.1

Дана ЗЛП

Знайти всі компоненти перетвореної задачі для ДБР, який відповідає базису . Чи є оптимальним цей ДБР?

Розв’язок

Базисні, небазисні змінні та відповідні їм векторикоєфіцієнтів ЦФ:

Небазисна матриця та вектор правих частин обмежень:

Базисна матриця та матриця, обернена до неї:

Значення базисних змінних та ЦФ:

Вектор відносних оцінок небазисних змінних:

Оскільки вектор відносних оцінок небазисних змінних містить додатні компоненти, а задача на максимум, то поточний базисний розв'язок не є оптимальним.

Развернуть

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

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

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

МетодичЕСКИЕ УКАЗАНИЯ по дисциплине Математические методы исследования операций Информационные управляющие системы и технологии

НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ УКРАИНЫ... КиЕвский ПолИтехнИчЕСКий Институт... Симплекс метод...

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

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

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

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

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

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

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

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

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

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

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

Табличный симплекс-метод
Пусть для исходной ЗЛП задано начальное ДБР, базис которого образуют первые 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 (Вырожденность). Пусть

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