Пример 2. Решение системы уравнений

Расчет установившихся значений вероятностей состояний системы (финальных вероятностей), описанной марковским процессом, сводится к решению системы алгебраических уравнений. Для изучения принципа решения подобных систем рассмотрим решение системы из трех уравнений с тремя неизвестными вида a_iX + b_iY + c_iZ = d_i (i = 1,2,3) с помощью команды Поиск решения.

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

Для решения системы уравнений следует:

1. Выполнить подготовительные действия (см. табл. 2.1):

1.1 Записать строкой начальные значения неизвестных X, Y, Z, например, нулевые значения в ячейки A10, B10, C10 соответственно.

1.2 Составить таблицу, содержащую значения коэффициентов при этих неизвестных a_i, b_i, c_i (i = 1,2,3), и значения соответствующих свободных членов d_i, например, в ячейках A12 : D14.

1.3 Перемножить начальные значения X, Y, Z на соответствующие коэффициенты (ячейки A16:C18) и просуммировать произведения по строкам (ячейки D16:D18).

2. Запустить Поиск решения:

2.1 Excel 2003: в менюСервис, выбрать команду Поиск решения;

2.2 Excel 2007: на вкладке Данные, в группе Анализ выбрать команду Поиск решения.

3. Заполнить окно диалога Поиск решения данными решаемой задачи (см. рис. 2.1):

3.1 В качестве целевой ячейки установить первую сумму: задать “Установить целевую ячейку (в примере это ячейка D16) равной значению” первого свободного члена d₁.

3.2 На две другие суммы наложить ограничения: равенство двум другим свободным членам d₂ и d₃ (используя кнопку “Добавить”).

3.3 В окне “Изменяя ячейки” указать ячейки с начальными значениями неизвестных X, Y, Z (в этих ячейках окажется результат решения системы).

3.4 Нажать кнопку “Параметры” и ознакомиться с параметрами и методами, используемыми при оптимизационных расчетах (при необходимости можно параметры изменить), чтобы закрыть окно “Параметры”, следует нажать кнопку ОК.

4. Запустить выполнение программы нажатием кнопки “Выполнить”. В результате появится сообщение о нахождении или не нахождении решения.

Таблица 2.1

	A	B	C	D	Комментарии
	X	Y	Z		Начальные значения (числа), после решения задачи на их месте появятся результирующие значения
	a1	b1	c1	d1	Коэффициенты (числа) в уравнениях и значения свободных членов
	a2	b2	c2	d2
	a3	b3	c3	d3
	a1 ∙X	b1∙Y	c1 ∙Z	=Сумм(A16:C16)	Начальный вид системы уравнений (числа)
	a2∙X	b2∙Y	c2∙Z	=Сумм(A17:C17)
	a3∙X	b3∙Y	c3∙Z	=Сумм(A18:C18)

Рис. 2.1 Окно “Поиск решения”

Содержание работы

Основная часть работы состоит в расчете установившихся значений вероятностей состояний системы (финальных вероятностей), описанной марковским процессом.

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

2. Изучить и решить примеры, описанные в теоретической части работы.

3. Выполнить задания для самостоятельного решения:

3.1 Найти корни уравнения третьего порядка. Рекомендации к решению: протабулируйте функцию (согласно номеру варианта) на достаточно большом интервале, постройте график, определите, сколько корней и где они примерно находятся, найдите корни через Подбор параметра.

Варианты заданий:

1. Y=х³-4х²-5х+6=0 5. Y=х³-5х²-4х+8=0

2. Y=1,5х³-х²-4х+4=0 6. Y=1,5х³-3х²-6х+5=0

3. Y=1,2х³-2х²-х+4=0 7. Y=0,5х³-2х²-4х+6=0

4. Y=х³-3х²-4х+4=0 8. Y=1,1х³-5х²-3х+7=0

3.2 Решить систему уравнений, используя надстройку Поиск решения.

Варианты заданий:

1) x₁ + 2x₂ – x₃ = -15

-x₁ + 7x₂ – 9x₃ = 4

x₁ + 2x₂ + 4x₃ = 18

2) 2x₁ + x₂ – 3x₃ = 5

-2x₁ + 4x₂ – 2x₃ = 2

x₁ + x₂ + 4x₃ = 8

3) x₁ + x₂ – x₃ = 2

x₁ + 3x₂ – 5x₃ = 5

x₁ + 4x₂ - 3x₃ = 10

3.3 Определить финальные вероятности состояний процесса, заданного (по указанию преподавателя) в виде графа.

Отчётность по работе

После выполнения работы обучаемый представляет отчет. Отчёт должен содержать:

1. Название и цель работы.

2. Результаты решений примеров, описанных в теоретической части.

3. Результаты решения контрольных заданий.

4. Выводы по результатам работы.

Контрольные вопросы

1. Объясните назначение и принцип работы средства MS Excel Подбор параметра.

2. Какой процесс можно считать марковским?

3. Как можно определить установившиеся значения вероятностей состояний системы?

4. Сформулируйте правило, по которому составляется система уравнений для определения вероятностей состояний системы.

Лабораторная работа 3: Решение задач линейной оптимизации

Цель работы

Изучить средства программы Microsoft Excel для решения задач линейной оптимизации.

Теоретические основы

В общем виде задачу оптимизации формулируется следующим образом:

Пусть X = (x₁, x₂…x_n) – вектор действительных переменных. Необходимо минимизировать или максимизировать целевую функцию z = f(X) при выполнении нескольких ограничений g_j(X) ≤ b_j, (j = 1…m), которые задаются в виде неравенств или равенств. Могут быть также добавлены условия неотрицательности переменных (x_i ≥ 0), которые включаются в указанные ограничения.

Если все функции f(X) и g_j(X) линейны относительно переменных x_i то имеем задачу линейной оптимизации, если хотя бы одна из функций нелинейная, то получаем задачу нелинейной оптимизации.

Таким образом, задача оптимизации включает три элемента:

- переменные x₁, x₂…x_n (в средстве Поиск решения ячейки, содержащие значения этих переменных, называются изменяемыми ячейками);

- целевая функция (ячейка, содержащая значение этой функции называется целевой ячейкой);

- ограничения (для применения средства Поиск решения ограничения могут быть записаны на рабочем листе и затем указаны в диалоговом окне либо заданы непосредственно в этом окне без записи на рабочем листе). При задании ограничений отдельно указываются функции ограничений g_j(X) и вектор правых частей ограничений b_j.

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

После создания табличной модели задачи оптимизации для нахождения оптимального решения применяют средство Поиск решения.