2.06M

Категория: $Математика$ Математика

Похожие презентации:

Двойственные задачи линейного программирования

Двойственные задачи ЛП

Построение двойственной задачи

Двойственные задачи линейного программирования. Лекция 3

Задачи линейного программирования

Прямая и двойственная задачи и их решение симплекс-методом

Задачи линейного программирования

Линейное программирование. Задачи

Задачи линейного программирования (двойственность)

2.

План
1. Задача линейного программирования
2. Постановка задачи
3. Экономическая интерпретация
двойственной задачи
4. Математическая модель двойственной
задачи
5. Примеры

Задача линейного программирования имеет вид
c1 x1 ... c n x n extr
a11 x1 ... a1n x n b1 ,
a m1 ,1 x1 ... a m1 ,n x n bm1 ,
a m1 1,1 x1 ... a m1 1,n x n bm1 1 ,
a m1 x1 ... a mn x n bm ,
x1 0,..., x m 0,
где c1 ,…, c п , аij , b1 ,…, bm - заданные числа, причем bi 0 , i 1,..., m .

4.

Введем
c (c1 ,..., c n ) ,
x ( x1 ,..., x n ) ,
b (b1 ,..., bm ) ,
векторы
Aij (a1 j ,..., a mj ) - j -й столбец матрицы А {a ij } . Условно считают х 0
, если хi 0 , i 1,..., n .
Множество
ограничений
задачи
линейного
программирования задает многогранник в пространстве R n . Если
задача линейного программирования имеет решение, то хотя бы
одно из них находится среди вершин многогранника.
Поэтому решение задачи линейного программирования
сводится к перебору этих величин, причем к «разумному»
перебору: если имеется какая-то вершина, то сначала узнают с
помощью критерия оптимальности не является ли она решением,
если нет, то строят новую вершину, в которой значение функции
цели f 0 ( x) c, x будет меньше (при решении задачи на min), чем в
старой вершине.

5.

Прежде всего от задачи с неравенствами введением
дополнительных переменных переходят к задаче с равенствами.
Делается это просто:
если a11 x1 ... a1n xn b1 , то a11 x1 ... a1n xn хп 1 b1 , х п 1 0 ;
если же a k1 x1 ... a kn xn bk , то a k1 x1 ... a kn xn xп k bk , х п k 0
( m1 1 k m ).

6.

Будем считать, что к равенствам перешли и задача имеет вид
f 0 ( x) c, x min
a11 x1 ... a1n x n b1 ,
a m1 x1 ... a mn x n bm ,
x 0.
(s)
Заметим, что теперь систему равенств можно записать
компактно через векторы A j :
x1 A 1 ... x n A n b .
(1)

7.

С каждым вектором x свяжем вектор
положительных координат:
I (x)
индексов его
I ( x) i : xi 0 .
Равенство (1) можно записать так
b x j A j .
j I ( x )
Решение x системы (s) называется базисным решением, если
векторы
A : j I ( x)
j
образуют линейно-независимую систему.

8.

Строка s i системы (s) называется базисной, если она
содержит какую-то переменную с коэффициентом 1, которой нет
во всех остальных строках.
Задача называется задачей с базисом, если все ее строки
являются базисными.

9.

Пример.
x1 2 x 2 min
2 x1 x 2 4 x3 x 4 10,
x 2 x x 12,
1
3
5
4 x1 x3 2 x 4 x6 8,
x 0.
Это – задача с базисом. В первой строке имеем x2 , во второй
- x 5 и в третьей - x 6 . Базисное решение x 0 (0,10,0,0,12,8) .

10.

Если имеем задачу, не являющуюся задачей с базисом, то
сначала создают новую задачу с базисом. Делается это так. В
каждую небазисную строку искусственно добавляют свою новую
переменную, которая с коэффициентом М ( М достаточно большое
число) добавляется и к функции цели f 0 ( x) c, x .
Пример. От задачи
x1 2 x 2 min
2 x1 x 2 x3 20,
x 2 x 10,
1
2
2 x1 x 2 16,
x 0.
перейти к задаче с базисом.

