Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Решение двойственной задачи




 

В данном параграфе мы рассмотрим пример решения двойственной задачи, основанный на теореме о равновесии (теорема 5.3).

Пример 4.2. 1. Решить общую задачу линейного программирования.
2. Составить и решить двойственную задачу, используя теорему о равновесии.

 

z (X) = – 5 x 1 + 3 x 2 + 5 x 3 – 7 x 4 ® max, (4.15)

2 x 1 + x 2 + x 3 + 3 x 4 ³ – 3,

2 x 1 + 3 x 2 + 4 x 3 + 2 x 4 £ 3, (4.16)

x 1 + 2 x 2 + 2 x 3 x 4 = 4,

x 2, x 3, x 4 ³ 0.

 

Решение. Для удобства составления двойственной задачи и решения основной задачи добьемся того, чтобы все ограничения задачи на максимум были равенствами или неравенствами вида £. Для этого умножим первое неравенство системы (4.16) на – 1. Мы приходим к задаче:

 

z (X) = – 5 x 1 + 3 x 2 + 5 x 3 – 7 x 4 ® max, (4.17)

– 2 x 1 x 2x 3 – 3 x 4 £ 3,

2 x 1 + 3 x 2 + 4 x 3 + 2 x 4 £ 3, (4.18)

x 1 + 2 x 2 + 2 x 3x 4 = 4,

x 2, x 3, x 4 ³ 0.

 

1. Для решения задачи (4.17) – (4.18) методом Штифеля введем в первое и во второе ограничения системы (4.18) добавочные переменные y 1³ 0 и y 2³ 0.

y 1 = 2 x 1 + x 2 + x 3 + 3 x 4 + 3,

y 2 = – 2 x 1 – 3 x 2 – 4 x 3 – 2 x 4 + 3, (4.19)

0 = x 1 – 2 x 2 – 2 x 3 + x 4 + 4,

y 1, y 2, x 2, x 3, x 4 ³ 0.

 

Таким образом, задачу (4.17), (4.19) можно записать в виде жордановой таблицы 4.12:

 

 

  x 1 x 2 x 3 x 4       x 2 x 3 x 4  
y 1 –2 –1 –1 –3     y 1 –5 –5 –1 –5
y 2             y 2        
  –1     –1     x 1 –2 –2   –4
z   –3 –5       z        

Табл. 4.12. Табл. 4.13.

 

Заметим, что числа, составляющие первые три строки таблицы 4.12, совпадают с числами, образующими основную матрицу системы (4.18). Последняя строка таблицы состоит из коэффициентов функции цели (4.18), взятых с противоположным знаком. Таким образом, первоначальная жорданова таблица мола быть составлена сразу из условия исходной задачи (4.17) – (4.18).

На первом шаге метода Штифеля выберем в качестве разрешающего элемента элемент а 31 = – 1. При этом неограниченная на знак свободная переменная x 1 меняется с базисной переменной 0. После первого шага из таблицы можно вычеркнуть столбец, верхний заглавный элемент которого равен нулю (первый столбец). Строку, соответствующую неограниченной на знак переменной x 1, можно, предварительно запомнив, исключить из таблицы.

После первого шага мы приходим к таблице 4.13. В крайнем правом столбце таблицы 4.13 имеется отрицательное число а 14 = – 5. Следовательно, базисное решение, соответствующее данной таблице, не является опорным планом задачи (4.17), (4.19). Для того чтобы попытаться войти в область планов задачи, нужно найти в первой строке таблицы 4.13 отрицательное число (например, а 13 = – 1) и выбрать разрешающий элемент в столбце, содержащем данный отрицательный элемент (в данном случае – это третий столбец).

Разрешающий элемент в третьем столбце выбираем по принципу минимального симплексного отношения. В данном случае минимальное симплексное отношение соответствует как раз элементу а 13 = – 1. Дело в том, для второго оставшегося элемента а 23 = 0 симплексное отношение вообще не определено. Выбирая в таблице 4.13 в качестве разрешающего элемента а 13 = – 1, после одного шага метода Штифеля, мы приходим к таблице 4.14:

 

 

  x 2 x 3 y 1   ti 2     x 2 x 4 y 1  
x 4     –1       x 3   1/5 –1/5  
y 2         11/8   y 2 –1 –8/5 8/5  
z –3 –5         z        

Табл. 4.14. Табл. 4.15.

 

Из таблицы 4.14 видно, что соответствующее ей базисное решение уже является опорным планом задачи (т.к. свободные члены b 1 = 5 и
b 2 = 11 не являются отрицательными числами). Но наличие отрицательных оценок свободных переменных говорит о том, что данный опорный план не является оптимальным. Сделаем еще один шаг метода Штифеля. Выберем для поиска разрешающего элемента второй столбец, соответствующий наименьшей отрицательной оценке – 5.

Для чисел а 12 = 5 и а 22 = 8 вычислим симплексные отношения и запишем их в правый дополнительный столбец таблицы 4.14:

 

 

Минимальное симплексное отношение приходится на первую строку. Поэтому в качестве разрешающего элемента нужно выбрать элемент а 12 = 5. После пересчета мы приходим к таблице 4.15. Все оценки свободных переменных в таблице 4.15 строго больше нуля. Следовательно, мы получили оптимальный опорный план, и этот план является единственным.

Некоторые компоненты оптимального плана и добавочные переменные y 1 и y 2 находятся из таблицы 4.15.

как свободные переменные.

– значения базисных переменных.

При этом максимум функции цели находится в правом нижнем углу таблицы:

 

.

 

Значение переменной найдем из запомненной ранее третьей строки таблицы 4.13:

 

.

 

Таким образом, мы нашли решение исходной задачи (4.15) – (4.16):

 

.

 

2. Составим задачу, двойственную к исходной задаче (4.17) – (4.18). Мы получим следующую задачу на минимум:

 

g (Y) = 3 y 1 + 3 y 2 + 4 y 3 ® min, (4.20)

– 2 y 1 + 2 y 2y 3 = – 5,

y 1 + 3 y 2 + 2 y 3 ³ 3,

y 1 + 4 y 2 + 2 y 3 ³ 5, (4.21)

– 3 y 1 + 2 y 2y 3 ³ – 7,

y 1, y 2 ³ 0.

 

Обозначим через – оптимальный опорный план двойственной задачи (4.20) – (4.21) воспользуемся теоремой о равновесии.

1. Подставим координаты оптимального опорного плана в систему ограничений (4.18):

Так как второе ограничение превратилось в строгое неравенство, то соответствующая компонента оптимального опорного плана двойственной задачи равна нулю (). Осталось найти компоненты и . Для этого воспользуемся второй частью теоремы о равновесии.

2. Так как третья компонента оптимального опорного плана строго больше нуля (), то соответствующее (третье) ограничение двойственной задачи, при подстановке в него компонент оптимального плана , обратится в равенство. Данное равенство вместе с первым ограничением (которое само по себе является равенством) дают нам систему линейных уравнений для нахождения и :

 

(4.22)

Подставляя в систему (4.22) уже найденное значение , получим систему двух уравнений с двумя неизвестными:

(4.23)

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

.

ПРИЛОЖЕНИЯ

 

Контрольное задание №1. Вычислить ранг матрицы.

 

1. .   2. .  
3. .   4. .  
5. .   6. .  
7. .   8. .  
9. .   10. .  
11. .     12. .  
13. .     14. .  
15. .     16. .  
17. .     18. .  
19. .     20. .  

 

 

Контрольное задание №2. Найти общее решение системы линейных уравнений.

 

 

1.   2.  
3.   4.  
5.   6.  
7.   8.  
9.   10.  
11.   12.  
13.   14.  
15. 16.  
17.  
18.   19.  

 

Контрольное задание №3. Дана общая задача линейного программирования. Требуется: 1) решить задачу методом Штифеля; 2) составить и решить двойственную задачу, используя теорему о равновесии.

 

   
   
 
 
 
 
 

 

 

ЛИТЕРАТУРА

 

Основная

 

1. Замбицкий Д.К. Линейная алгебра и линейное программирование: Учеб. пособие / Д.К. Замбицкий, М.К. Замбицкий. – Кишинэу: Еврика, 1997. – 200 с.

2. Зуховицкий С. И. Линейное и нелинейное программирование / С. И. Зуховицкий, Л.И. Авдеева. – М.: Наука, 1967. – 352 с.

3. Полунин И.Ф. Курс математического программирования / И.Ф. Полунин. – Минск: Вышэйш. шк., 1968. – 253 с.

4. Полунин И.Ф. Курс математического программирования: Для с.-х. вузов по спец. «Экономика и организация сельского хоз-ва», «Бухгалтерский учет в сельском хоз-ве» и «Экономика и организация водного хоз-ва» / И.Ф. Полунин. – 3-е изд., доп. – Минск: Вышэйш. шк., 1975. –
380 с.

5. Полунин И.Ф. Курс математического программирования: Для с.-х. вузов по спец. «Экономика и организация сельского хоз-ва» и «Бухгалтерский учет в сельском хоз-ве» / И.Ф. Полунин. – Минск: Вышэйш. шк., 1970. – 318 с.

 

Дополнительная

 

1. Зуховицкий С. И. Линейное и выпуклое программирование / С.И. Зуховицкий, Л.И. Авдеева. – 2-е, изд. переработ. и доп. – М.: Наука, 1967. – 360 с.

2. Полунин И.Ф. Математическое программирование в землеустройстве: Учеб. пособие для землеустроит. фак. с.-х. вузов / И.Ф. Полунин. – Минск: Вышэйш. шк., 1968. – 253 с.

3. Еремин И.И. Теория линейной оптимизации / И.И. Еремин; Отв. ред. Л.Д. Попов; РАН. УРО. Ин-т математики и механики. – Екатеринбург, 1999. – 312 с.

 

Составитель ст. преп. Уксусов Сергей Николаевич

Редактор Тихомирова О.А.

 

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...