Исследование операций (стр. 6 )

В столбце базиса содержатся наименования все переменных, которые не равны нулю, а в столбце решение - их значение, таким образом

xВ=1(1/3), xН = 3(1/3), S3=3, S4=2/3 .

Переменные S1 и S2 = 0. Обычно исследователя только значения переменных исходной задачи, в данном случае объемы производства краски для внутренних xВ и наружных xН помещений.

Значение целевой функции соответствующее оптимальному решению, содержится в строке Z столбца решения. В данном случае оно имеет смысл прибыли от реализации продукции : 12(2/3) тыс. $ / сутки .

2) Статус ресурсов.

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

ресурс	переменная	статус ресурса
Продукт А Продукт В Превышение объема производства краски В по отношению к Н Спрос на краску В	S1=0 S2=0 S3=3 S4=2/3	Дефицитный Дефицитный Недефицитный Недефицитный

ЛЕКЦИЯ 7

Увеличение дефицитных ресурсов ( в примере запасов краски), позволяет увеличить прибыль. Часто бывает важно знать: увеличение, какого из дефицитных ресурсов даст наибольшую прибыль. Ответ на этот вопрос дает характеристика, называемая ценность ресурса.

3) Ценность ресурса ( 2 задача на чувствительность ).

Ценность ресурса yi характеризуется величиной улучшения опти­мального значения целевой функции DZ, риходящейся на единицу вре­мени прироста объема данного ресурса DSi .

Yi=DZ / DSi

Значения ценности ресурсов находятся в строке Z симплекс таблице

в столбцах, соответствующих ресурсам S1,...,S4:

y1=1/3, y2=4/3, y4,y3=0

Естественно, что ценность недефицитных ресурсов равна нулю. Сино­нимами термина ценность ресурса являются также “скрытая цена ”, ”теневая цена”, “двойственная цена”.

4) Максимальное изменения данного ресурса (1 задача на чувстви - тельность )

Для того чтобы оценить, в каких предметах можно изменять запас ресурса, используют следующий прием : дают i-му ресурсу приращение Di и определяют его влияние на решение задачи.

Дадим, например, приращение D1ресурсу 1: т. е. исходную симплекс

таблицу вместо 6 запишем 6+D1 и решим эту задачу в общем виде.

Отметим, что будет меняться только один столбец таблицы-решения:

уравнение	начало	1	2
Z	0	12	12*(2/3)+(1/3)*D1
1	6+D1	2+D1	4/3 + 2/3 *D1
2	8	4	10/3 - 1/3 *D1
3	2	5	3 - 1 *D1
4	2	2	2/3 - 2/3 * D1

Эти коэффициенты (множители D1) совпадают со столбцом S1, поэтому их ре­шать не надо. Так как для базисных переменных оптимального решения должно выполняться требование неотрицательности:

xв = 12*(2/3) + (1/3)*D1 > 0

xн = 4/3 + (2/3)* D1 > 0

S3 = 3 - D1 > 0

S4 = 2/3 - (2/3)*D1 > 0,

которые выполняется при –2 < D1 < 1, то есть применение ресурса вне пределов (6T)-2 приводит к недопустимым решениям, то есть к другому базису.

5) Максимальное изменение коэффициентов целевой функции.

Наряду с определением допустимых изменений запасов часто необходимо проанализировать, как повлияет на оптимальное решение изменение коэффициентов целевой функции ( 3 задача на чувствительность ). Для решения задачи интересующему нас коэффициенту целевой функции дается приращение, например:

Z=(3+d1)*XH + 2*XB

В результате решения произойдет изменение только в первой строке -Z :

Б	xB xH S1 S2 S3 S4	решение
Z	0 0 1/3-(1/3)d1 4/3+(2/3)d1 0 0	12*(2/3)+(10/3)*d1
xB xH S1 S2	0 1 2/3 -1/3 0 0 1 0 -1/3 2/3 0 0 0 0 -2/3 1/3 0 1	1*(1/3) 3*(1/3) 3 2/3

Причем коэффициенты при d1 будут равны коэффициентам в соответствующих столбцах строки xH, коэффициент при которой получил приращение.

Для того, чтобы рассматриваемый план был оптимальным, неоходимо, чтобы коэффициенты: 1/3-(1/3)*d1> 0

4/3-(2/3)*d1 > 0 ,

откуда –2 < d1< 1 .

пункты-потребители кол-во товара на «m» складе

Где cmn - cтоимость перевозки от «m» склада к «n» - му потребителю еденицы груза. xmn - кол-во товара, привезенного из “m”- го склада к “n”-му потребителю. am - кол-во товара “m”- го склада bn - потребность “n” - го потребителя в товаре.

 

Bj Ai	B1	...	Bn	ai
A1	c11 x11		c1n	a1
...
Am	cm1		cmn xmn	am
bj	b1	...	bn

Строки таблицы заполняются так, что выполняются условия:

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

 

Целевая функция здесь записывается так :

то есть минимум стоимости перевозки.

4.5. Транспортная модель –частный случай линейного программирования.

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

cm1

Суть транспортной задачи в ее классической постановке, состоит в следующем :

cmn

Bn

A1

B1

...

...

Am

Есть m “складов ”, в каждом из них содержится am единиц некоторого товара, который оптимальным образом, с учетом стоимости перевозки cij нужно доставить к потребителям.

Для задания условий и решения задачи используется специальная таблица – матрица перевозок.

Решение транспортной задачи методом потенциалов происходит по следующему алгоритму.

1) Определяется базисное решение задачи (то есть некоторое начальное решение, от которогодвигаются к оптимальному) .

Рассмотрим ”диагональный” метод получения базисного решения. Суть метода:

1-ого потребителя “насыщают” товаром с первого склада: Если не хватает - то добавляют со второго склада; лишний товар с первого склада - попадает ко второму потребителю и так далее.

Например:

Bj Ai	B1	B2	B3	ai
A1	6 25	3	2	25
A2	3 5	7 2	5	25
A3	4	6 10	8 5	15
A4	6	8	6 25	25
bj	30	12	30

ЛЕКЦИЯ 8

2. Находятся потенциалы ai и bj всех пунктов отправления и назначения. Потенциалы, это некоторые вспомогательные переменные, для которых выполняются условия:

(*) ak+bl=ckl

где ckl-стоимость перевозки груза из пункта k в l

Для базисных переменных как правило, принимают a1=0 и на основание (*) рассчитывают остальные потенциалы:

b1=6, b2=10, b3=12 ;

табл. *

	b1	b2	b3	ai
A1	6 25	3	2	25
A2	3 5	7 20	5	25
A3	4	6 10	8 5	15
A4	6	8	6 25	25
Bj	30	30	30

b1=c11-a1=c11; b1+a2=c21=3; a2+b2=c22=7 и т. д.

3. По формуле gij=cij-(ai+bj) находятся коэффициенты для всех свободных переменных(не входящих в базис )