11.

Решение. Первая строка имеет базисную переменную x3 . Их
нет во второй и третьей строках.
Новая задача (н.з.) выглядит так:
x1 2 x 2 Мх 4 Мх 5 min
2 x1 x 2 x3 20,
x 2 x x 10,
1
2
4
2 x1 x 2 x5 16,
x 0.
Теперь х ( x1 , x2 , х3 , х4 , х5 ) .
Такой подход называется методом искусственного базиса.

12.

Мы имеем две задачи: исходную (и.з.) и новую (н.з.). Их
решения связаны следующим образом.
Если функция f 0 не ограничена снизу ( f 0 min ) в (н.з.), то
f 0 min и в (н.з.).
Пусть хопт ( x1 ,..., хп р ) оптимальное решение (н.з.). Возможны
два варианта:
Возможны два варианта:
v1) все искусственные переменные хп 1 ,…, хп р равны нулю.
Тогда хопт ( x1 ,..., хп ) - решение (н.з.);
v2) хотя бы одна искусственная переменная отличается от
нуля. Тогда система (s) (н.з.) не имеет решений.

13.

Ответ на второй вопрос – критерий оптимальности. Пусть
имеется базисное решение x , соответствующее базисным
столбцам j1 ,..., j m .
Пусть с Б (с j ,..., c j ) .
1
m
Числа ock ock ( x) c Б , A k - ck называется оценками базисного
решениях.
Базисное решение x будет оптимальным тогда и только
тогда, когда среди оценок этого решения не будет положительных.

14.

Назовем столбы с положительными оценками плохими, а
другие хорошими. Критерий оптимальности звучит теперь так:
базисное решение x тогда и только тогда будет оптимальным,
когда все столбцы являются хорошими. Плохой столбец можно
сделать хорошим, его включить в базис. Так в симплексном методе
и делают.
Плохой столбец включается в базис следующим образом.
Пусть плохой столбец имеет номер j . Составляем отношения:
bi
, aij 0
aij
(2)
и выбираем из них наименьшее отношение. Пусть это есть bk a kj .

15.

Выберем в качестве главного элемента в методу Гауса –
Жордана akj . В примере ниже этот элемент всегда берется в рамку.
Применяем преобразование Гаусса-Жордана:
- делим k -ую на akj : bk bk ; a ki a ki , i 1,..., n (очевидно, a kj 1 )
a kj
a kj
- если l k , то
bl bl bk ( alj ) ; ali ali a ki ( alj ) ,
i 1,..., n
(очевидно, что alj alj a kj ( alj ) 0 ).
Если ~x новое базисное решение, то будет c, ~x c, x .

16.

Замечание 1. Если (2) применить нельзя, т. е. alj 0 для
любого j , то отсюда следует, что f 0 ( x) ограничена снизу, f 0 min .
Замечание 2. Задачу c, x max решают переходом к задаче
на минимум
c, x min .
Замечание 3. Когда число переменных п 2 , то задачу
линейного программирования удобно решать графически.

17.

Пример 1. x1 x2 min
x1 2 x 2 8,
2 x x 8,
1
2
x1 x 2 2,
x 0.
Решение. Графический метод.
(s)

18.

Шаг 1. Изображаем на плоскости x1Оx 2 область D - множество
решений системы (s).
Рисуем три прямые
x1 2 x 2 8 , 2 x1 x 2 8 , x1 x 2 2
и отбираем требуемые полупространства.

19.

Шаг 2. Изобразим вектор с ( 1, 1) - направление роста
функции f 0 ( x) . Пунктирная линия l с .
Из рисунка следует, что
x min (2) (1)
Шаг 3. Решим систему из уравнений 1 и 2, чтобы получить
координаты точки xmin
x1 2 x 2 8,
2 x1 x 2 8,
8
16
8 8
x min , , f 0 min 2 .
3
3
3 3
Решим задачу симплексным методом.

