Математические методы в коммерческой деятельности. Буравлева О.Ю. - 19 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Взаимная симметрия прямой и двойственной задач определяет существование определенного соот-
ветствия между их оптимальными решениями, которое устанавливают теоремы двойственности: если
прямая и двойственная задачи линейного программирования имеют оптимальные решения, то экстре-
мальные значения их целевых функций равны, т.е. справедливо равенство
min CX = max YB (первая теорема двойственности).
Не менее важное соответствие оптимальных решений прямой и двойственных задач устанавливают
условия дополняющей нежесткости, которые связывают необходимые и достаточные условия опти-
мальности допустимых решений X и Y обеих задач со следующими соотношениями
Y(AX – B) = 0 (C – YA)X = 0 (вторая теорема двойственности) .
Таким образом всегда имеется возможность выбора: решать прямую или двойственную задачу, ис-
пользуя модификацию задачи, для которой легче найти решение.
Пример. Составить задачу, двойственную к данной:
.3,2,1,0
,645
,8324
,52
,332
min,23)(
321
321
321
321
31
=≥
=+−
≤−−
−≤−+
≤−+
→
+
−
=
jx
xxx
xxx
xxx
xxx
xxXZ
j
Р е ш е н и е. Используем общие правила составления двойственных задач. Умножим ограни-
чения-неравенства на –1, так как в задаче на минимум они должны иметь вид «≥» (см. правило 3).
Исходная задача запишется в виде:
.3,2,1,0
,645
,8324
,52
,332
min,23)(
4
3
2
1
321
321
321
321
31
=≥
=+−
−≥++−
≥+−
−≥+−−
→
+
−
=
jx
y
y
y
y
xxx
xxx
xxx
xxx
xxXZ
j
Составим двойственную задачу:
.0,0,0
,143
,05223
,242
max,68533)(
321
4321
4321
4321
4321
≥≥≥
≤+++
≤−+−−
−≤+−−−
→+−+−=
yyy
yyyy
yyyy
yyyy
yyyyYF
Неизвестная ,
4
y соответствующая ограничению-неравенству, может быть любого знака (см. прави-
ло 4).
5 ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ КАК ЧАСТНЫЙ СЛУЧАЙ
ОБЩЕЙ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ
5.1 Общая характеристика распределительной задачи
Распределительные задачи связаны с распределением ресурсов по работам, которые необхо-
димо выполнить. Задачи этого класса возникают тогда, когда имеющихся в наличии ресурсов
не хватает для выполнения каждой работы наиболее эффективным образом. Поэтому целью
решения задачи является отыскание такого распределения ресурсов по работам, при котором
либо минимизируются общие затраты, связанные с выполнением работ, либо максимизируется
получаемый в результате общий доход.

Страницы