Вырожденность двойственой задачи

2. Вырожденность двойственой задачи

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

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

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

Перерабатываются два вида руды: А и В. Заводу может быть поставлено до 100 тыс. т в день руды вида А по цене 3. 25 долл/т и д 30 тыс. т в день руды вида В более высокого качества по цене 3. 40 долл/т. Общая мощность основного процесса переработки равна 100 тыс. т руды в день при затратах на переработку 0. 35 долл. /т.

Основной процесс переработки позволяет получить из каждой тонны руды вида А 0. 15 т продукта 1 и 0. 85 т продукта 2, а из каждой тонны руды вида В 0. 25 т продукта 1 и 0. 75 т продукта 2.

Продукт 1 более ценный, и агрегат, называемый конвертером, способен из каждой тонны продукта 2 получить 0. 5 т продукта 1 и 0. 5 т продукта, который может быть продан как продукт 2, но который нельзя повторно перерабатывать конвертером. Мощность конвертера 50 тыс. т сырья в день при затратах на конвертерную обработку 0. 25 долл/т сырья. Условия реализации следующие. Продукт 2 может быть продан в неограниченном количестве по цене 3. 8 долл/т, продукт 1 продается по цене 5. 5 долл/т и его можно продать по этой цене до 45 тыс. т/день. Существующий контракт требует, чтобы менее 40 тыс. т/день продукта 1. Запасы продукта 1 могут увеличиваться со скоростью 4 тыс. т/день и эти запасы оцениваются из расчета 5. 20 долл/т. Излишек продукта 1 может быть продан в неограниченном количестве по пониженной цене равной 5. 0 долл/т. Оба продукта можно при необходимости докупить: закупочная цена продукта 1 равна 5. 75 долл/т; закупочная цена продукта 2 равна 4. 0 долл/т.

Для построения модели введем следующие обозначения переменных:

X1 - количество переработанной руды вида А

X2 - количество переработанной руды вида В

X3 - количество докупленного продукта 1

X4 - количество докупленного продукта 2

X5 - количество продукта 2 переработанного в конвертере

X6 - количество продукта 1 на складе

X7 - количество продукта 1 проданного по пониженной цене

X8 - дополнительная переменная ограничения на используемые ресурсы руды вида В (<=30)

X9 - дополнительная переменная условия, ограничивающего сверху количество продукта 1 которое можно продать по обычной цене (<=45)

X10 - дополнительная переменная условия, ограничивающего снизу количество продукта 1 которое можно продать по обычной цене (<=40)

X11 - дополнительная переменная условия, ограничивающего сверху объем складируемого запаса продукта 1 (<=4)

X12 - дополнительная переменная условия, ограничивающего сверху мощность основного процесса обработки (<=100)

X13 - дополнительная переменная условия, ограничивающего сверху мощность конвертера (<=50)

X14 - излишек продукта 2, который идет непосредственно на продажу не проходя конвертерной обработки

Ограничения

0. 15X1 + 0. 25X2 + X3 + 0. 5X5 - X6 - X7 + X9 = 45 [ 1 ]

0. 15X1 + 0. 25X2 + X3 + 0. 5X5 + X6 - X7 - X10 = 40 [ 2 ]

X2 + X8 = 30 [ 3 ]

X6 + X11 = 4 [ 4 ]

X1 + X2 + X12 = 100 [ 5 ]

X5 + X13 = 50 [ 6 ]

- 0. 85X1 - 0. 75X2 - X4 + X5 + X4 = 0 [ 7 ]

Целевая функция

5. 50*(0. 15X1 + 0. 25X2 + 0. 5X5) + 3. 80*(0. 85X1 + 0. 75X2 - 0. 5X5)

- 0. 35*(X1 + X2) - 3. 25X1 - 3. 40X2 - 0. 25X5 - 0. 1*(0. 15X1 +

0. 25X2) - 0. 25X3 - 0. 20X4 - 0. 30X6 - 0. 5X7 - MAX

0. 825X1 + 1. 375X2 + 2. 750X5 + 3. 230X1 + 2. 85X2 - 1. 9X5 - 0. 35X1

- 0. 35X2 - 3. 25X1 - 3. 40X2 - 0. 25X5 - 0. 015X1 - 0. 025X2 - 0. 25X3

- 0. 20X4 - 0. 30X6 - 0. 5X7 -> MAX

0. 44X1 + 0. 45X2 + 0. 6X5 - 0. 25X3 - 0. 2X4 - 0. 3X6 - 0. 5X7 -> MAX

Оценки ресурсов

Оценка ограничения на мощность основного процесса переработки равна 0. 44 долл/т (относительная оценка, соответствующая переменной X12 равна 0. 44). Эта оценка справедлива в диапазоне изменения мощности основного процесса определяемом выражением 100 + q, где MAX { 3/-0. 15; 70/-1; 32/-0. 85 } <= q <= MIN { 2/0. 15 } отсюда -20 <= q <= 13. 33

Таким образом, текущий доход можно увеличить на 0. 44 долл. за каждую тонну увеличения мощности основого процесса обработки, если будем увеличивать эту мощность лишь до 113, 33 тыс. т/день.

Оценка ограничения на мощность конвертера равна 0. 6 долл/т (относительная оценка, соответствующая переменной X13 равна 0. 6) Эта оценка справедлива в диапазоне изменения 50 + q, где MAX { 3/-0. 5; 50/-1 } <= q <= MIN { 2/0. 5 } отсюда -6 <= q <= 4

Таким образом, текущий доход можно увеличит на 0. 6 долл. за каждую тонну увеличения мощности конвертера, если будем увеличивать эту мощность лишь до 54 тыс. т/день.

Маргинальная оценка

Маргинальная оценка руды В равна 0. 01 долл/т и справедлива в диапазоне 30 + q, где MAX { 3/-0. 1; 30/-1 } <= q <= MIN { 2/0. 1; 70/1; 32/0. 1 } отсюда -30 <= q <= 20

Если лq = -30, то X2=0, то есть руда вида В закупаться не будет. Если q = 20, то X2=50, то есть можно покупать до 50 тыс. т руды В в день.

Можно сделать вывод, что мы получим чистый доход по 0. 01 долл. за каждую тонну руды вида В, купленную сверх 30 тыс. т/день, при условии, что общее количество покупаемой руды этого вида не превысит преела 50 тыс. т/день, при котором меняется маргинальная оценка из-за изменения базиса. Точно так же мы потеряем по 0. 01 долл. за каждую недостающую тонну руды вида В, если мы будем покупать меньше 30 тыс. т/день. Мы можем рассуждать иначе, а именно, что мы могли бы вести переговоры о дополнительной закупке руды вида В сверх 30 т/день (но не более чем на 20 тыс. т/день) по цене до

3. 40 + 0. 01 = 3. 41 долл/т.

Изменения коэффициентов целевой функции

1. ( Небазисные переменные )

X4: относительная оценка = 0. 2

Естли продукт 2 можно покупать по 4. 00 - 0. 2 = . 80 долл/т или дешевле, то это выгодно делать и мы можем покупать неограниченное количество этого продукта.

X6: относительная оценка = 0. 3

Если цена продукта 1 хранимого на складе увеличится до 5. 20 + 0. 30 = 5. 50 долл/т или более то выгодно хранить запас, увеличивая его до MIN {3/1, 4/1} = 3 тыс. т/день ( до того как произойдет смена базиса).

X7: относительная оценка = 0. 5

Если пониженная цена продукта 1 возрастет до 5. 00 + 0. 5 = 5. 50 долл/т или более, его выгодно продавать на таком рынке, причем ежеднневно можно продавать до 3 тыс. т, прежде чем изменится базис.

X3: относительная оценка = 0. 25

Если продукт 1 можно купить по цене 5. 75 - 0. 25 = 5. 50 долл/т или дешевле, выгодно сделать это, причем можно покупать до 2 тыс. т/день прежде чем изменится базис.

2. ( Базисные переменные )

X2: коэффициент целевой функции = -3. 40

Коэффициент целевой функции может меняться в диапазоне С2 + q, где 0. 01/-1 <= q <= оо

Если цена руды вида В станет равной 3. 41 долл/т или более ( С2 = -3. 40 - 0. 01 ) то выгодно увеличить X8, т. е. уменьшить количество покупаемой руды вида В; диапазон изменения X8 задается соотношениями MAX {2/-0. 1; 70/-1; 32/-0. 1} <= X8 <= MIN {3/0. 1; 30/1}

Обычно нас интересуют только положительные пределы. В нашем примере X8 может меняться до 30 тыс. т/день, прежде чем потребуется изменить базис ( X2 оратится в нуль ). Исследование полученных результатов показывает, что вычисление пределов осуществляется аналогично вычислению маргинальных оценок, выполненномоу ранее.

Это указывает нам путь вычисления маргинальных оценок для переменных, которые не равны значению своей верхней границы ( как мы увидим для руды вида А ( X1 ) )

X1: коэффициент целевой функции = - 3. 25

Коэффициент целевой функции может меняться в диапазоне С1 + q, где - 0. 44 <= q <= 0. 01

Если цена руды вида А уменьшится до 3. 24 долл/т или еще меньше ( С1 = -3. 25 + 0. 01 ), то станет выгодно увеличить X8 ( т. е. заменить руду вида В рудой вида А ) до X8 = 30, что соответствует X1 = 100, X2 = 0. Таким образом маргинальная оценка руды вида А в диапазоне 50-70 тыс. т/день равна 0. 44 долл/т.

Заметим, что скачок маргинальной оценки, отвечающей базисной переменной, происходит при значении, которое эта переменнаяi принимает в оптимальном решении ( в нашем примере при X1 = 70 ) Маргинальные оценки интерпретируются несколько иначе, чем изменения цен, требующиеся для того, чтобы изменить оперативный план. Если руда вида А может быть закуплена дешевле на 0. 01 долл/т, то от замены такой рудой руды вида В целевая функция не изменится; если цена руды вида А возрастет на 0. 44 долл/т, то уменьшение ее закупки на величину, не превосходящую 20 тыс. т/день, также не изменит значения целевой функции.

Изменения компонент вектора ограничений

1. ( Базисная дополнительная переменная )

Величина изменения может быть вычислена непосредственно:

X9 = 2 и X10 = 3 указывают, что количество продукта 1, которое можно продавать по обычной цене равно 43 ( меньше верхней границы на 2 и больше нижней границы на 3 ).

Значение X11 показывает, что верхний предел запаса продукта 1 может быть уменьшен на 4.

2. ( Небазисная дополнительная переменная )

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

X12: Мощность основного процесса обработки может меняться в диапаз MAX {3/-0. 15; 70/-1; 32/-0. 85} <= q <= MIN{2/0. 15} т. е. -20 <= q <= 13. 33

X8: Ресурсы руды типа В могут меняться в диапазоне 30 + q, где MAX {3/-0. 1; 30/-1} <= q <= MIN {2/0. 1; 70/1; 32/0. 1} т. е. -30 <= q <= 20

X13: Мощность конвертера может меняться в диапазоне 50 + q, где MAX {3/-0. 5; 50/-1} <= q <= MIN {2/0. 5} т. е. -6 <= q <= 4

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

Задача к семинарскому занятию

Предприятие может перерабатывать двавида руды: руда вида А может быть поставлена в объеме 50 тыс. т/день по цене 2. 80 долл/т, руда вида Б может быть поставлена в объеме 75 тыс. т/день по цене 2. 50 долл/т.

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

Блоки Эксплуатационные Предельные мощности затраты ($/т) тыс. т/день

Блок основной переработки 0. 20 100

Обогащение 0. 15 25

Измельчение 0. 10 40

Очистка 0. 15 40

Данные о продаже:

Продукт Доход (долл/т) Потребление (МАХ)

1 6. 00 Не ограничео

2 5. 00 60 тыс. т/день

3 4. 00 Не ограничено

Выход продуктов ( в т/т сырья )

Процесс основной обработки Обогащение

Руда А Руда Б proc1 proc2 gr1

proc1 0. 15 0. 12 tret1 0. 15 0. 20 0. 18

proc2 0. 10 0. 10 tret2 0. 35 0. 38 0. 40

proc3 0. 20 0. 15 tret3 0. 50 0. 42 0. 42

proc4 0. 23 0. 25

proc5 0. 32 0. 33

Измельчение Очистка

proc4 proc5 proc3 gr2

gr1 0. 15 0. 10 gr2 0. 20 0. 20 ref2 0. 55 0. 70

gr3 0. 25 0. 35

gr4 0. 40 0. 35

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

Характеристика качества продукта:

Продукты 1 и 3 не имеют никаких ограничений на качество.

Продукт 1 состоит из tret1 и ref1.

Продукт 3 состоит из tret3, ref2 и gr4.

Продукт 2: % окиси металла => 55

Запасы смесей сырья для продукта 2:

tret2 tret3 ref1 ref2 gr3 gr4

% окисей металлов 65 60 53 50 45 40

Мы хотим максимизировать чистый доход за день !

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ

x1 + x21 = 50 . . . . ruda1

x2 + x22 = 75 . . . . ruda2

x1 + x2 + x23 = 100 . . . . blok osn

0. 15x1 + 0. 12x2 = x3 . . . . pr1

0. 10x1 + 0. 10x2 = x4 . . . . pr2

0. 20x1 + 0. 15x2 = x5 . . . . pr3

0. 23x1 + 0. 25x2 = x6 . . . . pr4

0. 32x1 + 0. 33x2 = x7 . . . . pr5

0. 15x6 + 0. 10x7 = x9 . . . . gr1

0. 20x6 + 0. 20x7 = x10 . . . . gr2

0. 25x6 + 0. 35x7 = x11 . . . . gr3

0. 40x6 + 0. 35x7 = x12 . . . . gr4

0. 15x3 + 0. 20x4 + 0. 18x9 = x13 . . . . tr1

0. 35x3 + 0. 38x4 + 0. 40x9 = x14 . . . . tr2

0. 50x3 + 0. 42x4 + 0. 42x9 = x15 . . . . tr3

0. 45x5 + 0. 30x10 = x16 . . . . ref1

0. 55x5 + 0. 70x10 = x17 . . . . ref2

0. 5x13 + 0. 5x16 = x18 . . . . Q1

0. 3x15 + 0. 3x17 + 0. 4x12 = x19 . . . . Q3

65x14 + 60x15 + 53x16 + 50x17 + 45x11 + 40x12 = 55x20

УСТРОЙСТВО ПК

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

Типовая система IBM PC включает системный блок, где размещены основая электроника компьютера и накопители, клавиатуруЂ, дисплей и принтер. Системный блок имеет размеры порядка 15*40*50см и весит около 13 кг.

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

Cистемный блок IBM PC состоит из следующих основных компонентов: