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



Скачать 61.14 Kb.
Дата17.01.2013
Размер61.14 Kb.
ТипЗадача



Лабораторные работы по курсу ТПР. Составитель ассистент кафедры АСУ Воловщиков В.Ю.

КУРС ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ

ЛАБОРАТОРНАЯ РАБОТА №4


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

Цель работы:

  • изучить основы метода ограничений для решения многокритериальных задач линейного программирования;

  • решить многокритериальную задачу линейного программирования методом ограничений;

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


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

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

Пусть задано некоторое множество линейных функций цели , где

, (1)

причем m первых функций цели максимизируются , а остальные M-m минимизируются . На вектор управляющих воздействий наложены линейные ограничения вида:


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

а для минимизируемых функций цели
(4)
где gif" name="object12" align=absmiddle width=23 height=24>- решение, принадлежащее множеству ограничений (2), оптимизирующее i–ю функцию цели, - решения, обеспечивающие наихудшие значения соответственно для максимизируемого и минимизируемого критерия на заданном множестве ограничений (2).

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


где - вектор весовых коэффициентов исходных критериев, причем на последний накладывается ряд ограничений:




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

(5)


для минимального значения параметра , при котором эта система еще совместна.

Решение системы (5) эквивалентно решению следующей задачи линейного программирования:
(6)

при ограничениях


(7)




……………………………..

(8)



где

(9)
(10)

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

.

Этот метод не зависит от вида функциональной зависимости и множества допустимых альтернатив А. Требуется только для каждой конкретной задачи иметь эффективные способы проверки системы неравенств (5).

Рассмотрим иллюстративный пример:

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

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


,
.
На рис. 1 изображена область

определения задачи, точка А2 соот-

ветствует оптимальному плану по

второму критерию, точка А3– оптимальному плану по первому



Рисунок 1



критерию. Отрезок [A2, A3]представляет собой эффективные планы.

Эквивалентная задача линейного программирования примет вид:


при ограничениях



В результате решения поставленной задачи получим следующий результат



,



Полученное решение (1,694; 2,694) – единственное, и оно является точным решением задачи, так как для него , то есть, одинаковы относительные отклонения от оптимальных значений по обоим критериям.

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

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



Рисунок 2





.

(14)

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

Для каждого решения представить следующие результаты:

- численное значение вектора весовых коэффициентов;

- численные значения преобразованных критериев;

- произведения вектора весовых коэффициентов на соответствующие численные значения преобразованных критериев;

- численные значения переменных, в том числе дополнительно введенной переменной;

- численные значения целевых функций.

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

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

1 Титульный лист.

2 Задание по лабораторной работе.

А) Математическая постановка задачи многокритериальной оптимизации в общем виде

Б) Математическая постановка задачи многокритериальной оптимизации в соответствии с выданным заданием

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

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

3 Результаты исследований (включить геометрическую интерпретацию и провести анализ полученных результатов).

4 Выводы по проделанной работе.
Литература: Михалевич В.С., Волкович В.Л. Вычислительные методы исследования и проектирования сложных систем. – М.: Наука. Главная редакция физико-математической литературы, 1982.


Похожие:

Решение многокритериальной задачи линейного программирования методом ограничений iconРешение задачи линейного программирования
Решить задачу линейного программирования. Используя теорию двойственности, доказать правильность полученного решения
Решение многокритериальной задачи линейного программирования методом ограничений iconЗадача линейного программирования
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы
Решение многокритериальной задачи линейного программирования методом ограничений iconРешим прямую задачу линейного программирования двойственным симплексным методом, с использованием симплексной таблицы
Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1)
Решение многокритериальной задачи линейного программирования методом ограничений iconПеречень вопросов к зачету (3 семестр) для студентов направления менж
Несовместность системы ограничений задачи линейного программирования: причины, примеры, экономическая интерпретация
Решение многокритериальной задачи линейного программирования методом ограничений iconЗадачи линейного программирования (оптимизация)
Задачей линейного программирования (злп) называется задача отыскания экстремума (максимума или минимума) линейной функции от нескольких...
Решение многокритериальной задачи линейного программирования методом ограничений iconЛекция-семинар: Построение математических моделей целочисленного линейного программирования
Для одной и той же оптимизационной задачи можно построить несколько моделей целочисленного линейного программирования
Решение многокритериальной задачи линейного программирования методом ограничений iconЗадачи линейного программирования и их решение средствами Excel
В большинстве оптимизационных задач зависимости между переменными линейны. Линейность предполагает наличие двух свойств пропорциональности...
Решение многокритериальной задачи линейного программирования методом ограничений iconРешение задачи линейного программирования, симплекс-метод с естественным и искусственным базисом. Особые случаи решения
Перечень основных вопросов для подготовки к экзамену по дисциплине "Математические методы в управлении"
Решение многокритериальной задачи линейного программирования методом ограничений iconДвойственный симплекс-метод
Решим прямую задачу линейного программирования двойственным симплексным методом, с использованием симплексной таблицы
Решение многокритериальной задачи линейного программирования методом ограничений iconДвойственный симплекс-метод
Решим прямую задачу линейного программирования двойственным симплексным методом, с использованием симплексной таблицы
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org