Разделы

Авто
Бизнес
Болезни
Дом
Защита
Здоровье
Интернет
Компьютеры
Медицина
Науки
Обучение
Общество
Питание
Политика
Производство
Промышленность
Спорт
Техника
Экономика

Неограниченные решения

Некоторые задачи могут допускать бесконечное увеличение значений переменных без нарушения наложенных ограничений. Это говорит о том, что модель недостаточно точна:

· Не учтены одно или несколько ограничений, не являющихся избыточными;

· Не точно оценены параметры ограничений.

Пример: max Z = 2 х1 + х2

{ х1 - х2 ≤ 10 - (1) 2 х1 ≤ 40 - (2)

x1 , x 2 ≥ 0

Баз. Пер. Х1 х2 х3 х4 Решение
Z - 2 - 1
х3 - 1
х4

 

Если на некоторой итерации небазисная переменная имеет в ограничениях не положительные коэффициенты, то пространство решений, в данном направлении, не ограничено.

Если, кроме того,: коэффициент при это переменной в Z уравнении отрицателен (в задаче max) или положителен (в задаче min), то целевая функция так же не ограничена.

 

Пример: max Z = 6 х1 - 2 х2

{ 2 х1 - х2 ≤ 2 - (1) х1 ≤ 4 - (2)

x1 , x 2 ≥ 0

Баз. Пер. Х1 х2 х3 х4 Решение
Z - 6
х3 - 1
х4

 

Отсутствие допустимых решений

 

Раздел: Двойственная задача ЛП.

Тема: Взаимосвязь прямой и двойственной задачи.

Двойственная задача – это вспомогательная задача ЛП, которая формулируется с помощью определенных правил из условий прямой или исходной задачи, приведенной к стандартной форме.

Исходную задачу, приведенную к стандартной форме, можно записать в общем виде:

  max Z = C1X1 + C2X2 + … + CnXn
  (min)
{ a11x1 + a12x2 + … + а1nxn = b1 ( у1)
a21x1 + a22x2 + … + а2nxn = b2 (у)2
am1x1 + am2x2 + … + аmnxn = bm (у)m

В состав n переменных xj входят остаточные и избыточные переменные.

Max(min) Z=

 

При ограничениях i=1,2,…m

xj>=0 j=1,2…n

 

Двойственная задача формулируется по следующим правилам:

· Каждому ограничению прямой задачи соответствует переменная двойственной задачи.

· Каждой переменной прямой задачи соответствует ограничение двойственной задачи.

· Правые части ограничений становятся коэффициентами целевой функции двойственной задачи.

 

Направление оптимизации, ограничения и знаки запишем в виде таблицы:

 

Прямая задача Двойственная задача
Целевая функция Целевая функция Ограничения Переменные
max min Не ограничены в знаке
min max Не ограничены в знаке

 

Двойственная задача:

Min(max) W=

При ограничениях i=1..m j=1..n

yi не огранич. в знаке

 

Между прямой и двойственной задачами существует тесная взаимосвязь. Оптимальное решение одной из задач можно получить из данных симплекс-таблицы для оптимального решения другой задачи.

Трудоемкость вычислений при решении задач зависит в большей степени от числа ограничений, чем от количества переменных, поэтому если в двойственной задаче ограничений меньше, то целесообразней решать ее, а полученный результат использовать для нахождения оптимального решения прямой задачи.

 

Пример: max Z = 5 х1 + 12 х2 + 4 х3

 

{ х1 + 2 х2 + х3 ≤ 10 - (1) 2 х1 - х2 + 3 х3 = 8 - (2)

x1 , x2 , x 3 ≥ 0

 

max Z = 5 х1 + 12 х2 + 4 х3 + 0 х4 - MR

 

{ х1 + 2 х2 + х3 + х4 = 10 - (1) 2 х1 - х2 + 3 х3 + R = 8 - (2)

x1 , x2 , x 3, x4 , R ≥ 0

 

Оптимальное решение:

Баз. Пер. Х1 х2 х3 х4 R Решение
Z 3/5 29/5 - 2/5 + М 274/5
Х2 - 1/5 2/5 - 1/5 12/5
Х1 7/5 1/5 2/5 26/5

 

Двойственная задача:

min w = 10 y1 + 8 y2

 

{ y1 + 2 y2 ≥ 5 - (1) 2 y1 - y2 ≥ 12 - (2) y1 + 3 y2 ≥ 4 - (3) y1 + 0 y2 ≥ 0 - (4) 0 y1 + y2 ≥ - M - (5)

y1 ≥ 0, , y2 – не ограничен в знаке

 

y2 = y 2’- y2

 

Баз. Пер. y1 y2 y2 Y3 х4 х5 R1 R2 R3 Решение
Z             26/5 - М 12/5 - М - М 274/5
Y5             7/5 - 1/5 - 1 3/5
y2             - 2/5 1/5 2/5
y1             1/5 2/5 29/5

 

y2 = 0 – 2/5 = - 2/5; y 1 = 29/5; w = 274/5;

 

1) max Z = min w = 274/5 , то есть значения целевых функций совпадают;

2) коэффициент при начальной базисной переменной в оптимальном Z уравнении прямой задачи равен разности между левой и правой частями ограничений двойственной задачи, соответствующих данной переменной.

29/5 = y1 – 0; y 1 = 29/5

-2/5 + М = y2 + М; y 2 = - 2/5;

 

Оптимальное решение прямой задачи можно определить из симплекс-таблицы для оптимального решения двойственной задачи. Двойственная задача к двойственной есть ни что иное, как прямая задача.

 

Тема: Двойственный симплекс-метод.

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

Например, min z=2x1+x2

 

3x1+x2>=3

4x1+3x2>=6

x1+2x2<=3

x1,x2>=0

 

Преобразуем все ограничения в неравенства со знаком <=, умножив правую и левую части на (-1). Решение становится недопустимым. Приведем к стандартной форме, введя остаточные переменные.

-3x1-x2+x3=-3

-4x1-3x2+x4=-6

x1+2x2+x5=3

x1,x2,x3,x4,x5>=0

 

 

min z-2x1-x2=0

 

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

 

Баз. Пер. Х1 х2 х3 х4 х5 Решение
Z -2 -1
Х3 -3 -1 -3
Х4 -4 -3 -6
Х5

 

Условие допустимости:

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

Условие оптимальности:

Выбор включаемой переменной производится следующим образом. Вычисляются отношения коэффициентов z-строки к отрицательным коэффициентам исключаемой строки. В задаче min выбирается минимальное отношение, в задаче max - наибольшее отношение. При наличии альтернатив выбор делается произвольно. Если в отношениях все знаменатели положительные или нулевые, задача не имеет допустимых решений.

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

Итак,

X4 – исключаемая переменная

X2 – включаемая переменная.

Оптимальное решение:

Баз. Пер. Х1 х2 х3 х4 х5 Решение
Z -2/5 -1/5 12/5
Х1 -3/5 1/5 3/5
Х2 4/5 -3/5 6/5
Х5 -1

 

Полученное решение является и оптимальным и допустимым.

 

Матричные вычисления.

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

Пример: max Z = 5 х1 + 12 х2 + 4 х3

 

{ х1 + 2 х2 + х3 ≤ 10 - (1) 2 х1 - х2 + 3 х3 = 8 - (2)

x1 , x2 , x 3 ≥ 0

Начальная симплекс-таблица:

Баз. Пер. Х1 х2 х3 х4 R Решение
Z -5 -12
Х4
R -1

 

Оптимальное решение прямой задачи:

Баз. Пер. Х1 х2 х3 х4 R Решение
Z 3/5 29/5 - 2/5 + М 274/5
Х2 - 1/5 2/5 - 1/5 12/5
Х1 7/5 1/5 2/5 26/5

 

Вычисления, связанные с определением новых значений элементов симплекс-таблицы, можно разделить на два типа:

1. вычисление столбцов коэффициентов ограничений;

2. вычисление коэффициентов строки, соответствующей целевой функции.

 

1. столбец на итерации i=обратная матрица на итерации i*столбец исходной модели

Например, x1 столбец в опт. реш.=

 

Или столбец решение в опт. табл.=

 

2. z-коэф-т при xj=, т.е. равен разности между левой и правой частями соответствующего ограничения двойственной задачи.

Значения двойственных переменных yi на любой итерации:

, где Сi – вектор-строка исходных коэффициентов целевой функции при базисных переменных прямой задачи

A-1 – обратная матрица.

Например,

z-коэффициент при x1=y1+2y2-5

z-коэффициент при x2=2y1-y2-12

z-коэффициент при x3=y1+3y2-4

z-коэффициент при x4=y1-0

z-коэффициент при R=y2+M

В оптимальном решении

 

z-коэффициент при x1=y1+2y2-5=29/5+2*(-2/5)-5=0

.

.

.

 

z-коэффициент при R=y2+M=-2/5+M

 

Тема: Анализ построенной математической модели на чувствительность с использованием обратной матрицы и соотношений двойственности.

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

 

Пример: Прямая задача: max Z = 3 х1 + 2 х2

 

{ х1 + 2 х2 ≤ 6 - (1) 2 х1 + х2 ≤ 8 - (2) - х1 + х2 ≤ 1 - (3) х2 ≤ 2 - (4)

x1 , x2 ≥ 0

 

Баз. Пер. Х1 х2 х3 х4 х5 Х6 Решение
Z 1/3 4/3 38/3
Х2 2/3 - 1/3 4/3
Х1 - 1/3 2/3 10/3
Х5 - 1
Х6 - 2/3 1/3 2/3

 

Двойственная задача: min w = 6 y1 + 8 y2 + y3 + 2 y4

 

{ y1 + 2 y2 - y3 ≥ 3 - (1) 2 y1 + y2 + y3 + y4 ≥ 2 - (2)

y1 , y2 , y3 , y4 ≥ 0

 

 

 

Тема: Изменения условия задачи, влияющие (меняющие) на допустимость

1. Изменение правых частей

Предположим, запас исходного продукта А увеличен с 6 до 7 тонн.

 

( Х2 )          
Х1 = ( обратн. матрица )х( Исходн столбец )
Х5
Х6          
( 2/3 - 1/3 )*( )=( )
- 1/3 2/3
-1
- 2/3 1/3

 

Z = 3 * 3 + 2 * 2 = 13

 

Предположим, что максимальный суточный запас исходных продуктов составляет не 6 и 8, а 7 и 4 тонны.

 

( 2/3 - 1/3 )*( )=( 10/3 )
- 1/3 2/3 1/3
-1 - 2
- 2/3 1/3 - 4/3

 

Z = 3* (1/3) + 2 * (10/3) = 23/3

 

Баз. Пер. Х1 х2 х3 х4 х5 Х6 Решение
Z 1/3 4/3 23/3
Х2 2/3 - 1/3 10/3
Х1 - 1/3 2/3 1/3
Х5 - 1 - 2
Х6 - 2/3 1/3 - 4/3

 

Полученное решение недопустимо, поэтому воспользуемся двойственным симплекс-методом, чтобы получить допустимое решение.

 

После применения двойственного метода получим допустимое решение

x1 = 1 ; x2 = 2 ; Z = 7 ;

 

2. Добавление нового ограничения

 

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

 

а) x1 ≤ 4 – новое ограничение (x1 = 10/3 , x2 = 4/3)

Выполняется при текущем решении;

б) x1 ≤ 3 – новое ограничение

Не выполняется при текущем решении;

 

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

 

x1 + x7 = 3 ; x7 ≥ 0

x1 – уравнение из оптимальной симплекс-таблицы:

x1 - (1/3) x3 + (2/3) x4 = 10/3

x1 = 10/3 + (1/3) x3 - (2/3) x4

(1/3) x3 - (2/3) x4 + x7 = - 1/3

 

 

Баз. Пер. Х1 х2 х3 х4 х5 Х6 х7 Решение
Z 1/3 4/3 38/3
Х2 2/3 - 1/3 4/3
Х1 - 1/3 2/3 10/3
Х5 - 1
Х6 - 2/3 1/3 2/3
Х7 1/3 - 2/3 - 1/3

 

 

После применения двойственного симплекс-метода получаем допустимое решение: x1 = 3 ; x2 = 3/2 ; Z = 12 ;

 

! Добавление нового связывающего ограничения не может улучшить значения целевой функции.

 

Тема: Изменения условий задачи, влияющие на оптимальность решения

1. Изменение коэффициентов целевой функции

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

 

Пример: а) max Z = 3 х1 + 2 х2 изменяем на Z = 5 х1 + 4 х2

 

1, у2, у3, у4) = (коэффициенты при баз. перемен-х) х (обратн. матрица) =

 

  ( 2/3 - 1/3 )  
= (4; 5; 0; 0;) х - 1/3 2/3 = (1; 2; 0; 0)
- 1
  - 2/3 1/3  

 

Баз. Пер. Х1 х2 Х3 х4 х5 Х6 Решение
Z

 

б) Z = 4 х1 + х2

  ( 2/3 - 1/3 )  
1, у2, у3, у4) = (1; 4; 0; 0;) х - 1/3 2/3 = (-2/3; 7/3; 0; 0)
- 1
  - 2/3 1/3  

 

Баз. Пер. Х1 х2 Х3 х4 х5 Х6 Решение
Z - 2/3 7/3 44/3

 

Баз. Пер. Х1 х2 Х3 х4 х5 Х6 Решение
Z - 2/3 7/3 44/3
Х2 2/3 - 1/3 4/3
Х1 - 1/3 2/3 10/3
Х5 - 1
Х6 - 2/3 1/3 2/3

 

После применения обычного симплекс-метода получим оптимальное решение : x1 = 4 ; x2 = 0 ; Z = 16 ;.

 

2. Добавление нового вида производственной деятельности

Производится более дешевый вид краски для наружных работ, требующий по ¾ тонны исходных продуктов А и Б на 1 тонну конечного продукта. Прибыль, получаемая от реализации 1 тонны новой краски равна 3/2 денежных единиц.

 

Пример: Прямая задача: max Z = 3 х1 + 2 х2 + (3/2) х7

 

{ х1 + 2 х2 + (3/4) х7 ≤ 6 - (1) 2 х1 + х2 + (3/4) х7 ≤ 8 - (2) - х1 + х2 - х7 ≤ 1 - (3) х2 ≤ 2 - (4)

x1 , x2 , х7 ≥ 0

 

Составим ограничение двойственной задачи, соответствующее переменной х7 :

х7 : (3/4) у1 + (3/4) у2 – у3 ≥ 3/2

В исходной таблице х рассматривается как небазисная переменная, поэтому двойственные оценки останутся неизменными

1, у2, у3, у4) = (1/3; 4/3; 0; 0)

 

(столбец при х7 в опт реш) = (обратн матрица) х (коэффициенты при х7) =

 

  ( ¾ )=( ¼ )
= (обр матрица) х ¾ ¼
- 1 -1
  - ¼

 

Обычный симплекс-метод:

Баз. Пер. Х1 х2 х3 х4 х5 Х6 х7 Решение
Z 1/3 4/3 - ¼ 38/3
Х2 2/3 - 1/3 ¼ 4/3
Х1 - 1/3 2/3 ¼ 10/3
Х5 - 1 - 1
Х6 - 2/3 1/3 - 1/4 2/3

 

x1 = 2 ; x2 = 0 ; x7 = 16/3 ; Z = 14 ;.

! Включение в модель нового вида производств. деятельности может улучшить значение целевой функции.

 

Раздел: Транспортная модель

Тема: Методы получения начального решения

Транспортная модель используется для представления наиболее экономичного плана перевозки одного вида продукции из нескольких исходных пунктов в пункты назначения.

Для построения транспортной модели используются следующие величины:

· Объем производства в каждом исходном пункте аi ;

· Спрос в каждом пункте назначения bj ;

· Стоимость перевозки единицы продукции из каждого исходного пункта в каждой пункт назначения cij ;.

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

m n

min Z = Σ Σ Cij xij

i=1 j=1

{ n Σ хij ≤ ai j=1 m Σ хij ≥ bj i=1

xij ≥ 0

 

Транспортная задача называется сбалансированной или закрытой, если суммарный объем производства равен суммарному спросу:

m n

Σ ai = Σ bj

i=1 j=1

Тогда в ограничениях знаки неравенства меняются на знаки равенства:

{ n Σ хij =ai j=1 m Σ хij = bj i=1

 

Сбалансированность модели является обязательным условием для применения специальных методов решения транспортной задачи.

Транспортная модель может быть представлена с помощью транспортной таблицы, строки которой соответствуют исходным пунктам, столбцы – пунктам назначения, коэффициенты Сij располагаются в правом верхнем углу каждой ячейки.

 

  b1 b2
a1 x11 c11 x12 c12
   
a2 x21 c21 x22 c22
   

 

 

Пример: В исходных пунктах имеются запасы продукции 90, 400 и 110 тонн. Потребители должны получить продукт в количестве 140, 300, 160 тонн. Найти такое распределение груза, чтобы затраты на перевозку были минимальными, если матрица затрат имеет вид:

 

C = ( )

3 3

Σ ai = Σ bj = 600

i=1 j=1

  b1 b2 b3 Объем
a1        
       
a2        
       
a3        
       
спрос  
                     

min Z = 2 х11 + 5 х12 + 2х13 + 4х21 + х22 + 5х23 + 3х31 + 6х32 + 8х33

{ х11 + х12 + х13 = 90 х21 + х22 + х23 = 400 х31 + х32 + х33 = 110 х11 + х21 + х31 = 140 х12 + х22 + х32 = 300 х13 + х23 + х33 = 160

xij ≥ 0

 

В данном случае задача сбалансирована, т.е. сумма объемов производства равна сумме спросов: 90+400+110=140+300+160=600. Если задача не сбалансирована, вводятся дополнительные фиктивные исходные пункты или пункты назначения, куда распределяется избыток или недостаток продукции. Т.к. пункт фиктивный, то стоимость перевозки берется, равной 0.

 

Специальные методы решения транспортной задачи повторяют шаги симплекс-алгоритма:

· Нахождение начального допустимого решения или опорного плана.

· Проверка его на оптимальность

· Нахождение нового решения, если решение не оптимально.

 

Нахождение начального допустимого решения можно осуществить тремя способами:

· Правило северо-западного угла

· Метод минимальной стоимости

· Приближенный метод Фогеля

 

Дата публикации:2014-01-23

Просмотров:433

Вернуться в оглавление:

Комментария пока нет...


Имя* (по-русски):
Почта* (e-mail):Не публикуется
Ответить (до 1000 символов):







 

2012-2018 lekcion.ru. За поставленную ссылку спасибо.