![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Альтернативные оптимальные решенияСодержание книги
Похожие статьи вашей тематики
Поиск на нашем сайте
Когда гиперплоскость, представляющая целевую функцию, параллельна гиперплоскости, соответствующей связывающему ограничению (которое в точке оптимума выполняется как точное равенство), целевая функция принимает одно и то же оптимальное значение в некоторой совокупности точек пространства решений. Такие решения называются альтернативными оптимальными решениями. Приводимый ниже пример рассматриваемой ситуации показывает, что при этом обычно существует бесконечное множество альтернативных решений. Пример: F( при ограничениях x1 + 2×x2 £ 5 (ресурс 1) x1 + x2 £ 4 (ресурс 2) x1 ³ 0, x2 ³ 0. Рис.2 иллюстрирует условия данной задачи ЛП, особенность которой состоит в том, что прямая, представляющая целевую функцию, параллельна прямой, соответствующей одному из связывающих ограничений.
Рис. 2. Геометрическая интерпретация альтернативных базисных решений Это обусловливает наличие альтернативных оптимальных решений. Любая точка отрезка ВС представляет собой альтернативный оптимум, причем в каждой из этих точек целевая функция имеет одно и то же оптимальное значение. Приведем решение задачи в симплекс-таблице. Таблица 2
Каким образом по результатам итерации можно узнать о наличии альтернативных решений? Нулевое значение симплексной разности у небазисной переменной свидетельствует о том, что ее включение в базис не изменит значения целевой функции, но приведет к изменению других переменных. Любое решение, соответствующее точке ( В: х1 = 0; х2 = 5/2; С: х1 = 3; х2 = 1; и полагая
Информация о наличии альтернативных оптимумов дает возможность выбора альтернативного варианта в наибольшей степени отвечающего сложившейся производственной ситуации.
Метод искусственного базиса Часто, после приведения ОЗЛП к каноническому виду расширенная матрица системы линейных уравнений (СЛУ) не является К-матрицей (нет начального опорного плана), и, следовательно, решать такую КЗЛП симплекс-методом нельзя. Суть метода искусственного базиса состоит в следующем: строится такая вспомогательная КЗЛП (ВКЗЛП) с заранее известным опорным планом, по решению которой либо определяется начальный опорный план исходной задачи, либо устанавливается, что ее множество планов пусто. Дано:
Найти: К-матрицу (начальный опорный план). Построим следующую ВКЗЛП:
Очевидно, начальный опорный план ВКЗЛП имеет вид:
Применяя симплекс-метод, находят
Замечание: ВКЗЛП всегда разрешима, так как множество ее планов не пусто, а целевая функция ограничена. Теорема: Если Пример: F(X) = 5×x1 + 3×x2 + 4×x3 - x4 x1 + 3×x2 + 2×x3 + 2×x4 = 3 2×x1 + 2×x2 + x3 + x4 = 3
x1 + 3×x2 + 2×x3 + 2×x4 + y1 = 3 x1 + 3×x2 + 2×x3 + 2×x4 + y2 = 3 xj
Таблица 1
Замечание: По мере выхода искусственных переменных из базиса, вычисления в соответствующих клетках симплекс-таблицы не проводятся. Получили оптимальный опорный план ВКЗЛП.
Теперь решаем симплекс-методом исходную задачу: F(X)= 5×x1 + 3×x2 + 4×x3 - x4 x2 + 3/4×x3 + 3/4×x4 = 3/4 x1 - 1/4×x3 - 1/4×x4 = 3/4 xj Таблица 2
Анализ решаемых задач Математическая модель является хорошим средством получения ответов на широкий круг самых разнообразных вопросов, возникающих при принятии оптимальных решений. Например, на этапе постановки задачи часто производится анализ с целью ответа на вопросы: “что будет, если...?“ и/или “что надо, чтобы...?”. Анализ с целью ответа на первый вопрос называется вариантным анализом; на второй - решениями по заказу. Для задач распределения ресурсов большой интерес представляет решение задачи минимизации используемых ресурсов при заданном результате.
Рассмотрим следующую исходную задачу: Первая постановка: F( при ограничениях на ресурсы 2 X1 + X3 + X4 X1 + 2 Xj Решив задачу получим: X1 = 0 - объем производства продукции вида 1, X2 = 125 - объем производства продукции вида 2, X3 = 0 - объем производства продукции вида 3, X4 = 80 - объем производства продукции вида 4. F( Вторая постановка: F( при ограничениях на ресурсы 2 X1 + X3 + X4 X1 + 2 X1 X3 X4 Xj В результате решения получим: Третья постановка: F( 2 X1 + X3 + X4 + Y2 = 80 - (сырье) X1 + 2 X1 X3 Y1, Y2, Y3 Решив задачу получим: При решении по заказу пользователь задает значения тех величин, которые он хочет иметь в оптимальном решении. Такие задачи могут быть трех видов: 1) назначение величины целевой функции; 2) назначение величин искомых переменных; 3) назначение величин используемых ресурсов. Следует иметь в виду, что во всех этих случаях возможно появление несовместного решения. Рассмотрим такую ситуацию на нашем примере. Четвертая постановка: F( при ограничениях на ресурсы 2 X1 + X3 + X4 X1 + 2 X1 X3 = 30, X4 = 70 ограничения на выпуск продукции) Xj Очевидно, что для выпуска такого количества продукции располагаемых ресурсов будет недостаточно. Найдем минимальные значения дополнительных необходимых ресурсов каждого вида позволяющих удовлетворить ограничениям задачи. Пятая постановка: F( 2 X1 + X3 + X4 - t2 = 80 - (сырье) X1 + 2 X1 X3 = 30, X4 = 70. t1, t2, t3 Решив задачу получим:
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-04-21; просмотров: 853; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.216.142.24 (0.011 с.) |