20.

Шаг 1. Подготовка задачи.
а) переход к равенствам
x1 x 2 min
x1 2 x 2 x3 8,
2 x x x 8,
1
2
4
x1 x 2 x5 2,
x 0.

21.

б) создание искусственного базиса. Третья строка – не
базисная. В качестве М берем 100 (можно взять и 1000; это на
решение не влияет)
x1 x 2 100 x6 min
x1 2 x 2 x3 8,
2 x x x 8,
1
4
2
x1 x 2 x5 ( x6 ) 2,
x 0.

22.

Шаг 2. Составим симплекс таблицу. Таблица содержит
разъясняющую обозначения. Само решение сводится к
преобразованиям Гаусса-Жордана до тех пор пока не встретится
плохой столбец без положительных элементов (см. замечание 1
(выше)) или пока все столбцы не станут хорошими.

23.

C
-1
-1
0
0
0
100
b x
x1
x2
x3
x4
x5
x6
0
8
1
2
1
0
0
0
0
8
2
1
0
1
0
0
100
2
1
1
0
0
-1
1
200
101
101
0
0
-100
0
0
6
0
1
1
0
1
-1
0
4
0
-1
0
1
2
-2
-1
2
1
1
0
0
-1
-1
-2
0
0
0
0
1
0
4
0
3/2
1
-1/2
0
0
2
0
-1/2
0
1/2
1
-1
4
1
1/2
0
1/2
0
-4
0
1/2
0
-1/2
0
-1
8/3
0
1
2/3
-1/3
0
0
10/3
0
0
1/3
1/3
1
-1
8/2
1
0
-1/3
2/3
0
-16/3
0
0
-1/3
-1/3
0
CБ
Комментарий
Исходная
табл.
Таблица1
Таблица 2
Таблица 3
-

24.

В исходной таблице x 0 (0,0,8,8,0,2) . C Б (0,0,100 ) - координаты c j
находящиеся в строке C над базисными столбцами.
В столбце b после горизонтальной черты получаются
значения f 0 ( x 0 ) , f 0 ( x1 ) ,…
Под чертой далее приведены оценки базисного решения по
столбцам.
Для x 0 получились два плохих столбца А 1 , А 2 . Включим в
базис А 1 . Отношения 8 , 8 , 2 .
1
2
1

25.

Для таблицы 1 базисное решение
x1 (2,0,6,4,0,0) .
Искусственное решение в исходной таблице было х6 2 , в
таблице 1 оно равно 0. Далее столбец этой переменной можно не
заполнять.
С Б (0,0, 1) .
Плохой столбец А 5 .

26.

В таблице 2 базисное решение x 2 (4,0,4,0,2) ; С Б (0,0, 1) .
Плохой столбец А 2 .
В таблице 3 базисное решение x 3 ( 8 , 8 ,0,0, 10 ) ; С Б ( 1,0, 1) .
3 3
3
Среди оценок нет положительных – все столбцы хорошие
8 8
10
хопт x 3 ( , ,0,0, ) .
3 3
3
Как отмечалось, искусственная переменная х6 0 . Значит, в
исходной задаче хопт ( 8 , 8 ) , f 0 min 16 .
3 3
3

27.

С каждой задачей линейного
программирования тесно связана другая
линейная задача, называемая
двойственной к исходной.
Пусть дана задача ЛП.
Максимизировать линейную функцию
c1 x1 ... c n x n extr
(1)

28.

При ограничениях
(2)
где c1 ,…, c п , аij , b1 ,…, bm - заданные числа, причем bi 0 , i 1,..., m .
Или в матричном виде

29.

Двойственная к ней задача
формулируется следующим образом
Минимизировать линейную
функцию
(3)
при ограничениях

