Основы математического программирования (стр. 10 )

Таблица последняя, нет положительных членов.

x1 = 6

x2 = 36

x3 = 24

x4 = 0

y1 = 0

y2 = 0

y3 = 5

y4 = 0

Zmin = 15420

Смешанная система ограничений
Разрешающая строка	Разрешающий столбец
Окончание
СИМПЛЕКС-МЕТОД
Вариант недопустимый (Хотя бы один свободный член отрицательный	Вариант допустимый (нет отрицательных свободных членов)
Противоречивость В строке с отрицательным свободным членом все элементы положительные Нет решения	Обычный недопустимый вариант (среди свободных членов, кроме строки Z, нет нулей)	Случай вырожденности ( среди свободных членов, кроме строки Z, появляется ноль)	Обычный допустимый вариант (среди свободных членов, кроме строки Z, нет нулей)	Случай вырожденности (среди свободных членов, кроме строки Z, появляется ноль)
	Строка	Столбец	Строка	Столбец	Строка	Столбец	Строка	Столбец
Окончание
Есть оптимальный вариант	Нет оптимального варианта
Решение		Решение

При mах – ищем При min ищем

2.8. Понятие графического метода. Особые случаи графического метода

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

Zmax= 50 x1 +40x2

2x1 + 5x2 ≤ 20

8x1 + 5x2 ≤ 40

5x1 + 6x2 ≤ 30

На осях 0х1 и 0х2 построим графики функций

L1 = 2x1 + 5x2 = 20

L2 = 8x1 + 5x2 = 40

L3 = 5x1 + 6x2 = 30

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

Отметим это штриховкой, обозначив допустимую сторону каждой координатной оси.

Графики представляют собой графики линейных функций – прямые.

Необходимо для каждого графика найти две точки. Зададим х1=0, затем х2 = 0.

L1: А1(0, 4) В1(10, 0)

L2: А2(0, 8) В2(5, 0)

L3: А3(0, 5) В3(6, 0)

Штриховкой покажем ОДЗ.

Далее найдем оптимальное значение.

Функция Z – линейная. График – прямая линия.

Zmax= 50 x1 +40x2 (1)

Так как функция линейна, можем прибавить к ней любое число – получим новую прямую, но она будет достигать max в той же точке.

Построим график функции

Z =50 x1 +40x2 = 200

Данному уравнению соответствует другая прямая, чем для уравнения (1), но они параллельны.

При перемещении этой прямой в одну сторону Z будет возрастать, в другую убывать.

Построим график прямой 50 x1 +40x2 = 200 А3(0, 5) В3(4,0)

При перемещении прямой от начала координат, значение Z возрастают.

Максимума она достигает в точке пересечения прямых L2 и L3.

Если строить график точно, (на миллиметровке) можно достаточно точно определить оптимальное решение.

Или решить совместно два последних уравнения (2 уравнения, 2 неизвестных).

8x1 + 5x2 = 40

5x1 + 6x2 = 30

Выразим х1 из первого уравнения

х1 = (40-5х2)/8

Подставим во втрое уравнение

5(40-5х2)/8 + 6x2 = 30

25 – 25/8x2 + 6x2 = 30

x2 = 40/23 ~ 1,7

Следовательно х1 = 90/23 ~ 3,9

Целевая функция достигает максимума, равного

50*90/23 + 40*40/23 =6100/23 ~ 265,2

Особые случаи графического метода.

1. Задача не имеет решения в том случае, если нет фигуры, ограниченной всеми прямыми.

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

3. Альтернативный оптимум. Бывает в том случае, когда прямая целевой функции параллельна стороне многоугольника.

Пример 1.

Zmax= 10x1 + 3x2

2x1 +3x2 ≤ 33

x1 + 6x2 ≥ 14

5x1 – 4x2 ≥ 2

x1 – 2x2 ≤ 6

x1 ≥ 0; х2 ≥ 0

 

Пример 2.

Zmax = x1 + 2x2 –2x1 +3x2 ≤ 9 x1 – 2x2 ≤ 2 x1 ≥ 0; х2 ≥ 0

Zmin = x1 + 2x2 –2x1 +3x2 ≤ 9 x1 – 2x2 ≤ 2 x1 ≥ 0; х2 ≥ 0

Пример 3.

Zmax = x1 – x2

–2x1 +3x2 ≤ 9

x1 – x2 ≤ 2

x1 + x2 ≤ 8

x1 ≥ 0; х2 ≥ 0

Пример 4.

Zmin = 2x1 + x2

–2x1 +3x2 ≤ 9

x1 + 2x2 ≥ 8

x1 + x2 ≤ 8

x1 ≥ 0; х2 ≥ 0

2.9. Двойственность в линейном программировании

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

Обе эти задачи образуют пару двойственных задач линейного программирования.

Составим двойственную задачу к задаче использования сырья.

Имеется m видов сырья количестве b1, b2, … bm, которые используются для изготовления n видов продукции.

Известно:

aij – расход i-ого вида сырья на единицу j-ой продукции;

сj – прибыль при реализации единицы j-ого вида продукции.

Составить план выпуска продукции, обеспечивающей максимальную прибыль.

Математическая модель задачи имеет вид:

Z(x) = c1x1 + c2x2 + … + cnxn max

a11x1 + a12x2 + … + a1n xn ≤ b1 y1

a21x1 + a22x2 + … + a2n xn ≤ b2 y2

…………………………………………….

am1x1 + am2x2 + … + amn xn ≤ bm ym

xj ≥ 0, j = 1, 2, …, n

Предположим, что второй производитель хочет перекупить сырье.

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

Введем вектор оценок (цен) видов сырья Y (y1, y2, …, ym).

Затраты на приобретение i-ого вида сырья в количестве bi равны biyi.

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

F(y) = b1y1 + b2y2 + … + bmym min

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

Система ограничений примет вид:

a11y1 + a21y2 + … + an1 yn ≤ c1

a12y1 + a22y2 + … + an2 yn ≤ c2

…………………………………………….

a1ny1 + a2ny2 + … + amn yn ≤ сn

Очевидно, что оценки (стоимость) видов сырья должны удовлетворять условиям неотрицательности

yj ≥ 0, j = 1, 2, …, m

Таким образом, связь исходной и двойственной задачи состоит в том:

1. Коэффициенты ci целевой функции исходной задачи являются свободными членами системы ограничений двойственной задачи.

2. Свободные члены bi системы ограничений исходной задачи служат коэффициентами целевой функции двойственной задачи.

3. Матрица коэффициентов системы ограничений двойственной задачи является транспонированной матрицей коэффициентов системы ограничений исходной задачи.

Общие правила составления двойственных задач.

1. Во всех ограничениях исходной задачи свободные члены должны находиться в правой части, а члены с неизвестными – в левой.

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

3. Если знаки неравенств в ограничениях исходной задачи ≤, то целевая функция Z(x) должна максимизироваться, а если ≥ - минимизироваться.

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

5. Целевая функция двойственной задачи имеет вид:

F(y) = с0 + b1y1 + b2y2 + … + bmym

где с0 – свободный член целевой функции Z(x) исходной задачи.

b1, b2, … bm – свободные члены в ограничениях исходной задачи, при этом bi – свободный член именно того ограничения, которому соответствует переменная yi.

y1, y2, …, ym – неизвестные в двойственной задаче.

6. Целевая функция двойственной задачи оптимизируется в противоположную сторону от исходной задачи.

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

8. Строки коэффициентов в матрице ограничений исходной задачи становятся столбцами в матрице ограничений двойственной задачи. Коэффициенты целевой функции исходной задачи становятся свободными членами в ограничениях двойственной задачи. Все знаки ограничений имеют вид ≥, ели целевая функция стремится к min и наоборот.

Пример 1.

Составить задачу, двойственную к данной:

Z(x) = x1 + 4x2 + 3x3 min

x1 + x2 + x3 ≤ 10

2x1 – x2 ≥ 6

x1 + 2x2 + 3x3 ≥ 12

xj ≥ 0, j = 1, 2, 3

Решение:

Умножим первое неравенство на -1.

Z(x) = x1 + 4x2 + 3x3 min

–x1 – x2 - x3 ≥ –10 y1

2x1 – x2 ≥ 6 y2

x1 + 2x2 + 3x3 ≥ 12 y3

xj ≥ 0, j = 1, 2, 3

Умножим правые части ограничений на соответствующие переменные двойственной задачи и сложим их. Получим целевую функцию.

F(y) = - 10y1 + 6y2 + 12y3 max

–y1 + 2y2+ y3 ≤ 1

–y1 – y2 + 2y3 ≤ 4

–y1 + 3y3 ≤ 3

yj ≥ 0, j = 1, 2, 3

Пример 2.

Составить задачу, двойственную к данной:

Z(x) = 4x1 + 2x2 + 3x3 min

4x1 + 3x2 – x3 ≥ 4

5x1 + x2 + 2x3 ≥ 6

xj ≥ 0, j = 1, 2, 3

Пример 3.

Составить задачу, двойственную к данной:

Z(x) = 6x1 + 4x2 max

2x1 + 4x2 ≤ 8

2x1 + x2 + 2x3 ≤ 6

xj ≥ 0, j = 1, 2

2.10. Понятие целочисленности в линейном программировании

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

Задача целочисленного программирования может быть сформулирована следующим образом:

Найти максимум или минимум функции

n

Z(x) = ∑ cjxj

j = 1

при условиях

n

∑ aijxj = bi, i = 1, 2, …, m

j = 1

xj ≥ 0, j = 1, 2, …, n

а также при дополнительном условии xj – целое число.

такие задачи называются частично целочисленными.

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

В основе метода заложена идея, состоящая в том, что сначала решается задача линейного программирования без учета условий целочисленности.

Рассмотрим пример.

1. Z(x) = c1x1 + c2x2+… + cnxn max

2. a11x1 + a12x2 + … + a1nxn ≤ b1

a21x1 + a22x2 + … + a2nxn ≤ b2

……………………………..

am1x1 + am2x2 + … + amnxn ≤ bm

3. xj ≥ 0, xj – целое число.

Составим исходную симплексную таблицу.

БП	СЧ	x1	x2	…	xn
y1	b1	a11	a12	…	a1n
y2	b2	a21	a22	…	a2n
…	…	…	…	…	…
ym	bm	am1	am2	…	amn
Z	0	c1	c2	…	cn

Допустим, что в результате расчетов мы нашли допустимый оптимальный вариант