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

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

Особые случаи симплексного метода

Особые случаи симплексного метода - раздел Программирование, Линейное программирование Неединственность Оптимального Решения (Альтернативный Оптимум):...

Неединственность оптимального решения (альтернативный оптимум):

Решим симплексным методом задачу:

F=3x1 + 3х2 à maxпри ограничениях:

х1 + х2 <= 8

A
2х1 - х2 >= 1

B
х1 - 2х2 <= 2

F=24
х1, х2 >= 0

Геометрическое решение:

 


Оптимум в любой точке отрезка АВ. Т.к. линия уровня параллельна этому отрезку. При решении задачи симплекс-методом наличие альтернативного оптимума проявляется следующим образом:

На очередном шаге получим: осн пер – х1, х2, х5;

неос п - х3, х4.

Выражение основных через неосн:

Х1 = 5 – (2/3)Х3 – (1/3)Х4

Х2 = 3 – (1/3)Х3 + (1/3)Х4

Х5 = 9 – Х3 – Х4

Х1 = (3; 5; 0; 0; 9) – ДБР, соответствует угловой точке А (3; 5). Линейная функция F = 24 – Х3. В выражении отсутствуют положительные коэффициенты при неосновных переменных, значит критерий оптимальности выполнен, т.е. Х1 – оптим БР, Fмакс = 24. Однако в последнем выражении для F = 24 – Х3 отсутствует неосновная переменная Х4 (входит с нулевым к-ом), поэтому изменение этой переменной не приведет к изменению цел функции.

 

Вырожденность базисного решения:

Решим симплексным методом задачу:

F=2x1 - х2 à maxпри ограничениях:

х1 - х2 <= 2

 
3х1 - 2х2 <= 6

6х1 - 4х2 <= 14

х1, х2 >= 0

На первом шаге получим: осн пер – х3, х4, х5;

неос п - х1, х2.

Выражение основных через неосн:

Х3 = 2 - Х1 + Х2

Х4 = 6 – 3Х1 + 2Х2

Х5 = 14 – 6Х1 + 4Х2

Х1 = (0; 0; 2; 6; 14) – допустимое БР. Линейная функция F = 2x1 - х2. Переводя Х1 в основные, получаем Х1 = min{2; 6/3; 14/6} = 2. Оценочные отношения в первых двух совпадают. Любое выбираем.

 

На втором шаге получим: осн пер – х1, х4, х5;

неос п - х2, х3.

Выражение основных через неосн:

Х1 = 5 + Х2 – Х3

Х4 = 0 – Х2 + 3Х3

Х5 = 2 – 2Х2 + 6Х3

Х2 = (2; 0; 0; 0; 2) – вырожденное БР, т.к. осн переменная Х4 = 0. Линейная функция F = 4 + Х2 – 2Х3. Переводя Х2 в основные, получаем Х2 = min{¥; 0; 1} = 0, поэтому на следующем шаге изменения целевой функции не произойдет (0 * 1). Это нарушение принципа улучшения решения. Поэтому принцип – не ухудшить.

Следующий шаг данного примера тоже приведет к вырожденному БР. Этот шаг, хоть и не вызвал увеличения значения цел функции, привел к новому БР. Наличие «пустых» шагов может привести к «зацикливанию» - не рассматриваем.

Вывод:

Если на каком-либо шаге наибольшее возможное значение переменной достигается в нескольких уравнениях одновременно (совпадают их оценочные отношения), то разрешающее – любое из них. На очередном шаге получим вырожденное БР.

Отсутствие конечного оптимума:

Решим симплексным методом задачу:

F=2x1 - 3х2 + 1à min при ограничениях:

х1 + х2 >= 4

 
2х1 - х2 >= 1

F=0
х1 - 2х2 <= 1

х1, х2 >= 0

A
На очередном шаге получим: осн пер – х1, х2, х5;

B
неос п - х3, х4.

Выражение основных через неосн:

Х1 = 5/3 + 1/3 Х3 + 1/3 Х4

Х2 = 7/3 + 2/3 Х3 – 1/3 Х4

Х5 = 4 + Х3 – Х4

Х1 = (5/3; 7/3; 0; 0; 4) – допустимое БР. Линейная функция F = -8/3 - 4/3x3 + 4/3х4. Переводя Х3 в основные (т.к. имеет отрицательный коэффициент, а ищем мин), получаем Х3 = min{¥; ¥; ¥} = ¥, т.к. во все уравнения эта переменная входит со знаком свободного члена. Уравнения не ограничивают рост Х3, поэтому и целевая функция неограниченно убывает.

Вывод:

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

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

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

Линейное программирование

А х а х a nxn b... при n является плоскостью а при n gt ее обобщением в n мерном...

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

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

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

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

Линейное программирование
Оптимизационная задача была сформулирована в общем виде: найти переменные х1, х2, …, хп, удовлетворяющие системе неравенств (уравнений) φi

Понятие экономико-математической модели
Существует много различных определений понятия «модель», отличающихся друг от друга. Но это понятие знакомо каждому: игрушечный корабль – модель корабля, фотоснимок пейзажа, географическая карта –

Задача об использовании ресурсов (задача планирования производства).
Для изготовления двух видов продукции П1 и П2 используют три вида ресурсов Р1, Р2 и Р3. Известны запасы этих ресурсов В1, В2 и В3 и число единиц ресурсов, затрачиваемых на изготовление единицы кажд

Задача о раскрое материалов.
На раскрой (распил, обработку) поступает материал одного образца в количестве А единиц. Требуется изготовить из него L разных комплектующих изделий в количествах, пропорциональных числам b1, b2, …

Система m линейных уравнений с n переменными
Система m линейных уравнений с n переменными имеет вид:   а11*Х1 + а12*Х2 + …+ а1j*Xj + …+ а1n*Xn =

Геометрический смысл решений неравенств, уравнений и их систем
Теорема 1. Множество решений неравенства с двумя переменными а11х1 + а12х2 <= b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой а11х1 + а12х2 = b1, вкл

Является выпуклым многоугольником (или выпуклой многоугольной областью).
Каждое из неравенств в соответствии с теоремой 1 определяет одну из полуплоскостей, являющуюся выпуклым множеством точек (из математики: выпуклое множество точек – если оно вместе с любыми двумя св

Свойства задач ЛП
Выше в лекции по ЛП было показано, что любая задача ЛП м.б. представлена в виде общей, канонической или стандартной задачи. Причем, от одной задачи можно перейти к другой. Будем рассматрив

Геометрический метод решения задач ЛП
Итак, выше было доказано, что множество допустимых решений (многогранник решений) ЗЛП представляет собой выпуклый многогранник (или выпуклую многогранную область), а оптимальное решение задачи нахо

Симплексный метод
Выше были рассмотрены основные теоремы ЛП. Из них следует, что если ЗЛП имеет оптимальное решение, то оно соответствует хотя бы одной точке многогранника решений и совпадает хотя бы с одним из допу

Нахождение оптимума линейной функции
Пример: Решим симплексным методом задачу: F=2x1 + 3х2 à maxпри ограничениях: х1 + 3х2 &l

Симплексные таблицы
Практические расчеты с использованием симплекс метода – на компьютере. Если вручную, то используются симплекс-таблицы. Будем решать задачу на максимум. I. После введения добавочных перемен

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