Решение задач линейного и нелинейного программирования
Рассмотрим решение задач, в которых требуется найти экстремум некоторой функции нескольких переменных при условии, что переменные, от которых она зависит, должны удовлетворять некоторым ограничениям. Ограничения на значения переменных обычно задаются в виде равенств или неравенств. Функция, для которой требуется найти экстремум, называется целевой функцией. Если и целевая функция, и все ограничения задачи линейны, то такая задача называется задачей линейного программирования. Если в постановке задачи имеется хотя бы одно нелинейное выражение, то речь идет о задаче нелинейного программирования.
Пример 2.6 – Пусть требуется изготовить коробку (без крышки) емкостью 100 см3, с площадью основания не более 30 см2. Необходимо найти такие размеры коробки (длину, ширину и высоту), чтобы расход материала на ее изготовление был минимальным.
Обозначим длину коробки как x1, ширину – x2, высоту – x2. Тогда объем коробки (в см3) вычисляется как x1×x2×x3, площадь основания – как x1×x2×, а площадь всех поверхностей (т.е. расход материала в см2) – как x1×x2 + 2x1×x3 + 2x2×x3 (здесь первое слагаемое – площадь дна коробки, второе и третье – площади ее стенок). Таким образом, задачу определения размеров коробки можно сформулировать так: найти такие значения переменных x1, x2, x3, чтобы величина x1×x2 + 2x1×x3 + 2x2×x3 была минимальной, и при этом выполнялись условия x1×x2 £ 30 и x1×x2×x3 = 100. Кроме того, очевидно, что переменные x1, x2, x3 по смыслу не могут быть отрицательными числами. Эту постановку задачи можно записать в следующем виде:
E = x1×x2 + 2x1×x3 + 2x2×x3 ® min
x1×x2 £ 30
x1×x2×x3 = 100
xi ≥ 0, i=1,…,2.
Здесь E – целевая функция, подлежащая минимизации (конечно, вместо буквы E можно использовать любое обозначение). Остальные выражения математической модели называются ограничениями. Это задача нелинейного программирования, так как целевая функция, а также ограничения x1×x2 £ 30 и x1×x2×x3 = 100 – нелинейны. Задача решается с помощью программы Поиск решения следующим образом.
1Перейти на новый рабочий лист. Выбрать любые свободные ячейки для получения решения, т.е значений переменных x1, x2, x2. Пусть для этого выбраны, например, ячейки B2, C2, D2. В ячейки B1, C1, D1 ввести подписи “x1”, “x2”, “x3”.
2В ячейку A4 ввести подпись “Целевая функция”. В ячейку B4 ввести формулу целевой функции: =B2*C2+2*B2*D2+2*C2*D2. Для наглядности ввести в ячейку D4 подпись “min”.
3В ячейку A5 ввести подпись “Ограничения”. В ячейку B5 следует ввести формулу левой части первого ограничения: =B2*C2. В ячейку C5 ввести (для наглядности) знак этого ограничения, т.е. обозначение “<=”. В ячейку D5 ввести правую часть ограничения: число 30. В ячейку B6 ввести формулу второго ограничения (=B2*C2*D2), в ячейку C6 – знак ограничения (=), в ячейку D6 – правую часть ограничения (100). Ограничения, задающие неотрицательность переменных, вводить в рабочий лист не требуется (их ввод будет показан ниже). Вид рабочего листа с исходными данными для решения задачи (с указанием всех введенных формул) показан на рисунке 2.4.
Примечание – При вводе знака равенства, указывающего вид ограничения (в данном примере – в ячейке C6), необходимо перед знаком равенства в ячейку ввести знак “Пробел”, чтобы знак равенства распознавался табличным процессором Excel именно как поясняющий текст, а не как начало математической формулы.
Рисунок 2.4 – Рабочий лист с постановкой задачи для примера 2.6
4В ячейки, где определяются значения переменных (т.е. в ячейки B2, C2, D2) ввести произвольные начальные значения, например, единицы.
5Для решения задачи из меню Сервис выбрать элемент Поиск решения. В появившемся окне Поиск решения ввести следующее:
− в поле Установить целевую ячейку указать ячейку с формулой целевой функции: B4;
− установить переключатель Равной минимальному значению, так как требуется определить максимум целевой функции;
− в поле Изменяя ячейки указать ячейки, в которых должны быть получены значения переменных: B2:D2;
− в области Ограничения ввести ограничения задачи. Для начала их ввода нажать кнопку Добавить. На экран выводится окно Добавление ограничения. В этом окне в поле Ссылка на ячейку указывается ячейка, в которой находится формула левой части ограничения, а в поле Ограничение – его правая часть (число или ссылка на ячейку, где находится правая часть ограничения). Например, чтобы ввести первое из ограничений, требуется в поле Ссылка на ячейку указать ячейку B5, в среднем поле выбрать знак ограничения (<=), а в поле Ограничение указать ячейку D5. Для ввода ограничения нажать кнопку Добавить. Аналогично ввести второе ограничение. Чтобы указать, что все переменные должны быть неотрицательными, необходимо в поле Ссылка на ячейку ввести B2:D2, в поле знака ограничения выбрать “>=”, в поле Ограничение ввести 0. По окончании ввода всех ограничений нажать OK;
− для решения задачи нажать кнопку Выполнить.
6После появления окна с сообщением о том, что решение найдено, установить переключатель Сохранить найденное решениеи нажатьOK. Рабочий лист с результатами решения будет иметь примерно такой вид, как показано на рисунке 2.5.
Рисунок 2.5 – Рабочий лист с результатами решения примера 2.6
Таким образом, результаты решения задачи оказались следующими: x1=5,48, x2=5,48, x3=3,32. Эти величины представляют собой, соответственно, длину, ширину и высоту коробки (в сантиметрах). При этом расход материала будет минимальным и составит примерно 103,03 см2.
Пример 2.7 – Пусть в условиях примера 2.6 дополнительно требуется, чтобы размеры коробки выражались целыми числами.
В данном случае требуется добавить в постановку задачи дополнительное условие: значения переменных (т.е. ячеек B2, C2, D2) должны быть целыми. Для этого выполнить следующее.
1Из меню Сервис выбрать элемент Поиск решения.
2В появившемся окне Поиск решения нажать кнопку Добавить.
3В появившемся окне Добавление ограничения в поле Ссылка на ячейку указать B2:D2, а в поле знака ограничения выбрать отметку цел. Нажать OK.
4Чтобы получить решение задачи, нажать кнопку Выполнить. Сохранить найденное решение в рабочем листе. Результаты будут иметь примерно такой вид, как показано на рисунке 2.6.
Рисунок 2.6 – Рабочий лист с результатами решения примера 2.7
Таким образом, результаты решения задачи оказались следующими: x1=5, x2=5, x3=4. Это означает, что длина, ширина и высота коробки должны составлять, соответственно, 5, 5 и 4 см. При этом расход материала будет минимальным и составит 105 см2.
Операции с матрицами
В Excel имеется набор функций для сложных математических операций с прямоугольными таблицами чисел – матрицами. Эти функции в основном располагаются в категории Математические. Рассмотрим их применение на следующем примере.
Пример 2.8 – Даны матрицы:
, 
, 
.
Требуется выполнить следующие матричные операции:
- найти определитель матрицы A;
- найти произведение матриц B и C;
- найти матрицу, обратную матрице A;
- выполнить транспонирование матрицы C.
Пусть матрицы введены в рабочий лист Excel, как показано на рисунке 2.7.
Рисунок 2.7 – Исходные данные для примера 2.8