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

Лабораторная работа № 2

ПО КУРСУ “КОМПЬЮТЕРНЫЕ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ”

РЕШЕНИЕ МАТЕМАТИЧЕСКИХ ЗАДАЧ
В ТАБЛИЧНОМ ПРОЦЕССОРЕ EXCEL

Цель работы – Изучение возможностей применения табличного процессора MS Excel для решения задач, требующих сложных математических расчетов, в том числе оптимизационных задач.

Порядок выполнения работы

Выполнение работы включает решение задач, приведенных в подразделах 2.2 – 2.7. По каждой задаче должны быть сделаны выводы, отражающие смысл полученных результатов. Выводы рекомендуется вносить в рабочие листы Excel вместе с получаемыми результатами.

Для решения математических задач в Excel применяются специальные функции, а также несколько математических программ, основная из которых – программа Поиск решения (меню Сервис), предназначенная для решения уравнений, систем уравнений, поиска экстремумов.

Простые вычисления

Пример 2.1 –Известны координаты одиннадцати точек на плоскости. Требуется найти расстояния от каждой из первых десяти точек до одиннадцатой.

Примечание – Напомним, что расстояние между точками с координатами (x₁; y₁) и (x₂; y₂) вычисляется по формуле: .

1В ячейку А1 ввести заголовок “X”, в ячейку B1 – заголовок “Y”. В ячейки A2:A11 и B2:B11 ввести произвольные числа – координаты десяти точек (будем считать, что в столбец A вводятся координаты X, а в столбец B – координаты Y).

2В ячейки D2 и E2 ввести произвольные числа – координаты одиннадцатой точки.

3В ячейку G1 ввести заголовок ”Расстояния”. В ячейках G2:G11 вычислить расстояния от первых десяти точек до одиннадцатой. Для этого выполнить следующее:

– в ячейке G2 найти расстояние между первой и одиннадцатой точками. Для этого ввести формулу: =КОРЕНЬ((A2–$D$2)^2+(B2–$E$2)^2). Здесь знаком $ обозначены абсолютные адреса ячеек, которые не будут изменяться при копировании формулы в другие ячейки;

– в ячейках G3:G11 вычислить расстояния от каждой из остальных точек до одиннадцатой. Для этого с помощью мыши распространить формулу, введенную в ячейку G2, на ячейки G3:G11. Убедиться, что в ячейке G3 находится формула =КОРЕНЬ((A3–$D$2)^2+(B3–$E$2)^2), в ячейке G4 – =КОРЕНЬ((A4–$D$2)^2+(B4–$E$2)^2) и т.д.

Решение уравнений

Пример 2.2 – Решить уравнение: 60×2^x = 0,1.

1Перейти на новый рабочий лист. Выбрать любую свободную ячейку для получения решения, т.е значения переменной x. Пусть для этого выбрана, например, ячейка C1. В соседнюю ячейку B1 ввести подпись “x”.

2В ячейку B2 ввести подпись “Левая часть”. В ячейку C2 ввести формулу, задающую левую часть уравнения: =60*2^C1.

Примечание – Все подписи и обозначения на рабочем листе (“x”, “Левая часть” и т.д.) в этой и последующих задачах необязательны. Их рекомендуется указывать только для наглядности.

3Выбрать элемент меню Сервис – Поиск решения. В появившемся окне Поиск решения ввести следующее:

− в поле Установить целевую ячейку указать ячейку, в которой задана левая часть уравнения, в данном примере – ячейку C2;

− установить переключатель Равной значению. В поле рядом с этим переключателем указать значение 0,1 (т.е. правую часть уравнения);

− в поле Изменяя ячейки указать ячейку, в которой должно быть получено решение уравнения, в данном примере – ячейку C1;

− чтобы получить решение, нажать кнопку Выполнить.

Настройка, заданная в окне Поиск решения, означает следующее: требуется установить целевую ячейку C2 равной значению 0,1, изменяя для этого значение ячейки C1.

4После появления окна с сообщением о том, что решение найдено, установить переключатель Сохранить найденное решение и нажать OK.

