С учетом этих ограничений решите следующие задачи ЛП.

a) Максимизировать г = 2#, + х2 - Зх3 + 5хл.

b) Максимизировать г = 8л:, + 6х2 + Зх3 - 2xt.

c) Максимизировать г = Зхх - х2+ Зх3 + 4х4.

d) Минимизировать г - 5л:, - 4л:2 + 6л:3 - 8л:4.

e) Минимизировать г = -4л:, + 6л:2 - 2л:3 + 4л:4.

3. Дана следующая система уравнений:

л:, + 2х2 - Зл:3 + 5л:4 + л:5 = 4, 5л:, - 2л:2 + 6л:4 + х6 = 8, 2л:, + Зл:2 - 2*3 + 3*4 + х7 = 3, -хх + х3- 2х4 + xs = О,

Пусть переменные л:5, х6, х7 и л:8 составляют начальное допустимое базисное решение. Предположим, что в базис вводится переменная хг Определите, какую из переменных текущего базисного решения следует исключить из базиса так, чтобы все переменные остались неотрицательными. Найдите значение переменной хх в этом новом базисе. Повторите это упражнение для переменных л:2, л:3 и л:4.

4. Дана следующая задача ЛП.

Максимизировать z = xt

при ограничениях

5л:, + л:2 = 4, 6л;, + л:3 = 8, Зл:, -Ь лг4 - 3, л: л:2, л:3, л:4>0.

a) Решите эту задачу путем нахождения точек пересечений (не используя метод Гаусса-Жордана), на каждом шаге интерпретируя полученные результаты в терминах базисных решений симплекс-метода.

b) Повторите решения задачи ЛП при тех же ограничениях, что и в п. а, но для минимизации целевой функции z = л:,.

5. Решите следующую задачу ЛП путем нахождения точек пересечений, на каждом шаге интерпретируя полученные результаты в терминах базисных решений симплекс-метода.

Максимизировать z = 5хх - 6х2 + Зх3 - 5xt + 12л;5

при ограничениях

л:, + 3*2 + 5*3 + 6*4 + 3*5 < 90,

2* *3> ХЬ -

(Подсказка. Базисное решение содержит только одну переменную.)

6. Следующая таблица представляет отдельную итерацию симплекс-метода. Все переменные неотрицательные. Таблица не оптимальна как для задачи максимизации, так и для задачи минимизации.

a) Разделите все переменные на базисные и небазисные и найдите их значения.

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

c) Повторите упражнение п. Ь, предполагая, что решается задача минимизации.

d) Какие небазисные переменные не смогут изменить значение целевой функции, если их ввести в базис?

7. Рассмотрите двухмерное пространство решений на рис. 3.7.

a) Пусть целевая функция имеет следующий вид:

максимизировать г = Зх, + 6х2.

Предполагая, что реализация симплекс-метода начинается в точке А, определите последовательность угловых точек, приводящих к точке оптимума Е.

b) Определите вводимую переменную, значения соответствующих отношений в условии допустимости и значение целевой функции, полагая, что реализация симплекс-метода начинается в точке А и целевая функция имеет вид

максимизировать г = 4хх + х2.

c) Повторите п. b применительно к целевой функции

максимизировать z = xt + 4х2.

Рис. 3.7. Пространство решений для упражнения 7

8. Дана следующая задача ЛП.

Максимизировать г = 16л:, + 15л:2

при ограничениях

40л:, + 31л:2< 124, -jc, + л:2 < 1, л:, <3, л:2>0.

a) Решите поставленную задачу симплекс-методом, выбирая в качестве вводимой небазисную переменную, имеющую наибольший по абсолютной величине отрицательный коэффициент в z-строке симплекс-таблицы.

b) Решите поставленную задачу симплекс-методом, выбирая в качестве вводимой небазисную переменную, имеющую наименьший по абсолютной величине отрицательный коэффициент в z-строке симплекс-таблицы.

c) Подсчитайте количество итераций, используемых для решения задачи в пп. атлЬ. Действительно ли выбор вводимой переменной среди небазисных, имеющих наибольший по абсолютной величине отрицательный коэффициент в z-строке, ведет к уменьшению числа итераций, выполняемых при реализации симплекс-метода?

d) Предположим, что задача максимизации целевой функции z заменена на задачу минимизации путем умножения функции г на -1. Как это скажется на количестве итераций симплекс-метода?

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

Расход ресурса на производство одного изделия Ограничение на ресурс

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

3.3.3. Реализация симплекс-метода в системе TORA

В программной системе TORA можно выполнить все итерации симплекс-метода так же, как это было описано в разделе 3.3.2. Сначала введите условия задачи (как это сделать, см. приложение Б). Затем из меню SOLVE/MODIFY выберите команду SolveOAIgebraiclterationsAII-Slack. (Команда All-Slack (Все остаточные) указывает на то, что начальное базисное решение состоит только из остаточных дополнительных переменных. Остальные команды из подменю Iterations будут описаны