Метод Анализа Иерархий (МАИ) -- математический инструмент системного подхода к сложным проблемам принятия решений. МАИ не предписывает лицу, принимающему решение, какого-либо «правильного» решения, а позволяет ему в интерактивном режиме найти такой вариант (альтернативу), который наилучшим образом согласуется с его пониманием сути проблемы и требованиями к ее решению. МАИ позволяет понятным и рациональным образом структурировать сложную проблему принятия решений в виде иерархии, сравнить и выполнить количественную оценку альтернативных вариантов решения. Анализ проблемы принятия решений в МАИ начинается с построения иерархической структуры, которая включает цель, критерии, альтернативы и другие рассматриваемые факторы, влияющие на выбор. Эта структура отражает понимание проблемы лицом, принимающим решение. Каждый элемент иерархии может представлять различные аспекты решаемой задачи, причем во внимание могут быть приняты как материальные, так и нематериальные факторы, измеряемые количественные параметры и качественные характеристики, объективные данные и субъективные экспертные оценки. Следующим этапом анализа является определение приоритетов, представляющих относительную важность или предпочтительность элементов построенной иерархической структуры, с помощью процедуры парных сравнений. Безразмерные приоритеты позволяют обоснованно сравнивать разнородные факторы, что является отличительной особенностью МАИ. На заключительном этапе анализа выполняется синтез (линейная свертка) приоритетов на иерархии, в результате которой вычисляются приоритеты альтернативных решений относительно главной цели. Лучшей считается альтернатива с максимальным значением приоритета.

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

Создание нового проекта в программе MPRIORITY

В окне создания нового проекта были выбраны:

1) Название проекта

2) Число уровней в иерархии

3) Максимальное количество элементов

4) Комментарии к проекту

Рис. 1 Создание нового проекта

Название и комментарий отвечают полученному заданию. Число уровней устанавливается 3, а максимальное число элементов - 7 соответствует числу альтернатив.

Редактирование исходного графа

Во второй уровень графа записываются критерии, в третий - альтернативы.

Рис. 2 Окно редактирования параметров

Рис. 3 Отредактированный граф

Построение матрицы парных сравнений

Относительно верхнего уровня построим матрицу парных сравнений для критериев.

Рис. 4 Отредактированная матрица парных сравнений

где d_xy - расстояние между х и у определяется как max_ix_i - y_i, a d - т.н. порог индекса несогласия. Теперь введённые нами раньше соотношения модифицируются так:

Этап 1

Геометрическая интерпретация множества решений линейного неравенства

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

.

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

Чтобы определить искомую полуплоскость, нужно взять какую-либо точку, не принадлежащую граничной прямой, и проверить, удовлетворяют ли ее координаты данному неравенству.

Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой эта точка принадлежит, в противном случае - другая полуплоскость.

Пример 1. Геометрической интерпретацией решений неравенства является полуплоскость, изображенная на рис. 4.1 стрелками. Покажем это.

Рис.21. Геометрическая интерпретация решений линейного неравенства

Прежде всего, в неравенстве заменим знак неравенства на знак точного равенства и построим соответствующую прямую . Эта прямая делит плоскость на две полуплоскости. Так как точка О (0,0) удовлетворяет неравенству , то областью решения данного неравенства является полуплоскость, которой принадлежит эта точка.

Геометрическая интерпретация множества решений системы линейных неравенств

Пусть дана система линейных неравенств с двумя неизвестными:

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

Возможные случаи области допустимых решений

На рис. 2. представлены возможные ситуации, когда ОДР ЗЛП - выпуклый многоугольник (а), неограниченная выпуклая многоугольная область (б), единственная точка (в), пустое множество (г), прямая линия (д), луч (е), отрезок (ж).

а

Б

в

г

д

е

ж

Рис. 22. Возможные случаи ОДР

Этап 2

Теперь предположим, что ОДР найдена. Перейдем к следующему этапу графического метода решения ЗЛП. Покажем, как среди всех точек ОДР найти такую точку, в которой функция цели имеет максимальное значение. Для этого рассмотрим функцию цели:

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

Вектор называется градиентом функции Z. Он перпендикулярен линиям уровня и показывает направление наибольшего возрастания функции Z. Так как , то .

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

Рис. 23. Функция Z принимает максимальное значение в точке М

Пусть, например, выпуклый многоугольник АВМСD является ОДР, а расположен так, как изображено на рис. 23. Тогда принимает максимальное значение в точке М.

Условия

Производитель может работать на внутренний рынок или на экспорт. При этом на внутренний рынок производитель может произвести 3 продукта за единицу времени, а на экспорт 8. Зная ограничения на количество сырья, затраченную электроэнергию и затраты на транспортировку, найти максимум производства на внутренний рынок.

Таблица 1

Постановка задачи и ограничений

Значения ограничивающих функций

