Таблица 5п-11. Конечная таблица

60 50

Переменные в решении

60 50

Количество решения

Z C-Z

50 О

10 40/3

-10 -40/3

-40/3 -1/3 2/3

24 9 4

Таблица 5п-12. Компьютерная распечатка анализа чувствительности

МАХ 60X1 + 50X2

SUBJECT ТО

2) 4X1 + 10X2 < 100

3) 2X1 + Х2 < 22

4) 3X1 + 3X2 < 39 END

LP OPTIMUM FOUND AT STEP 3

OBJECTIVE FUNCTION VALUE 740.000

VARIABLE XI X2

VALUE 9.00 4 .00

SLACK OR SURPLUS

REDUCED COSTS 0.00 0.00

24.00 0.00 0.00

SENSITIVITY ANALYSIS

OBJECTIVE COEFFICIENT RANGES

DUAL PRICES 0.00 10.00 13.33

Распечатка начинается исходной задачей и оптимальными значениями переменных. Оптимальные значения переменных даны сначала, под заголовком VARIABLE (ПЕРЕМЕННЫЕ), за ними следуют оптимальные значения переменных резерва, которые перечислены под заголовком ROW (СТРОКА). Справа от оптимальных значений переменных расположена колонка REDUCED COSTS (РЕДУЦИРОВАННАЯ СТОИМОСТЬ), а справа от оптимальных значений резерва - колонка DUAL PRICES (ДВОЙНЫЕ ЦЕНЫ). Здесь строка 2 относится к S], строка 3 относится к S2, и строка 4 относится к S3. Двойные цены равны значениям в строке C-Z конечной таб-

ЛЯДЫ (см.таблицу 5п-11). Не забудьте, что для переменных в решении, значения C-Z буду! Рви нулю. Отличная от нуля редуцированная стоимость затем появится, если переменная не присутствовала в решении. Ненулевая редуцированная стоимость указывает значение, на которое коэффициент при переменной целевой функции может увеличиваться, не входя в решение. Так, если редуцированная стоимость 2,00, то переменная этой целевой функции увеличится на более чем на 2,00, чтобы быть в решении, - если задача содержит одно изменение.

Двойные цены - это теневые показатели для переменных избытка или резерва (в данном случае, резервные переменные).

В оставшейся части распечатки содержатся результаты анализа чувствительности: сначала диапазоны целевого коэффициента (диапазоны оптимальности), затем диапазон правой части ограничений (диапазон выполнимости). Для каждой переменной, CURRENT VALUE (ТЕКУЩЕЕ ЗНАЧЕНИЕ) относится к коэффициенту целевой функции; следующий столбец указывает количество возможного увеличения, а далее следующий столбец-количество возможного уменьшения, которые не изменят оптимального значения переменных, находящихся в решении. Для правосторонних диапазонов приведены переменные резерва (фактически, строка 2 относится здесь к Sj, строка 3 к S2, и строка 4 к S3). ТЕКУЩЕЕ ЗНАЧЕНИЕ относится к начальным правосторонним значениям ограничений. Следующие два столбца показывают значения, на которые можно изменить правую часть ограничений, чтобы она оставалась в пределах диапазона выполнимости.

Ключевые термины

Графическое линейное программирование

Диапазон выполнимости

Диапазон оптимальности

Значения опорной строки

Избыток

Искусственная переменная Новая опорная строка Область возможных решений Ограничения Параметр

Переменные решения Резерв

Связывающее ограничение

Симплекс

Таблица

Теневые цены

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

Цель

graphical linear programming

range of feasibility

range of optimality

row pivot values

surplus

artificial variable new pivot row feasible solution space constraints parameter decision variables slack

binding constraint simplex tableau shadow prices objective function objective

Решение задач

ЗАДАЧА 1

Небольшая строительная компания специализируется на строительстве и продаже домов на одну семью. Компания предлагает два основных типа домов, модель А и модель В. Дома модели А требуют 4000 часов рабочего времени, 2 тонны камня и 2000 кв.футов пиломатериалов. Дома модели В требует 10.000 часов рабочего времени, 3 тонны камня и 2000 кв.футов пиломатериалов. Из-за больших сроков по-

ставки материалов и дефицита квалифицированной и полу-квалифицированной рабочей силы в данной местности, компании придется ограничиться уже имеющимися ресурсами в течение наступающего строительного сезона. Это порядка 400.000 часов рабочего времени, 150 тонн камня и 200000 кв.футов пиломатериалов. Сколько моделей А и В (в соотношении) должна произвести компания, если прибыль от модели А $1000 за единицу, а модели В $2000 за единицу. Предположим, что компания может продать все построенные дома.

Решение:

а. Запишем формулы целевой функции и ограничений.

Максимизировать: Z = 1000А + 2000В Ограничения:

Труд: 4000А + 10000В < 400000 часов работы

Камень: 2А -t- ЗВ < 150 тонн

Пиломатериалы: 2000А + 2000В < 200000 кв.футов

А, В>0

б. Построим графически целевую функцию и ограничения. Найдем угловую точку оптимума (см.график). Обратите внимание, что ограничение по пиломатериалам является избыточным: оно не формирует границу пространства возможных ре-

шении.

Излишек

Оптимум

20 40 60 80 100 Количество единиц модели А

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

Труд 4000А + 10000В = 400000

- ?nnn X (Камень 2А + 38= 150}

40006= 100000 В = 25

Подставьте В = 25 в одно из уравнений и решите для А:

2A-f-3(25) = 150 А = 37,5

Z = 1000 (37,5) + 2000 (25) = 87500

ЗАДАЧА 2

Решите следующую задачу для значений X, У, W, которые будут максимизировать целевую функцию.

Максимизировать: Ограничения:

Z=20x-(-16y+ lOw (1)4х -H2y-i-3w<120 (2) 5х +4y-b2w< 100 (3)2х-ьЗу+ 3w<90 X, у, w>0