Графическое решение задачи.

Задачи оптимизации.

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

Для постановки задачи оптимизации необходимо следующее:

· выбрать объект оптимизации;

· сформулировать цель оптимизации (математическим выражением цели оптимизации является целевая функция);

· сформулировать внешние (граничные) условия задачи;

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

Задачи оптимизации с несколькими параметрами

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

Постановка задачи

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

Система ограничений при этом имеет вид алгебраической системы из m линейных уравнений (неравенств) с n неизвестными:

где x₁, x₂, x₃…x_n, - неизвестные параметры системы,

c₁, c₂, c₃…c_n, - масштабные множители для целевой функции,

- масштабные множители в системе ограничений,

меры ограничений по условию задачи.

Требуется найти решение системы (2) x₁, x₂, x₃…x_n, удовлетворяющее заданным ограничениям, при котором функция W принимает max (min) значение.

Возможны следующие варианты системы (2):

· m = n. Это наиболее простой случай, система решается алгебраически и имеет единственное решение;

· m > n. Система имеет бесконечное множество решений, одно из которых – оптимальное. Решается либо аналитическим путем с помощью специальных методов, либо графическим методом. Второй метод – более наглядный, но пригоден лишь для (n -число переменных задачи);

· m < n. Система решения не имеет.

Графическое решение задачи.

1) Рассмотрим систему неравенств:

Для удобства запишем ее в следующем виде:

Графическое решение этой системы показано на рис.1. Решением этой системы являются координаты всех точек, принадлежащих области допустимых решений (ОДР), т.е. многоугольнику ABCDO.
Т.к. в ОДР бесчисленное множество точек, значит, рассматриваемая система имеет бесчисленное множество допустимых решений.

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

W =x₁+x₂→max, (5)

Задаем произвольное значение для W:

W =x₁+x₂ =1, (6)

и строим эту линию пунктиром (см.Рис.1).

Поскольку требуется найти оптимальное решение, при котором целевая функция W = x1+x2→max, будем перемещать линию W параллельно самой себе в направлении стрелки до тех пор, пока она не расположится выше многоугольника ABCDO и не будет иметь с ним минимального числа общих точек. Очевидно, что оптимальным решением будут координаты точки С, равные:

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

Пример 1

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

Таблица 1

Изделия Условия
Стоимость 1 изд., у.е.
Время изготовл., час.	0,1	0,2
Рабочее время, час.
Общее кол-во изд.
Кол-во изд. по типам

Требуется определить: какое количество изделий каждого типа нужно производить, чтобы их суммарная стоимость была максимальной.

1. Аналитическое решение:

В данном случае число ограничений равно числу неизвестных (m = n).

Целевая функция задачи будет иметь вид:

Система ограничений:

Из решения системы находим значения

Подставляя их в

2. Графическое решение:

Рис.2.

Как видно из Рис.2, координаты точки пересечения линии W с ОДР будут также равны:

Пример 2

Фабрика выпускает два вида продукции. Ее производство ограничено наличием необходимых ресурсов: A, B, C.

Нормы затрат ресурсов на единицу продукции, запасы ресурсов и прибыль от реализации единицы продукции приведены в табл. 2.

Требуется составить план выпуска продукции, который обеспечивал бы наибольшую прибыль.

Таблица 2

Вид продукции Вид ресурса			Запас ресурса
A
B
C
Прибыль от 1 ед. прод.
Кол-во изд. по типам

Прибыль от реализации всей продукции (целевая функция) составит:

Система ограничений:

Графическое решение задачи приведено на Рис.3, из которого следует, что:

Рис.3.

Не нашли, что искали? Воспользуйтесь поиском: