Материал: Основы математического моделирования. курс лекций. Перова А.В
Применив теорему равновесия к задаче определения производственного плана, можно видеть, что положительную двойственную оценку будут иметь лишь те виды ресурсов, которые полностью используются при оптимальном плане производства изделий (т.е. соответствующее ограничение выполняется как строгое равенство). Поэтому двойственные оценки определяют дефицитность используемых ресурсов. Если i-я двойственная оценка равна нулю, то по i-му виду сырья имеется резерв.
Значения двойственных оценок можно определить по симплексной таблице решения прямой задачи следующим образом: -( j cj), где j-номера столбцов единичных векторов
из исходной симплекс-таблицы (на начальной итерации); j-
окончательные оценки из последней симплекс-таблицы, соответствующие этим векторам. При этом индексы двойственных оценок определяются номером ограничения, которому они соответствуют. Например, из симплексной таблицы 6 можно определить, что двойственная оценка для трудовых ресурсов
y1* 1 |
, для сырья y*2 4 |
и для финансов y*3 0. |
Необходимо заметить, что если в качестве канонической формы рассматривается задача максимизации, то суммаj cj берется без знака “-“.
Задачи дробно-линейного программирования
Общая задача дробно-линейного программирования состоит в определении максимального (минимального) значения функции
|
n |
|
|
|
cj x j |
|
F1 |
F |
j 1 |
|
|
n |
F2 |
||
|
d j xj |
|
|
|
|
|
|
|
j 1 |
|
|
при условиях
80
|
|
|
|
n |
|
bi |
|
|
|
|
|
|
|
|
|
|
a ij x j |
(i 1, m); |
|
||||||
|
|
|
|
j 1 |
|
|
|
|
|
|
|
|
|
|
|
|
x j |
0 (j |
|
), |
|
||||
|
|
|
1, n |
|
||||||||
где cj, |
dj, bi |
|
и |
aij |
– |
|
постоянные числа, |
|||||
n |
|
|
|
|
n |
|
|
|
в области |
неотрица- |
||
d j x j |
0 , ( j 1, n ) и d j x j |
0 |
|
|||||||||
j 1 |
|
|
|
|
j 1 |
|
|
|
|
|
|
|
тельных решений |
системы линейных уравнений, |
задающих |
||||||||||
|
|
|
|
|
|
|
|
n |
|
|||
ограничения. Предположение, что |
djx j 0 не нарушает |
|||||||||||
|
|
|
|
|
|
|
|
j 1 |
|
|||
общности задачи, поскольку в том случае, когда эта величина отрицательна, минус можно отнести к числителю.
Сформулированная задача может быть сведена к задаче линейного программирования. Для этого следует обозначить
n |
1 |
|
|
|
|
y0 dj |
xj |
и ввести новые переменные |
|||
j 1 |
|
|
|
|
|
|
yi y0xj |
( j |
|
). |
|
|
1,n |
||||
Используя введенные обозначения, исходную задачу сведем к следующей - найти максимум (минимум) функции
|
n |
||
F * c j y j |
|||
при условиях |
j 1 |
||
|
|
|
|
n |
|
|
|
aij y j |
bi y0 0, i |
|
|
1, m; |
|||
j 1 |
|
|
|
n |
|
|
|
d j x j |
1; |
||
j 1 |
|
|
|
y j 0, ( j 1, n) и y0 0.
Построенная задача является задачей линейного программирования, следовательно, ее решение можно найти известными методами. Зная оптимальный план этой задачи, на
81
основе соотношений y j y 0 x j , получаем оптимальный план
исходной задачи.
Пример 6. Для производства двух видов изделий A и В используются два типа технологического оборудования. Первое изделие проходит обработку только на втором типе оборудования, второе - на первом и на втором. Время обработки каждого из изделий на оборудовании данного типа приведено в табл. 9. Там же указаны затраты, связанные с производством одного изделия каждого вида.
Таблица 9
Тип оборудования |
Затраты времени (ч) |
|
|
на обработку одного изделия |
|
|
A |
B |
I |
|
2 |
II |
1 |
2 |
Затраты на производство |
5 |
4 |
одного изделия |
|
|
Оборудование II типа предприятие может использовать не более 52 часов. При этом оборудование I типа целесообразно использовать не менее 16 часов. Требуется определить, сколько изделий каждого вида следует изготовить, чтобы себестоимость одного изделия была минимальной.
Составим математическую модель задачи. За x1 обозначим количество выпускаемых изделий вида A, за x2 – количество изделий вида B. Себестоимость определяется следующим образом: С=З/K, где К – количество выпускаемых изделий, З - общие затраты на их производство. Тогда получим следующую задачу дробно-линейного программирования:
F |
5x 1 |
4 x 2 |
min |
; |
|
x 1 |
x 2 |
|
|||
|
|
|
|||
2x |
2 |
16; |
|
|
|
|
|
2x 2 |
52; |
|
|
x1 |
|
||||
x1, x 2 |
0. |
|
|
||
82
Преобразуем ограничения-неравенства данной задачи в равенства:
F |
5x1 |
4x 2 |
|
min ; |
||
x1 |
x 2 |
|
||||
|
|
|
|
|||
2x 2 x 3 |
16 ; |
|||||
|
|
x 4 52 ; |
||||
x1 2x 2 |
||||||
x 1 , x 2 , , x 4 0. |
||||||
Сведем данную задачу к задаче линейного программи- |
||||||
рования. Для этого обозначим x |
x |
2 |
1через y0 и введем |
|||
|
|
1 |
|
|
||
новые переменные yj y0xj ( j 1,5).
В результате приходим к следующей задаче: найти ми-
нимум функции F 5y1 |
4y2 при условиях |
2y 2 y 3 16 y 0 0; |
|
|
2y 2 y 4 52 y 0 0; |
y1 |
|
|
y 2 1; |
y1 |
|
y 0 , y1 , , y 4 0.
Система ограничений задачи содержит всего одну базисную переменную y4. Поэтому составим расширенную задачу путем введения двух искусственных переменных y5 и у6:
F 5 y 1 |
4 y 2 |
My 5 My 6 min при условиях |
|
|
2 y 2 y 3 16 y 0 y 5 |
0; |
|
|
|
2 y 2 y 4 52 y 0 |
0; |
|
y1 |
||
|
|
y 2 y 6 1; |
|
|
y1 |
|
|
y 0 , y1 , , y 6 0.
Решение задачи методом искусственного базиса приведено в табл. 10.
83
|
|
|
|
|
|
|
|
|
|
Таблица 10 |
|
x |
c |
|
b |
5 |
4 |
0 |
0 |
0 |
|
|
|
|
y1 |
y2 |
y3 |
y4 |
y0 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
6 |
5 |
|
Y5 |
М |
|
0 |
0 |
2 |
-1 |
0 |
-16 |
|
|
|
y4 |
0 |
|
0 |
1 |
2 |
0 |
1 |
-52 |
|
|
|
y6 |
М |
|
1 |
1 |
1 |
0 |
0 |
0 |
|
|
|
|
0 |
|
|
-5 |
-4 |
0 |
0 |
0 |
|
|
|
|
1 |
|
|
1 |
3 |
-1 |
0 |
-16 |
|
|
|
y2 |
4 |
|
0 |
0 |
1 |
-1/2 |
0 |
-8 |
|
|
|
y4 |
0 |
|
0 |
1 |
0 |
1 |
1 |
-36 |
|
|
|
y6 |
M |
|
1 |
1 |
0 |
1/2 |
0 |
-6 |
|
|
|
|
0 |
|
|
-1 |
0 |
-2 |
0 |
-32 |
|
|
|
|
M |
|
1 |
0 |
1/2 |
0 |
-6 |
|
|
|
|
y2 |
4 |
|
0 |
0 |
1 |
-1/2 |
0 |
-8 |
|
|
|
y1 |
5 |
|
0 |
1 |
0 |
1 |
1 |
-36 |
|
|
|
y6 |
M |
|
1 |
0 |
0 |
-1/2 |
-1 |
30 |
|
|
|
|
0 |
|
|
0 |
0 |
-16/3 |
5 |
-220 |
|
|
|
|
M |
|
0 |
0 |
-1/2 |
-1 |
30 |
|
|
|
|
y2 |
4 |
|
8/30 |
0 |
1 |
-19/30 |
-8/30 |
0 |
|
|
|
y1 |
5 |
|
36/30 |
1 |
0 |
12/30 |
-6/30 |
0 |
|
|
|
y0 |
0 |
|
1/30 |
0 |
0 |
-1/60 |
-1/30 |
1 |
|
|
|
|
220/30 |
0 |
0 |
-12/30 |
-72/30 |
0 |
|
|
|
||
Из таблицы видно, что оптимальным планом задачи яв-
ляется y1* 36 / 30; y2* 16 |
/ 30; y3* y4* 0; y0* 1/ 30 . |
Учитывая, что yj |
y0x j, находим оптимальный план |
исходной задачи: x* 36; x* 16; x* 0; x* 0 . F(X*)=220/30. |
|||
1 |
2 |
3 |
4 |
84