Файл: 1ЭМММ-Линейное программирование.pdf

Сделать презентацию

Скачать файл (0,47Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 02.02.2026

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

Скачиваний: 2

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

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

1.Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ог- раничений привести к виду " £ ", а если минимум — к виду " ³ ",. Для этого неравенства, в которых данное требование не выполняется, умножить на (-1).

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

3.Найти матрицу A' , транспонированную к матрице А.

4.Сформулировать двойственную задачу на основании

полученной матрицы A' и условия неотрицательности переменных.

П р и м е р . 1 . Дана	исходная				задача	линейного
программирования:
Z = 5× x1 - x2 ® max
ì3× x1 + x2 ³ 7
ï	× x1 + 7		× x2 £ 15
ï5	× x1 + 7		× x2 £ 15
í
ïx2 £ 14
ïx		³ 0, x	2	³ 0
î 1			2

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

1. Так как исходная задача является задачей на максимизацию, то приведем все неравенства системы ограничений к виду " £ ", для этого обе части первого неравенства умножим на (-1).

Z = 5× x1 - x2 ® max

ì-3× x1 - x2 £ -7
Получим ïï5× x1 + 7× x2 £ 15 .
í	£ 14
ïx2	£ 14
ïx	³ 0, x	2	³ 0
î 1		2

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

Составим расширенную

матрицу

системы

А:

æ-3

-1

- 7ö

A = ç

÷ .

-1

Найдем

матрицу

A ' , транспонированную к

А:

- 3

5 ö

A ' = ç

-1 7

-1÷ .

- 7

0 ø

Сформулируем двойственную задачу:

F = -7× y1 +15× y2 +14× y3 ® min

ì-3× y1 + 5× y2 ³ 5

× y2 + y3 ³ -1

í- y1 + 7

ïy

³ 0, y

³ 0

î 1

П р и м е р . 2 . Дана

исходная

задача

линейного

программирования:

Z = 5× x1 - x2 + 8× x3 - x4 ® max

ì2× x1 + 5× x2 - x3 + 7× x4 = 2

ïx - x

+ 5× x

- x

£ 3

ï 1

íx - x

+ 3× x

+ 7× x

= 5

ï 1

ïx

³ 0, x

³ 0

î 1

Тогда двойственная задача будет иметь вид:

F = 2× y1 + 3× y2 + 5× y3 ® min

ì2× y1 + y2 +y3 ³ 5

× y1 - y2 - y3 = -1

ï5

5× y2 + 3×y3 ³ 8

í- y1 +

ï7× y - y

+ 7 ×y

= -1

îy2 ³ 0

О с н о в н о е

н е р а в ен с т в о

т е о р и и

д в о й с т в ен н о с т и .

Имеется пара взаимно двойственных задач. Для любых

допустимых

решений

= {x1, x2,...xn} и

={y1, y2,..., ym}

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

исходной и			двойственной			задач	справедливо неравенство
				n	c j x j £	m
Z(X ) £ F(Y )			или	å	c j x j £	å bi yi .
				j=1	i =1
	Д о с т а т о ч н ы й п р и з н а к о п т и м а л ь н о с т и .
		Если		X* = {x1, x2,...xn*} ,			Y* = {y1, y2,..., ym*} -

допустимые решения взаимно двойственных задач, для которых выполняется равенство Z(X *) = F(Y*) , то X * и Y * являются оптимальными решениями соответствующих задач.

П ер в а я т е о р е м а д в о й с т в ен н о с т и .

Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая задача, причем оптимальные значения их функций равны: Zmax = Fmin .

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

В т о р а я т е о р е м а д в о й с т в е н н о с т и . Предположим, дана симметричная пара взаимно

двойственных задач.

n				n
åaij x j £ bi	yi , i =			åaij x j + xn+i = bi
åaij x j £ bi	yi , i =	1, m		åaij x j + xn+i = bi
j=1				j=1
m				m
åaij yi ³ c j	x j , j =			åaij yi - ym+ j = cj
åaij yi ³ c j	x j , j =		1, n	åaij yi - ym+ j = cj
i=1				i=1
Отсюда можно установить соответствие между
первоначальными	переменными			одной	из	взаимно-

двойственных задач и дополнительными переменными другой задачи:

x1	x2	...	xn	xn+1	xn+m
ym+1	ym+2	...	ym+n	y1	ym

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

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

ì m
ï	å xn+i × yi = 0
ïi=1
í n		= 0
ï	å x* × y*
ï	j m+ j
î j=1

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

x*n+i × yi* = 0, i = 1,2,...,m x*j × y*m+ j = 0, j = 1,2,...,n.

Отсюда вытекает вторая теорема двойственности.

Положительным компонентам оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты решения другой задачи. То есть, если x j * ³ 0 ,то

yi* = 0 , а если yi* ³ 0 ,	то x j * = 0 .
Т р е т ь я т е о р е м а д в о й с т в ен н о с т и .
Компоненты	оптимального решения двойственной

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

Компоненты оптимального решения двойственной задачи равны значениям частных производных целевой функции

Zmax (		) по соответствующим			аргументам	т.е.	∂Zmax	= yi и
	b
							∂bi
характеризуют			на	сколько	вырастут	доходы		если
соответствующий ресурс увеличить на одну единицу.

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

Для производства двух видов продукции T1,T2 используется три вида сырья. Предприятие имеет сырья R1, R2, R3 соответственно в количествах 50, 30, 60 единиц. От

реализации единицы каждого вида продукции предприятие получит прибыль соответственно 17 руб. ( c1 ), 25 руб. ( c2 ).

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

Нормы расхода сырья на производство товаров вместе с данными о прибыли и запасах сырья представлены в следующей таблице:

	Нормы расхода сырья
	для производства
Вид сырья	единицы товара			Запасы
	T1		T2
R1	4		2	50
R2	2		5	30
R3	3		4	60
Прибыль	17		25
Пусть x1, x2	- объем	производства		товаров T1,T2 ,