по Общей теории систем и системный анализ (стр. 3 из 13)

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

.

Обозначим множество оптимальных (выбранных) решений

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

Рисунок 1.

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

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

4.1 Методы безусловной и условной оптимизации

4.2 Задача 1.

Найти

(1)

где

4.3 Задача 1

сводится к решению системы уравнений:

(2)

и исследованию значения второго дифференциала:

(3)

в точках

решения уравнений (1).

Если квадратичная форма (2) отрицательно определена в точке, то она достигает в ней максимальное значение, а если положительно определена, то минимальное значение.

Пример:

(4)

Система уравнений имеет решения:

Точка (– 1/3,0) является точкой максимума, а точка (1/3,2) –точкой минимума.

4.4 Задача 2.

Найти

(5)

при условиях:

(6)

Задача 2 решается методом множителей Лагранжа. Для этого находится решение системы (т + п) уравнений:

(7)

(8)

Пример.

Найти стороны прямоугольника максимальной площади, вписанного в круг:

. Площадь А прямоугольника можно записать в виде: А = 4ху, тогда

откуда

4.5 Задача 3.

Найти:

(9)

при условиях:

(10)

Эта задача охватывает широкий круг задач, определяемых функциями f и j.

Если они линейны, то задача является задачей линейного программирования.

4.6 Задача 3а.

Найти

(11)

при условиях

(12)

Она решается симплекс-методом, который с помощью аппарата линейной алгебры производит целенаправленный перебор вершин многогранника, определяемого (12).

4.7 Симплекс-метод

(состоит из двух этапов):

Этап 1. Нахождение опорного решения х(0).

Опорное решение – одна из точек многогранника (12).

Этап 2. Нахождение оптимального решения.

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

Частный случай задачи линейного программирования – так называемая транспортная задача.

4.8 Транспортная задача.

Пусть в пунктах

находятся склады, в которых хранятся товары в количестве соответственно. В пунктах находятся потребители, которым необходимо поставить эти товары в количествах соответственно. Обозначим cij стоимость перевозки единицы груза между пунктами

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

количество товара, перевозимого из пункта аi в пункт bj.

Для того, чтобы удовлетворять запросы потребителя, необходимо, чтобы величины хij удовлетворяли условиям:

(13)

В то же время со склада а; нельзя вывезти продуктов в большем количестве, чем там имеется. Это означает, что искомые величины должны удовлетворять системе неравенств:

(14)

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

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

(15)

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

, удовлетворяющие ограничениям (13), (14) и доставляющие функции (15) минимальное значение. Ограничение (14) – это условие баланса; условие (13) можно назвать целью операции, ибо смысл операции в том и состоит, чтобы обеспечить запросы потребителей.

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

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

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

ограничениям (13), (14). Если

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

4.9 Задача 3б.

В общем случае задача (9 – 10) называется задачей нелинейного программирования. Рассмотрим ее в более принятом виде:

(16)

при условиях

(17)

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

называется релаксационным, если: