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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

расширенной задачи отбрасыванием нулевых искусственных переменных, т.е. ).2,6,0,0(
*
=X
О т в е т: 10)(max −=XZ при ).2,6,0,0(
*
=X
4 ТЕОРИЯ ДВОЙСТВЕННОСТИ
4.1 Виды математических моделей двойственных задач
Любой задаче линейного программирования (исходной или прямой) можно поставить в соответст-
вие другую задачу, которая называется двойственной, или сопряженной. Обе эти задачи образуют пару
двойственных (или сопряженных) задач линейного программирования.
Для ряда практических задач линейного программирования целесообразно заменить решение ис-
ходной прямой задачи решением соответствующей двойственной задачи, симметричной исходной. Для
любой прямой задачи линейного программирования можно сформулировать двойственную задачу сле-
дующим образом.
Составим двойственную задачу к задаче использования сырья.
Имеется m видов сырья в количестве b, b
2
, b
3
, …, b
m
, которые используются для изготовления n ви-
дов продукции. Известно: a
ij
– расход i-го вида сырья на единицу j-ой продукции;
j
c
– прибыль при реа-
лизации единицы j-го вида продукции.
Математическая модель данной задачи имеет вид:
max(min),...)(
2211
→
+
+
+
=
nn
xcxcxcXZ (4.1)
4
3
2
1
2211
22222121
11212111
,...
.............................................
,...
,...
y
y
y
y
bxaxaxa
bxaxaxa
bxaxaxa
mnmnmm
nn
nn
=+++
=+++
=+++
(4.2)
x
j
≥ 0, j = 1,2, …, n. (4.3)
Здесь njx
j
...,,2,1, = – объем производства j-го вида продукции.
Предположим, что второй производитель хочет перекупить сырье. Составим двойственную задачу,
решение которой позволит определить условия продажи сырья. Введем вектор оценок (цен) видов сы-
рья
).,...,,(
21 m
yyyY = Затраты на приобретение i-го вида сырья в количестве
i
b равны
ii
yb . Второму произ-
водителю будет выгодно минимизировать суммарные затраты на приобретение всех видов сырья, по-
этому целевая функция имеет вид:
.min...)(
2211
→
+
+
+
=
mm
ybybybYF (4.4)
Первому производителю невыгодно продавать сырье, если суммарная стоимость всех видов сырья,
расходуемых на каждое изделие j-ой продукции, т.е.
....
2211 mmjjj
yayaya +++
Меньше прибыли
j
c
и система огрничений имеет вид:
≥+++
≥+++
≥+++
.2211
22222112
11221111
...
.................................................
,...
,...
nmmnnn
mm
mm
cyayaya
cyayaya
cyayaya
(4.5)
Очевидно, что оценки видов сырья должны удовлетворять условиям неотрицательности
....,,2,1,0 miy
i
=≥ (4.6).
Таким образом, связь исходной и двойственной задач состоит в том, что коэффициенты
j
c
целевой
функции исходной задачи являются свободными членами системы ограничений двойственной задачи,
свободные члены
i
b системы ограничений исходной задачи служат коэффициентами целевой функции
двойственной задачи, а матрица коэффициентов системы ограничений двойственной задачи является
транспонированной матрицей коэффициентов системы ограничений двойственной задачи.
Рассмотренная пара задач относится к симметричным парам двойственных задач. В теории двойст-

Страницы