Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Методы решения задач.

Читайте также:
  1. B. Принятия оптимального управленческого решения по наиболее важным вопросам деятельности на рынке.
  2. I.5.5. Просмотр и анализ результатов решения задачи.
  3. II. Финансовые методы управления
  4. String - методы
  5. Абстрактные методы
  6. Актовый материал как исторический источник и методы их изучения
  7. Алгоритм решения

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

(7.10)

 

Дана система из n линейных неравенств с n неизвестными и линейная функция F. Требуется найти решение системы x1, x2, x3…xn, удовлетворяющей ГРУ, при котором функция F принимает max значение.

Задачи линейного программирования можно решить аналитическим путем и графическим методом. Второй метод – наглядный, но пригоден лишь для n=2 (т.е. где число переменных = 2).

Пример.

Известно, что уравнение прямой имеет вид: a1x1+a2x2=b. Построим прямую 2x1+x2=2. Перепишем это уравнение в виде:

При такой форме записи в знаменателе показаны отрезки, которые отсекает прямая на осях координат (Рис. 7.2). Если от исходного уравнения перейти к неравенству 2x1+x2£2, то графически решение этого неравенства показано на рис. 7.3, т.е. решением линейного неравенства с двумя переменными является полуплоскость. На рис. 7.3 часть плоскости, которая не удовлетворяет неравенству расположена выше прямой, заштрихована. Координаты всех точек, принадлежащих не заштрихованной части плоскости, имеют такие значения х1 и х2, которые удовлетворяют заданному неравенству. Эта полуплоскость является областью допустимых решений (ОДР).

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

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

Графическое решение этой системы показано на рис. 7.4

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

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

Если мы хотим найти оптимальное решение, то мы должны принять целевую функцию. Пусть мы хотим, чтобы решение было оптимальным в смысле максимизации целевой функции F=x1+x2 → max

 
 

Эта зависимость на рис. 7.5 представлена в форме уравнения прямой с угловым коэффициентом x2=F–x1, из которого видно, что tga= –1. При этом угол a=135°, а величина F равна отрезку, отсекаемому прямой на оси ординат. Если прямую перемещать параллельно самой себе в направлении, указанном стрелками, то величина F будет возрастать. Совместим теперь ОДР, изображенную на рис. 7.4, с линией целевой функции F, построенной на рис. 7.5, получим рис. 7.6.

Поскольку требуется найти оптимальное решение, при котором целевая функция F=x1+x2®max, т.е. стремится к максимуму, будем перемещать график целевой функции в направлении увеличения F. Очевидно, что оптимальным решением будут координаты точки С, равные х1* и х2*. При этом F=F*.

На основании рассмотренного можно сделать вывод:
оптимальным решением являются координаты вершин ОДР.

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

r Найти вершины ОРД, как точки пересечения ограничений.

r Определить последовательно значения целевой функции в вершинах.

r Вершина, в которой ЦФ приобретает оптимальное (максимальное или минимальное) значение, является оптимальной вершиной.

r Координаты этой вершины и являются искомыми оптимальными значениями переменных.


Дата добавления: 2015-10-31; просмотров: 111 | Нарушение авторских прав


Читайте в этой же книге: Практическая работа на ЭВМ | Решение систем линейных уравнений способом Гаусса. | Практическая работа на ЭВМ | Интерполяционный многочлен Лагранжа | Вычисление приближенного значения функции с помощью электронных таблиц | Практическая работа на ЭВМ | ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ТРАНСЦЕНДЕНТНЫХ УРАВНЕНИЙ | Метод половинного деления | Несколько определений | Метод Эйлера. |
<== предыдущая страница | следующая страница ==>
Общий случай задачи оптимизации| Основные положения симплекс-метода

mybiblioteka.su - 2015-2024 год. (0.007 сек.)