решение:

а. Сначала перепишем ограничения в виде уравнений с использованием переменных резерва:

(1)4x + 2y+3w+ 1si +0s2 + 0s3 = 120 • (2) 5х + 4у + 2w + Osi + 1s2-I-0s3 = 100 (3) 2x -I- 3y + 2w + 0si + 0s2 -I- 1s3 = 90

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

Таблица 1

В. Идентифицируйте переменную ввода (столбец с наибольшим положительным значением C-Z). Разделите цифры этого столбца (т.е. 4, 5, и 2) на их соответственные строчные значения. Самое маленькое положительное отношение укажет переменную, покидающую решение. Следовательно, х -входящая переменная, а S2 - выходящая переменная.

г. Разделите все числа в строке S2 на опорное значение (т.е. 5), чтобы получить опорную строку следующей таблицы. Чтобы вычислить новые строки si и зз, используйте опорное число для каждой строки (например, 4 для строки si) чтобы умножить каждое значение опорной строки, и вычтите результат из соответствующих значений предыдущей таблицы.

д. Вычислите значения для строк Z и C-Z.

е. Если все значения строки C-Z отрицательны или равны О, то оптимальное решение найдено. Если появляются положительные значения, повторите пункты в-д.

ж. Затем следуют вторая и третья таблицы. Оптимальные значения х =10,91, у = О, W = 22,73. Соответствующее значение целевой функции 445,46. Кроме того, обратите внимание, что ограничения 2 и 3 использованы полностью, но 8,18 из ог-

раничения 1 остается.

Таблица 2

-0,64

10,91 -0,18

22,73 0,45

= -12,78 = -60,61 = 50,51

Наименьшее положительное отношение указывает количество, на которое можно уменьшить правую часть, а ближайшее к нулю отрицательное значение (т.е. -12,78) указывает наибольшее допустимое увеличение. Следовательно, диапазон выполнимости для третьего ограничения (при первоначальном значении правой части 90):

от 90-50,51 =39,49 до 90 + 12,78= 102,78

г. Теневая цена третьей переменной резерва равна -0,91, что означает увеличение на $0,91 в значении целевой функции для каждой единицы увеличения значения правой части третьего ограничения до верхнего предела диапазона выполнимости. Так как стоимость приобретения дополнительной единицы $0,20 за каждую, чистое увеличение будет -f$0,71 за единицу. Таким образом, приобретать столько единиц, сколько возможно. В части (в) мы нашли что увеличение на 12,78 единиц возможно. Итак, приобретение этого количества разумно. За этой точкой теневая цена будет изменяться, поэтому дополнительные единицы данного ограничения будут просто добавляться к резерву; и другое ограничение станет связывающим для решения.

Вопросы для обсуждения и повторения

1. Для какого круга решений наиболее подходит линейное программирование?

2. Что значит термин «область возможных решений»? Чем определяется эта область?

ЗАДАЧА 3

На основе третьей таблицы задачи 2 выполните анализ чувствительности. В част ности, проделайте следующее:

а. Определите диапазон незначительности переменной у.

б. Определите диапазон оптимальности для коэффициента переменной х.

в. Определите диапазон выполнимости для третьего ограничения.

г. Если третье ограничение можно увеличить на $0,20 за единицу и 200 единиц доступно, сколько фирме следует покупать?

Решение:

а. Значение -1,27 для столбца у в строке C-Z указывает, что вклад единицы у в целевую функцию следует увеличить не менее чем на $1,27 для того, чтобы войти в решение. Диапазон незначительности - от $0 до $17,27.

б. Разделив значения строки C-Z на значения строки х, получим следующие отношения:

X у W S, S3

W = - §:§ = (-пре..) М = , ре..) If = -13,5 Е? = 5,ое

Самое малое положительное отношение 5,06, а отрицательное значение, самое близкое к нулю - 2,31. Следовательно, коэффициент х $20 может быть уменьшен на $2,31 и увеличен на $5,06 -это не влияет назначения оптимального решения. Диапазон оптимальности от $17,69 до $25,06.

в. Сначала разделите значения в столбце количества на соответствующие значения в столбце S3, поскольку нас интересует третье ограничение. При этом получим следующие отношения:

8,18

3. В графических задачах линейного программирования, что является предельным верхним значением:

а. числа переменных в задаче?

б. числа ограничений в задаче?

4. Что такое линия равной стоимости? Линия равной прибыли?

5. Что означает смещение линии целевой функции к началу координат?Что означает смещение от начала координат?

6. Как определяется входящая переменная в задачах максимизации при решении симплексным методом?Как определяется переменная, покидающая решение?

7. Какому аспекту графического решения соответствует симплексная таблица?Какому аспекту соответствует начальная таблица?

8. В каком направлении второе решение перемещается от начального решения в задаче с двумя переменными?

9. После того как оптимальное решение получено, можно рассмотреть возможность приобретения дополнительных недостаточных ресурсов в проблеме максимизации. Как при этом определить:

а. стоит ли добавлять данный ресурс?

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

10. Что означают термины «переменная резерва» и «искусственная переменная»? П. Какой набор избыточных, резервных и искусственных переменных используется в каждом из следующих ограничений?

а.< б.= в.>

12. Существует ли какое-либо теоретическое ограничение числа переменных при решении задачи симплексным методом?

13. Как интерпретируются значения на пересечении строки C-Z и столбца резерва?

14. На каком этапе решения задачи максимизации становится очевидно, что таблица содержит оптимальное решение?

Задачи

1. Решите данные задачи с использованием графического метода линейного программирования, и ответьте на последующие вопросы. Используйте совместные уравнения, чтобы определить оптимальные значения переменных, а. Максимизировать: Z = 2x1+10x2 Ограничения:

Труд: 10x1 + 4x240 часов

Материал: Ixi + 6x2 > 24 фунта

Место хранения: Ixi + 2x2 14 кв.футов

Х1,Х2>0

(1) Каковы оптимальные значения xi, Х2 и Z?

(2) Имеет ли какое-либо ограничение (отличное от нуля) резерв?Если да, то какое это ограничение и какова величина резерва?

(3) Имеет ли какое-либо ограничение (отличное от нуля) избыток? Если да, то какое это ограничение и какова величина избытка?

(4)Имеютли место избыточныеограничения?Если да,то какие?Кратко поясните.