Решение задач линейного и нелинейного программирования

Рассмотрим решение задач, в которых требуется найти экстремум некоторой функции нескольких переменных при условии, что переменные, от которых она зависит, должны удовлетворять некоторым ограничениям. Ограничения на значения переменных обычно задаются в виде равенств или неравенств. Функция, для которой требуется найти экстремум, называется целевой функцией. Если и целевая функция, и все ограничения задачи линейны, то такая задача называется задачей линейного программирования. Если в постановке задачи имеется хотя бы одно нелинейное выражение, то речь идет о задаче нелинейного программирования.

Пример 2.6 – Пусть требуется изготовить коробку (без крышки) емкостью 100 см³, с площадью основания не более 30 см². Необходимо найти такие размеры коробки (длину, ширину и высоту), чтобы расход материала на ее изготовление был минимальным.

Обозначим длину коробки как x ₁, ширину – x ₂, высоту – x _2. Тогда объем коробки (в см³) вычисляется как x ₁× x ₂× x ₃, площадь основания – как x ₁× x ₂×, а площадь всех поверхностей (т.е. расход материала в см²) – как x ₁× x ₂ + 2 x ₁× x ₃ + 2 x ₂× x ₃ (здесь первое слагаемое – площадь дна коробки, второе и третье – площади ее стенок). Таким образом, задачу определения размеров коробки можно сформулировать так: найти такие значения переменных x ₁, x ₂, x ₃, чтобы величина x ₁× x ₂ + 2 x ₁× x ₃ + 2 x ₂× x ₃ была минимальной, и при этом выполнялись условия x ₁× x ₂ £ 30 и x ₁× x ₂× x ₃ = 100. Кроме того, очевидно, что переменные x ₁, x ₂, x ₃ по смыслу не могут быть отрицательными числами. Эту постановку задачи можно записать в следующем виде:

E = x ₁× x ₂ + 2 x ₁× x ₃ + 2 x ₂× x ₃ ® min

x ₁× x ₂ £ 30

x ₁× x ₂× x ₃ = 100

x_i ≥ 0, i =1,…,2.

Здесь E – целевая функция, подлежащая минимизации (конечно, вместо буквы E можно использовать любое обозначение). Остальные выражения математической модели называются ограничениями. Это задача нелинейного программирования, так как целевая функция, а также ограничения x ₁× x ₂ £ 30 и x ₁× x ₂× x ₃ = 100 – нелинейны. Задача решается с помощью программы Поиск решения следующим образом.

1 Перейти на новый рабочий лист. Выбрать любые свободные ячейки для получения решения, т.е значений переменных x ₁, x ₂, x _2. Пусть для этого выбраны, например, ячейки 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

Таким образом, результаты решения задачи оказались следующими: x ₁=5,48, x ₂=5,48, x ₃=3,32. Эти величины представляют собой, соответственно, длину, ширину и высоту коробки (в сантиметрах). При этом расход материала будет минимальным и составит примерно 103,03 см².

Пример 2.7 – Пусть в условиях примера 2.6 дополнительно требуется, чтобы размеры коробки выражались целыми числами.

В данном случае требуется добавить в постановку задачи дополнительное условие: значения переменных (т.е. ячеек B2, C2, D2) должны быть целыми. Для этого выполнить следующее.

1 Из меню Сервис выбрать элемент Поиск решения.

2 В появившемся окне Поиск решения нажать кнопку Добавить.

3 В появившемся окне Добавление ограничения в поле Ссылка на ячейку указать B2:D2, а в поле знака ограничения выбрать отметку цел. Нажать OK.

4 Чтобы получить решение задачи, нажать кнопку Выполнить. Сохранить найденное решение в рабочем листе. Результаты будут иметь примерно такой вид, как показано на рисунке 2.6.

Рисунок 2.6 – Рабочий лист с результатами решения примера 2.7

Таким образом, результаты решения задачи оказались следующими: x ₁=5, x ₂=5, x ₃=4. Это означает, что длина, ширина и высота коробки должны составлять, соответственно, 5, 5 и 4 см. При этом расход материала будет минимальным и составит 105 см².

Операции с матрицами

В Excel имеется набор функций для сложных математических операций с прямоугольными таблицами чисел – матрицами. Эти функции в основном располагаются в категории Математические. Рассмотрим их применение на следующем примере.

Пример 2.8 – Даны матрицы:

, , .

Требуется выполнить следующие матричные операции:

- найти определитель матрицы A;

- найти произведение матриц B и C;

- найти матрицу, обратную матрице A;

- выполнить транспонирование матрицы C.

Пусть матрицы введены в рабочий лист Excel, как показано на рисунке 2.7.

Рисунок 2.7 – Исходные данные для примера 2.8