Для ограничивающих функций X1=X, X2=Y

Таблица 2

Нахождение ОДР

Рис. 24 ОДР и целевая функция

Черной линией отмечена целевая функция.

Градиент F(x)={(0;0),(3;-8)}

Антиградиент F(x)={(0;0),(-3;8)}

Так как находится максимум, то движение целевой функции происходит в направление вектора градиента.

Черной точкой отмечено решение, которое находится в точке (2,6875;0).

Значение исходное функции в оптимальной точке F(2,6875;0)=8,0625

2.2 Симплекс Метод

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

Основное содержание симплексного метода заключается в следующем:

1. Указать способ нахождения оптимального опорного решения

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

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

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

1. Привести задачу к каноническому виду

2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)

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

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

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

Определим максимальное значение целевой функции F(X) = 15x₁+17x₂+13x₃ при следующих условиях-ограничений.

0.9x₁+0.8x₂+1.2x₃?23

0.7x₁+1.1x₂+0.8x₃?25

0.6x₁+0.7x₂+0.9x₃?24

x₁?27

x₂?25

x₃?29

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных.

В 1-м неравенстве смысла (?) вводим базисную переменную x₄. В 2-м неравенстве смысла (?) вводим базисную переменную x₅. В 3-м неравенстве смысла (?) вводим базисную переменную x₆. В 4-м неравенстве смысла (?) вводим базисную переменную x₇. В 5-м неравенстве смысла (?) вводим базисную переменную x₈. В 6-м неравенстве смысла (?) вводим базисную переменную x₉.

0.9x₁ + 0.8x₂ + 1.2x₃ + 1x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ = 23

0.7x₁ + 1.1x₂ + 0.8x₃ + 0x₄ + 1x₅ + 0x₆ + 0x₇ + 0x₈ + 0x₉ = 25

0.6x₁ + 0.7x₂ + 0.9x₃ + 0x₄ + 0x₅ + 1x₆ + 0x₇ + 0x₈ + 0x₉ = 24

1x₁ + 0x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 1x₇ + 0x₈ + 0x₉ = 27

0x₁ + 1x₂ + 0x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ + 1x₈ + 0x₉ = 25

0x₁ + 0x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ + 0x₇ + 0x₈ + 1x₉ = 29

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

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

Решим систему уравнений относительно базисных переменных: x₄, x₅, x₆, x₇, x₈, x₉

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,23,25,24,27,25,29)

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2 и из них выберем наименьшее:

2-ая строка является ведущей.

Разрешающий элемент равен (1.1) и находится на пересечении ведущего столбца и ведущей строки.

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₅ в план 2 войдет переменная x2

Строка, соответствующая переменной x₂ в плане 2, получена в результате деления всех элементов строки x₄ плана 1 на разрешающий элемент

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x2 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x2 и столбец x2 .

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

Формируем следующую часть симплексной таблицы.

После преобразований получаем новую таблицу:

Итерация №1.

1. Проверка критерия оптимальности.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение новой базисной переменной.

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

3. Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1 и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (0.39) и находится на пересечении ведущего столбца и ведущей строки.

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

После преобразований получаем новую таблицу:

1. Проверка критерия оптимальности.

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Оптимальный план можно записать так:

x₁ = 12.33

x₂ = 14.88

F(X) = 15 * 12.33 + 17 * 14.88 = 437.907

2.3 Двойственная задача

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

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

Которая ограничена условиями

Тогда задача, состоящая в нахождение минимума функции

При условиях



Называется двойственной по отношению к исходной.

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

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

Прямую задачу см в предыдущем пункте курсовой работы.

Построим двойственную задачу по следующим правилам.

1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.

2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.

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

Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.

Расширенная матрица A.

0.9	0.8	1.2	23
0.7	1.1	0.8	25
0.6	0.7	0.9	24
1	0	0	27
0	1	0	25
0	0	1	29
15	17	13	0

Транспонированная матрица A^T.

0.9	0.7	0.6	1	0	0	15
0.8	1.1	0.7	0	1	0	17
1.2	0.8	0.9	0	0	1	13
23	25	24	27	25	29	0

курсовая работа "Линейное программирование" скачать

Подобные документы

• Графический метод решения задач линейного программирования

  Расчет производства необходимого количества продукции для получения максимальной прибыли предприятия. Математическая модель для решения задач линейного программирования. Построение ограничений и целевых функций. Исследование чувствительности модели.
  
  задача [74,7 K], добавлен 21.08.2010
  

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

  Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
  
  курсовая работа [581,5 K], добавлен 13.10.2008
  

• Графический метод решения задач линейного программирования

  Графический метод как наиболее простой и наглядный метод линейного программирования, его сущность и содержание, особенности применения на современном этапе. Этапы реализации данного метода. Описание интерфейса разработанного программного продукта.
  
  контрольная работа [318,0 K], добавлен 11.06.2011
  

• Графический метод решения задачи линейного программирования

  Решение задачи линейного программирования графическим методом, его проверка в MS Excel. Анализ внутренней структуры решения задачи в программе. Оптимизация плана производства. Решение задачи симплекс-методом. Многоканальная система массового обслуживания.
  
  контрольная работа [2,0 M], добавлен 02.05.2012
  

• Применение линейного программирования для решения оптимизационных задач

  Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
  
  курсовая работа [2,2 M], добавлен 29.05.2015
  

• Метод ветвей и границ

  Особенности метода ветвей и границ как одного из распространенных методов решения целочисленных задач. Декомпозиция задачи линейного программирования в алгоритме метода ветвей и границ. Графический, симплекс-метод решения задач линейного программирования.
  
  курсовая работа [4,0 M], добавлен 05.03.2012
  

• Разработка электронного учебного методического комплекса по изучению раздела "Симплексный метод решения задачи линейного программирования" дисциплины "Математические методы"

  Особенности задач линейного программирования. Симплексный метод решения задач линейного программирования. Обоснование выбора языка, инструментария программирования, перечень идентификаторов и блок-схема алгоритма. Логическая схема работы программы.
  
  дипломная работа [2,4 M], добавлен 13.08.2011
  

• Линейное программирование

  Классификация задач математического программирования. Сущность графического метода решения задач линейного программирования, алгоритм табличного симплекс-метода. Описание логической структуры и текст программы по решению задачи графическим методом.
  
  курсовая работа [263,5 K], добавлен 27.03.2011
  

• Линейное программирование

  Изучение экстремальных задач и поиск их решений. Выбор метода решения и приведения задачи к каноническому виду и к задаче линейного программирования. Метод искусственного базиса. Модифицированный симплекс-метод. Написание программы на языке С++Builder 6.
  
  курсовая работа [343,0 K], добавлен 28.11.2010
  

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

  Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
  
  курсовая работа [1,1 M], добавлен 21.03.2012
  

• Применение аналитической геометрии в экономике

  Понятие арифметического точечного пространства. Различные виды плоскостей в пространстве. Общая задача оптимизации. Геометрия задачи линейного программирования. Графический метод решения задачи линейного программирования при малом количестве переменных.
  
  курсовая работа [756,9 K], добавлен 29.05.2014
  

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

  Постановка задачи линейного программирования и формы ее записи. Понятие и методика нахождения оптимального решения. Порядок приведения задач к каноническому виду. Механизмы решения задач линейного программирования аналитическим и графическим способами.
  
  методичка [366,8 K], добавлен 16.01.2010
  

• Специальные задачи линейного программирования

  Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.
  
  курсовая работа [280,8 K], добавлен 17.11.2011
  

• Методы решения задач линейного программирования с n-переменными

  Характеристика основных методов линейного программирования с n- переменными, в частности, графического и симплекс-метода. Способы решения задачи по определению оптимальной структуры товарооборота, обеспечивающей торговому предприятию максимум прибыли.
  
  курсовая работа [678,7 K], добавлен 03.04.2011
  

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

  Особенности решения задач нелинейного программирования различными методами для проведения анализа поведения этих методов на выбранных математических моделях нелинейного программирования. Общая характеристика классических и числовых методов решения.
  
  дипломная работа [2,4 M], добавлен 20.01.2013
  

• Задачи линейного программирования. Алгоритм Флойда

  Постановка задач линейного программирования. Примеры экономических задач, сводящихся к задачам линейного программирования. Допустимые и оптимальные решения. Алгоритм Флойда — алгоритм для нахождения кратчайших путей между любыми двумя узлами сети.
  
  контрольная работа [691,8 K], добавлен 08.09.2010
  

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

  Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
  
  курсовая работа [132,0 K], добавлен 09.12.2008
  

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

  Широкое применение вычислительной техники как в общей математике, так и в одном из её разделов – математических методах. Ознакомление с решением задач линейного программирования симплекс-методом и графически. Составлена программа на языке Delphi.
  
  курсовая работа [57,1 K], добавлен 04.05.2010
  

• Построение и анализ на чувствительность моделей задач линейного программирования

  Методы определения оптимального плана производства (приобретения) продукции с учетом ограниченного обеспечения ресурсами различного вида. Технология поиска оптимального решения задач линейного программирования (ЗЛП) с помощью итоговой симплекс-таблицы.
  
  лабораторная работа [42,8 K], добавлен 11.03.2011
  

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

  Характеристика параметрических методов решения задач линейного программирования: методы внутренней и внешней точки, комбинированные методы. Алгоритм метода барьерных поверхностей и штрафных функций, применяемых для решения задач большой размерности.
  
  контрольная работа [59,8 K], добавлен 30.10.2014
  

Другие документы, подобные "Линейное программирование"

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам