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 будут описаны
далее в разделах 3.4, 4.3 и 7.4.2.) Далее задается точность, с которой будут отображаться выходные результаты, остается щелкнуть на кнопке Go То Output Screen (Перейти к экрану вывода).
На рис. 3.8 представлено окно, в котором показаны результаты расчетов для каждой итерации для модели Reddy Mikks (файл ch3ToraReddyMikks.txt). Чтобы перейти к следующей итерации, щелкните на кнопке Next Iteration (Следующая итерация, это режим пошагового выполнения). Чтобы сразу получить окончательный ответ, щелкните на кнопке All Iterations (Все итерации). Если вы выполняете вычисления в пошаговом режиме, то на каждой итерации можно указать вводимую и исключаемую переменные, щелкнув на соответствующих столбце и строке. Если ваш выбор корректен, то столбец закрасится зеленым цветом, а строка - красным. В противном случае получите сообщение об ошибке. Такой тип вычислений должен помочь вам понять основные базовые концепции симплекс-метода без громоздких вычислений по методу Гаусса-Жордана.
TORA D:\Work\ToraFilesV:h3ToraRedclyMild<s.txl
LINEAR PROGRAMMING
SIMPI FX 1ЛН1 I AI) (Starting All Slack Method)
Title: Reddy Mikks model, Example 7.2A (Maximize)
Step* for uenerrtirte NEXT tableau tram CURWrNT one:
1. ENTERING variable: Click a NONBASIC variable (rf correct, column turn* green)
?. LEAVING variable: Click а BASIC variable (it correct, row lurna red) 3. Click command button NEXT ITERATION (or Alt ITERATIONS) Thta atep maybe executed without Stcpa 1 inciter 2.
Рис. 3.8. Модель Reddy Mikks в программе TORA
УПРАЖНЕНИЯ 3.3.3
1. Дана следующая задача ЛП.
Максимизировать z = хг + х2 + Зх3 + 2xt при ограничениях
х1 + 2х2 - Зх, + 5х4 < 4, 5хг - 2х2 + 6х4 < 8,