В ячейке C1 указывается найденное решение (корень уравнения). В данном примере в ячейке C1 должно быть получено значение, близкое к –9,22. Значение ячейки C2 при этом должно быть очень близким к 0,1.

Если выводится сообщение о невозможности найти решение (“Поиск не может найти подходящее решение”, “Значения целевой ячейки не сходятся” и т.д.), это может означать, что в описании задачи, введенном в рабочем листе Excel или в окне Поиск решения, допущена ошибка. Возможно также, что заданная задача вообще не имеет решения.

Примечания

1 В некоторых случаях табличный процессор Excel не находит решения задачи из-за того, что начальные значения ячеек, указанных в поле Изменяя ячейки (т.е. начальные значения переменных задачи), нулевые. В таких случаях в ячейках, где определяются значения переменных, перед началом решения задачи следует указать произвольные начальные значения (например, единицы).

2 В данном примере еще до решения уравнения было очевидно, что решение у него только одно. В более сложных задачах, где уравнение может иметь несколько решений, рекомендуется сначала приближенно определить диапазоны, где находятся эти решения. Пример такой задачи будет рассмотрен в подразделе 2.6.

Решение систем уравнений

Пример 2.3 – Решить систему уравнений:

1Перейти на новый рабочий лист. Выбрать любые свободные ячейки для получения решения, т.е значений переменных x, y, z. Пусть для этого выбраны, например, ячейки B2, C2, D2. В ячейки B1, C1, D1 ввести подписи “X”, “Y”, “Z”.

2В ячейку B4 ввести подпись “Левые части”. В ячейки B5, B6, B7 ввести формулы, задающие левые части уравнений: в ячейку B5 – формулу =7*B2+48*C2–2*D2, в ячейку B6 – формулу =17*B2+10*C2–8*D2, в ячейку B7 – формулу =B2*C2*D2.

3В ячейку D4 ввести подпись “Правые части”. В ячейки D5, D6, D7 ввести правые части уравнений (20, 25 и 1). Рабочий лист с исходными данными для решения задачи будет иметь примерно такой вид, как показано на рисунке 2.1.

Примечание – Значения 0 в ячейках B5:B7 получены автоматически для начальных значений переменных (ячеек B2:D2), равных нулю.

4Выбрать элемент меню Сервис – Поиск решения. В окне Поиск решения ввести следующее:

− очистить поле Установить целевую ячейку;

− в поле Изменяя ячейки указать ячейки, в которых должны быть получены значения переменных: B2:D2;

− в области Ограничения ввести уравнения, составляющие решаемую систему. Для начала их ввода нажать кнопку Добавить. На экран выводится окно Добавление ограничения. В этом окне в поле Ссылка на ячейку указывается ячейка, в которой находится левая часть уравнения, а в поле Ограничение – правая часть уравнения (число или ссылка на ячейку, где находится правая часть уравнения). Чтобы задать первое из уравнений, требуется в поле Ссылка на ячейку указать ячейку B5. В среднем поле выбрать знак равенства (=). В поле Ограничение указать ячейку D5. Для ввода уравнения нажать кнопку Добавить. Аналогично вводятся остальные уравнения. Для ввода второго уравнения требуется в поле Ссылка на ячейку ввести B6, в поле знака – знак =, в поле Ограничение – D6. Для ввода третьего уравнения требуется в поле Ссылка на ячейку ввести B7, в поле знака – знак =, в поле Ограничение – D7. По окончании ввода всех уравнений нажать OK;

− чтобы получить решение задачи, нажать кнопку Выполнить.

Рисунок 2.1 – Рабочий лист с исходными данными для примера 2.3	Рисунок 2.2 – Рабочий лист с результатами решения примера 2.3

5После появления окна с сообщением о том, что решение найдено, установить переключатель Сохранить найденное решение и нажать OK. Рабочий лист с результатами будет иметь примерно такой вид, как показано на рисунке 2.2. Решение системы уравнений находится в ячейках B2:D2.

Как видно из рисунка 2.2, решение системы уравнений следующее (с округлениями): x = 2,64; y = 0,14; z=2,66. При этом левые части уравнений (ячейки B5:B7) равны правым частям, что подтверждает правильность решения.

Поиск экстремумов функций

Пример 2.4 – Найти экстремум функции y= 5x²–8x+2.

1Перейти на новый рабочий лист. Выбрать любую свободную ячейку для получения решения, т.е значения переменной x. Пусть для этого выбрана, например, ячейка C1. В соседнюю ячейку B1 ввести подпись “x”.

2В ячейку B2 ввести подпись “Функция”. В ячейку C2 ввести формулу, задающую функцию: =5*C1^2–8*C1+2.

3Выбрать элемент меню Сервис – Поиск решения. В появившемся окне Поиск решения указать следующее:

− в поле Установить целевую ячейку указать ячейку с формулой функции, для которой определяется экстремум: C2;

− установить переключатель Равной минимальному значению, так как в данной задаче требуется определить минимум функции;

− в поле Изменяя ячейки указать ячейку, в которой должна быть получена точка экстремума: С1;

− для решения задачи нажать кнопку Выполнить.

4После появления окна с сообщением о том, что решение найдено, установить переключатель Сохранить найденное решение и нажать OK. В ячейку C1 выводится найденное значение x, а в ячейку C2 – соответствующее ему значение y. В данном примере в ячейке C1 должно быть получено значение 0,8, а в ячейке C2 – значение –0,2. Таким образом, функция y= 5x²–8x+3 принимает минимальное значение при x = 0,8, при этом y = –0,2.

Исследование функций

Пример 2.5 – Найти все экстремумы функции y = 0,25x+sin x – 1 и все решения уравнения 0,25x+sin x – 1 = 0 для 0 ≤ x ≤ 10.

В данном случае функция может иметь несколько экстремумов (как минимумов, так и максимумов), а уравнение – несколько решений. Поэтому следует сначала построить график функции y = 0,25x+sin x – 1, чтобы приближенно определить, где находятся экстремумы и пересечения с осью x (т.е. решения уравнения 0,25x+sin x – 1 = 0). Затем необходимо найти каждый экстремум и каждое решение уравнения отдельно, используя программу Поиск решения.

Построение графика функции

1Перейти на новый рабочий лист. Ввести в ячейку A1 подпись “x”, в ячейку B1 – подпись “y”.

2В ячейку A2 ввести число 0, в ячейку A3 – число 0,1. Выделить ячейки A2 и A3. С помощью мыши распространить их содержимое на ячейки A4:A102. В результате в ячейках A2:A102 будут получены числа (значения переменной x) от 0 до 10 с шагом 0,1.

3В ячейку B2 ввести формулу: =0,25*A2+SIN(A2)–1. Распространить ее на ячейки B3:B102. В результате в ячейках B2:B102 будут получены значения y = 0,25x+sin x – 1 для x от 0 до 10 с шагом 0,1.

4По значениям x и y, указанным в ячейках A2:A102 и B2:B102, построить диаграмму с графиком функции y = 0,25x+sin x – 1. Тип диаграммы – Точечная, диапазон данных для построения диаграммы – A1:B102. Рабочий лист с исходными данными и диаграммой должен иметь примерно такой вид, как показано на рисунке 2.3.

Поиск экстремумов

Из графика, приведенного на рисунке 2.3, видно, что на заданном отрезке функция имеет три экстремума. Первый из них (максимум) достигается при значении переменной x, находящемся (примерно) в диапазоне от 1 до 2,5; второй (минимум) – от 4 до 5; третий (максимум) – от 7 до 9. Требуется найти каждый из этих экстремумов, используя программу Поиск решения.

Найдем первый из экстремумов. Задачу его поиска можно сформулировать так: найти максимум функции y = 0,25x+sin x – 1 при x ³ 1, x ≤ 2,5.

1Выбрать любую свободную ячейку для определения значения переменной x в точке экстремума. Пусть для этого выбрана, например, ячейка D25.

2В любую свободную ячейку ввести формулу для вычисления значения y в точке экстремума. Пусть для этого выбрана, например, ячейка D26. В нее необходимо ввести формулу: =0,25*D25+SIN(D25)–1.

 

Рисунок 2.3 – График функции y = 0,25x+sin x – 1

3Выбрать элемент меню Сервис – Поиск решения. В окне Поиск решения ввести следующее:

− в поле Установить целевую ячейку указать ячейку с формулой функции, для которой определяется экстремум: D26;

− установить переключатель Равной максимальному значению, так как в данном случае определяется точка максимума;

− в поле Изменяя ячейки указать ячейку, в которой должно быть получено значение переменной x: D25;

− в области Ограничения ввести ограничения на значение переменной x. Для этого нажать кнопку Добавить. Введем сначала ограничение x ³ 1. С этой целью в появившемся окне Добавление ограничения в поле Ссылка на ячейку следует указать ячейку D25. В среднем поле выбрать знак “больше или равно” (>=). В поле Ограничение указать число 1. Для ввода ограничения нажать кнопку Добавить. Чтобы ввести второе ограничение (x ≤ 2,5), требуется в поле Ссылка на ячейку ввести D25, в поле знака – знак <=, в поле Ограничение – число 2,5. Затем нажать OK;

− нажать кнопку Выполнить.

4После появления окна с сообщением о том, что решение найдено, установить переключатель Сохранить найденное решениеи нажатьOK. В ячейку D25 выводится найденное значение x, а в ячейку D26 – соответствующее ему значение y. В данном примере в ячейке D25 должно быть получено (округленно) значение 1,82, а в ячейке D26 – значение 0,42. Таким образом, первый (на отрезке 0 ≤ x ≤ 10) максимум функции y = 0,25x+sin x – 1 достигается при x = 1,82, при этом y = 0,42.

Рассмотрим поиск второго экстремума. Задачу его поиска можно сформулировать так: найти минимум функции y = 0,25x+sin x – 1 при x ³ 4, x ≤ 5.

Пусть для поиска значения x выбрана ячейка F25 (конечно, можно выбрать и любую другую свободную ячейку). Пусть в ячейку F26 введена формула для вычисления y: =0,25*F25+SIN(F25)–1. В окне Поиск решения необходимо указать следующее: в поле Установить целевую ячейку указать F26; установить переключатель Равной минимальному значению; в поле Изменяя ячейки указать F25; в области Ограничения указать ограничения F25 >= 4, F25 <= 5. Результат должен быть следующим: x = 4,46, y = –0,85.

Третий экстремум (максимум) предлагается найти самостоятельно. Результат должен быть следующим: x = 8,11, y = 1,99.

Поиск решений уравнения

Из графика, приведенного на рисунке 2.3, видно, что на заданном отрезке уравнение 0,25x+sin x – 1 = 0 имеет три решения. Первое из них находится (примерно) в диапазоне от 0,5 до 1,5; второе – от 2,5 до 3,5; третье – от 5 до 6.

Рассмотрим поиск первого решения. Задачу его поиска можно сформулировать так: решить уравнение 0,25x+sin x – 1 = 0 при x ³ 0,5, x ≤ 1,5.

Пусть для поиска значения x выбрана ячейка D30 (конечно, можно выбрать и любую другую свободную ячейку). Пусть в ячейку D31 введена формула для вычисления y: =0,25*D30+SIN(D30)–1. В окне Поиск решения необходимо указать следующее: в поле Установить целевую ячейку указать D31; установить переключатель Равной значению, и в поле рядом с этим переключателем указать значение 0; в поле Изменяя ячейки указать D30; в области Ограничения указать ограничения D30 >= 0,5, D30 <= 1,5. В результате в ячейке D30 должно быть получено значение 0,89, а в ячейке D31 – значение, очень близкое к нулю. Это означает, что 0,25x+sin x – 1 = 0 при x = 0,89.

Аналогично определяются два других решения. Они должны быть следующими: x = 2,85; x = 5,81.

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

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

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

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

E = x₁×x₂ + 2x₁×x₃ + 2x₂×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

---

Дата добавления: 2018-04-15; просмотров: 197; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!