Главная | Обратная связь | Поможем написать вашу работу!

B.3. Линейные оптимизационные задачи

ЛАБОРАТОРНАЯ РАБОТА №1.

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

Цель работы: Изучение возможностей пакета MS Excel при решении задач линейного программирования. Приобретение навыков решения задач линейного программирования.

Краткие теоретические сведения.

B.1. Основные понятия и положения

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

В электроэнергетике в зависимости от требований поставленной задачи могут приниматься и другие критерии оптимальности, в частности:

критерий надежности электроснабжения;

критерий качества электроэнергии;

критерий наименьшего отрицательного воздействия на окружающую среду (экологический критерий).

Решение оптимизационной задачи включает в себя следующие этапы:

1. Сбор исходной информации (исходных данных).

2. Составление математической модели, под которой понимается формализованное математическое описание решаемой задачи.

3. Выбор метода решения, определяемого видом математической модели.

4. Выполнение математических вычислений, поручаемое, как правило, компьютеру.

5. Анализ решения задачи.

B.2. Математическая модель

Формализованное математическое описание оптимизационной задачи, другими словами, математическая модель включает в себя:

целевую функцию;

ограничения;

граничные условия.

Целевая функция представляет собой математическую запись критерия оптимальности. При решении оптимизационной задачи ищется экстремум целевой функции, например минимальные затраты или максимальная прибыль. Обобщенная запись целевой функции имеет следующий вид:

Z(х ₁, х₂,... х_n) → extr, (1.1)

где х ₁, х₂,... х_n – искомые переменные, значения которых вычисляются в процессе решения задачи; общее количество переменных равно n.

Искомые переменные по своему характеру делятся на непрерывные, дискретные и целочисленные. Если переменная может принимать любые значения, такая переменная называется непрерывной. Примером непрерывной переменной может служить мощность, передаваемая по линии электропередачи.

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

Если переменная может принимать только определенные значения, такая переменная называется дискретной. Примером дискретной переменной может служить искомая мощность трансформатора или искомое сечение линии электропередачи. Значения таких величин регламентируются ГОСТами. Например, мощности трансформаторов составляют ряд … 630, 1000, 1600, … кВА, а сечения линии электропередачи – ряд … 50, 70, 95 … мм². Распространенной задачей с дискретными переменными является задача выбора варианта из числа заданных.

Зависимость между переменными в целевой функции (1.1) может быть линейной или нелинейной. Напомним, что линейной называется такая зависимость, в которую переменные x_i(i =1, 2, 3, … n) входят только в первой степени и с этими переменными выполняются только действия сложения, вычитания и умножения на постоянный коэффициент. Во всех других случаях зависимость будет нелинейной.

Нелинейная целевая функция в заданном диапазоне изменения переменных может иметь один экстремум или несколько экстремумов. В первом случае функция будет одноэкстремальной, во втором – многоэкстремальной. На рис. 1.1 приведены примеры одноэкстремальной (один минимум) и многоэкстремальной (два минимума и один максимум) функции Z(x) одной переменной в диапазоне изменения этой переменной d < x < D.

Рисунок В.1. Одноэкстремальная (а) и многоэкстремальная (б) функции

В случае многоэкстремальной функции каждый экстремум называется локальным. У многоэкстремальных функций ищется глобальный экстремум (наименьший минимум или наибольший максимум). Так при отыскании минимума функции, приведенной на рис. 1.1,б ищется глобальный минимум, отвечающий точке 3.

Ограничения представляют собой различные технические, экономические, экологические условия, учитываемые при решении задачи. Ограничения представляют собой зависимости между переменными х ₁, х₂,... х_n, задаваемые в форме неравенств или равенств

f₁(х ₁, х₂,... х_n) < b ₁;

f₂(х ₁, х₂,... х_n) = b ₂;

...................

f_m(х ₁, х₂,... х_n) > b_m.

Общее количество ограничений равно m. Правые части ограничений, представляющие собой постоянные коэффициенты b_j (j =1, 2, … m), называются свободными членами.

Как и в выражении целевой функции (1.1), зависимости между переменными в системе ограничений (1.2) могут быть линейными и нелинейными.

Граничные условия устанавливают диапазон изменения искомых переменных

d_i < х _i < D_i, i= 1, 2, … n, (1.3)

где d_i и D_i - соответственно нижняя и верхняя границы диапазона изменения переменной x_i.

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

x_i ≥0, где i =1 ,2, … n.

При наличии ограничений и граничных условий ищется уже не абсолютный, а относительный экстремум целевой функции. На рис. 1.2 показана некоторая функция одного переменного Z(x). Указан диапазон изменения переменной х (нижняя граница d и верхняя граница D). Видно, что абсолютный минимум функции соответствует точке 1, а относительный минимум – точке 2, принадлежащей заданному диапазону изменения переменной х.

Рис. 1.2. Абсолютный (точка 1) и относительный (точка 2) минимумы функции

B.3. Линейные оптимизационные задачи

Если целевая функция и система ограничений являются линейно зависимыми от переменных х ₁, х ₂ ,... х_n, для решения оптимизационной задачи используются методы линейного программирования.

Линейная математическая модель в общем случае имеет следующий вид:

Z = z ₁ x ₁ +z ₂ x ₂ +...+z_nx_n → extr,

a ₁₁ x ₁ +a ₁₂ x ₂ +...+a _1n x_n < b ₁,

a ₂₁ x ₁ +a ₂₂ x ₂ +...+a _{2 n} x_n= b₂,

........................

a _m1 x ₁ +a_m2x₂+...+a_mnx_n > b_m,