30.

(4)
или в матричном виде

31.

Задачи (1), (2) и (3), (4)
образуют пару взаимодвойственных
задач, и любая из них может
рассматриваться как исходная.
Решать исходную или двойственную
задачу – вопрос лишь удобства
Математические модели двойственных
задач могут быть симметричными и
несимметричными. В табл. 1, 2
приведены их матричные формы записи

32.

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

33.

34.

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

35.

36.

Пример. Даны прямые задачи.
Построить двойственные к ним задачи.

37.

Решение. Рассматриваемая задача
относится к симметричным двойственным
задачам на отыскание максимального
значения целевой функции.
Используем общие правила
составления двойственных задач. Так
как в задаче на максимум ограничения
неравенства должны иметь вид « < », то
умножим второе ограничениенеравенство на -1.
Исходная задача запишется в виде

38.

39.

Найдем соответствующую
двойственную задачу (строка 1, табл.
1). Введем вектор двойственных
переменных размерности 3 (по числу
уравнений системы ограничений) .
Соответствующие векторы и матрица
ограничений имеет вид:

40.

41.

Запишем двойственную задачу. Найти
минимум функции

42.

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

43.

Чтобы получить, например, первое
ограничение двойственной задачи, надо
найти сумму произведений элементов,
стоящих в столбце
, на
соответствующие двойственные
переменные. Результат
Считаем, что эта сумма не меньше
Аналогично составляются и остальные
ограничения двойственной задачи.

44.

45.

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

46.

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

47.

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

48.

Если же одна из задач не имеет
оптимального решения, то система
ограничений двойственной задачи
противоречива
Экономическая интерпретация
двойственной задачи.
Пусть
- оптимальное
решение прямой задачи, а
оптимальное решение двойственной
задачи

49.

На основании первой теоремы
двойственности
можно
записать
Найдем

50.

Учитывая, что функция
получим
линейная,
Из последней формулы следует:
значения переменных
в оптимальном
решении двойственной задачи
представляют собой оценки влияния
свободных членов
системы
ограничений прямой задачи на величину

51.

Пример 1. Для производства двух
видов продукции предприятие использует
четыре вида сырья
Затраты сырья на единицу каждого вида
продукции, прибыль и запасы сырья даны
в табл.

52.

Составить план производства,
обеспечивающий предприятию
максимальную прибыль.
Математическая модель прямой
задачи
Обозначим через
- количество
единиц продукции, соответственно I и II
видов.
Тогда задача заключается в следующем:

53.

максимизировать целевую функцию
при ограничениях

54.

Запишем задачу в матричном виде.
где
- вектор неизвестных,
- вектор коэффициентов
целевой функции,
- вектор правых частей
системы ограничений,

55.

- матрица коэффициентов
системы ограничений.
Решение прямой задачи дает
оптимальный план выпуска продукции I и
II видов.
Поставим в соответствие прямой
задаче двойственную задачу.

56.

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

57.

Представим двойственную задачу в
матричном виде
(4)
где
- вектор
двойственных переменных;
- транспонированная
матрица
коэффициентов системы ограничений

58.

Раскрывая соотношение (4) можно
сформулировать двойственную задачу
так:
найти минимум целевой функции
при ограничениях

59.

Чтобы найти решение этих задач
решим одну из них – прямую, т.к. система
ограничений этой задачи содержит лишь
неравенства « < ». Решение находим
симплексным методом.
Приведем задачу к каноническому виду

60.

61.

Запишем систему ограничений в
векторном виде
где

62.

Составим первую симплекс- таблицу

63.

Поскольку отыскивается максимум
задачи, то критерий оптимальности для
плана не выполнен, т.к. в
- строке
имеются отрицательные оценки.
Дальнейшие результаты пошагового
решения задачи представлены в табл.
3– 5.

64.

65.

66.

67.

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

68.

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