х_i > 0, i = 1, 2, ... n,

где z_i, b_j, a_ji - заданные постоянные величины, i = 1.2,… n; j = 1, 2,... m.

Задача линейного программирования формулируется следующим образом: найти экстремальное значение линейной целевой функции Z при ограничениях, заданных в форме линейных равенств и (или) неравенств, и граничных условиях, указывающих диапазон изменения переменных.

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

Допустим, что в линейной математической модели (2.1) ищется минимум целевой функции

Z = z ₁ x ₁ +z₂x₂+...+z_nx_n → min.

Если по этой же математической модели нужно найти максимум целевой функции Z, то у коэффициентов целевой функции меняются знаки на противоположные и вновь ищется минимум функции Z

Z = - z ₁ x ₁- z ₂ x ₂ -...- z_nx_n → min.

Таким образом, min (- z ₁ x ₁- z ₂ x ₂-…- z_nx_n) = max (z ₁ x ₁+ z ₂ x ₂+ …+ z_nx_n)

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

Пример. Решить задачу линейного программирования:

L = 5x₁ - 2x₃ ®min

- 5x₁ - x₂ + 2x₃ ≤ 2

- x₁+x₃+ x₄ ≤ 5

- 3x₁ + 5x₄≤ 7

x₁, x₂, x₃, x₄ – целые

0≤x_i≤100, iÎ1,2…4

Для решения подобных задач в MS EXCEL предназначена команда Поиск решения из меню Сервис.

Пусть значения x₁, x₂, x₃, x₄ хранятся в ячейки A1:A4, a значение функции L - в ячейке С1.

Введем целевую функцию:

С1 = –5*A1 – 2*A3

Введем ограничения:

С2 = –5*A1 - A2 + 2*A3

С3 = –А1 +А3 + А4

С4 = –3*А1 + 5*А4.

Пример заполнения экранной формы в MS Excel показан на рис. 1.

Рисунок. 1.

Таким образом, было задано условие исходной задачи линейного программирования. Выполним команду из главного меню Сервис ® Поиск решения (рис. 1).

Рисунок. 2.

Устремим целевую функцию в ячейке C1 к минимуму. Для этого введем в поле Установить целевую функцию значение С1 и установим опцию " равной минимальному значению ". В поле Изменяя ячейки необходимо указать адреса ячеек, в которых хранятся изменяемые значения. В нашем случае это ячейки А1:А4.

Для добавления ограничений необходимо щелкнуть по кнопке Добавить, появится диалоговое окно Добавить ограничение (рис. 2)

Рисунок. 3.

В поле ввода Ссылка на ячейку необходимо ввести адрес ячейки, где хранится ограничение, затем, щелкнув по стрелке, выбрать знак и ввести значение ограничения в поле Ограничение.

Щелчок по кнопке OK означает ввод очередного ограничения и возврат к диалоговому окну Поиск решения.

Щелчок по кнопке Добавить вводить очередное ограничение, находясь в окне Добавить ограничение.

В нашем случае окно будет иметь вид, изображенный на рис. 3. Щелчок по кнопке Выполнить начнет процесс решения задачи, завершится который появлением диалогового окна, изображенного на рис. 4.

Рисунок. 4.

Рисунок. 5.

Щелчок по кнопке OK приведет к появлению в ячейке С1 значения целевой функции L, а в ячейках A1:A4 - значений переменных x₁-x₄, при которых целевая функция достигает минимального значения (рис. 6).

Рисунок. 6.

Если задача не имеет решения или неверно были заданы исходные данные, в окне Результаты поиска решения может появиться сообщение о том, что решение не найдено.

Итак, назначение основных кнопок и окон диалогового окна Поиск решения:

· Поле Установить целевую ячейку - определяет целевую ячейку, значение которой необходимо максимизировать или минимизировать, или сделать равным конкретному значению.

· Опции " минимальному значению ", " максимальному значению " и " значению ", определяют, что необходимо сделать со значением целевой ячейки - максимизировать, минимизировать или сделать равным конкретному значению.

· Поле Изменяя ячейки определяет изменяемые ячейки. Изменяемая ячейка - это ячейка, которая может быть изменена в процессе поиска решения для достижения нужного результата в ячейке из окна Установить целевую ячейку с удовлетворением поставленных ограничений.

· Кнопка Предположить отыскивает все неформульные ячейки, прямо или непрямо зависящие от формулы в окне Установить целевую ячейку, и помещает их ссылки в окно Изменяя ячейки.

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

· кнопки Добавить, Изменить, Удалить позволяют добавить, изменить или удалить ограничение.

· Кнопка Выполнить запускает процесс решения определенной задачи.

· Кнопка Закрыть закрывает окно диалога, не решая проблемы. Сохраняются лишь изменения, сделанные при помощи кнопок Параметры, Добавить, Изменить и Удалить. Не сохраняются изменения, произведенные после использования данных кнопок.

· Кнопка Параметры выводит окно диалога Параметры поиска решения, в котором можно контролировать различные аспекты процесса отыскания решения, а также загрузить или сохранить некоторые параметры, такие, как выделение ячеек и ограничений, для какой-то конкретной задачи на рабочем листе.

· Кнопка Сбросить очищает все текущие установки задачи и возвращает все параметры к их значениям по умолчанию.

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

В задачах линейного программирования всегда необходимо найти минимум (или максимум) линейной функции многих переменных при линейных ограничениях в виде равенств или неравенств.

В задачах линейного программирования всегда необходимо найти минимум (или максимум) линейной функции многих переменных при линейных ограничениях в виде равенств или неравенств.