82820

Выбор видеокарты

Курсовая

Информатика, кибернетика и программирование

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

Русский

2015-03-03

768.62 KB

2 чел.

Содержание

Введение 2

Часть 1: Многокритериальная оптимизация 3

1.1 Определение множества Парето 3

Предметная область 3

Метод Парето 3

Мн-во Парето 4

Метод установления нижних границ 4

Субоптимизация 4

Лексико-графическая оптимизация 4

Метод Борда 5

1.2 Метод анализа иерархий 6

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

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

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

Результат 15

1.3 Метод Электра 16

Таблица критериев и весов критериев. 17

Список альтернатив 18

Оценки альтернатив 18

Сравнение альтернатив и выражение гипотез 19

Результаты Dxx 20

Граф связей 20

Граф с порогами D>2 20

Окончательный граф 20

Выводы по части 1 21

Часть 2: Линейное программирование 22

2.1 Графический метод 22

Условия 26

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

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

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

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

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

Заключение 40

Список литературы 41


Введение

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

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

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

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

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

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

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

Первая часть курсовой работы выполняется в выбранной самостоятельно предметной области. Для данной работы была выбрана тема “Выбор видеокарты”. Для второй части исходные данные берутся из сопровождающих материалов.

Часть 1: Многокритериальная оптимизация

  1.  Определение множества Парето

Множество Парето – множество допустимых альтернатив в задаче многокритериальной (векторной) оптимизации, для которых не существует другой допустимой альтернативы, имеющей по всем критериям не худшие оценки и, хотя бы по одному критерию – строго лучшие. В терминах самого В. Парето (итальянского математика и экономиста): «Всякое изменение, которое не приносит убытков, а которое некоторым людям приносит пользу (по их собственной оценке), является улучшением».

Предметная область

Выбор видеокарты

альт./крит.

Част. GPU МГц +

Объем VRAM Гб +

Част. VRAM МГц +

Цена т.р. -

Длина мм -

Тех. Процесс Нм -

А1 GTX 660

900

1,5

5500

6,5

196

28

А2 GTX 670

950

2

6000

7

270

28

А3 GTX 760

900

2

6100

6,5

196

22

А4 GTX 770

950

4

6200

6,5

196

22

А5 GTX 780

1000

3

6200

12

270

22

А6 TITAN

1000

12

7000

44

270

22

А7 R9 270

950

2

6100

5

270

26

А8 R9 280

990

2

6200

7

270

24

А9 R9 290

1000

3

6100

9

196

22

А10 R9 295

1000

4

6300

12

270

22

Метод Парето

А1 и А2

не сравнимы

А3 и А4

А4 доминирует

А5 и А9

не сравнимы

А1 и А3

А3 доминирует

А3 и А5

не сравнимы

А5 и А10

А10 доминирует

А1 и А4

не сравнимы

А3 и А6

не сравнимы

А1 и А5

не сравнимы

А3 и А7

не сравнимы

А6 и А7

не сравнимы

А1 и А6

не сравнимы

А3 и А8

не сравнимы

А6 и А8

не сравнимы

А1 и А7

не сравнимы

А3 и А9

не сравнимы

А6 и А9

не сравнимы

А1 и А8

не сравнимы

А3 и А10

не сравнимы

А6 и А10

не сравнимы

А1 и А9

не сравнимы

А1 и А10

не сравнимы

А4 и А5

не сравнимы

А7 и А8

не сравнимы

А4 и А6

не сравнимы

А7 и А9

не сравнимы

А2 и А3

не сравнимы

А4 и А7

не сравнимы

А7 и А10

не сравнимы

А2 и А4

А4 доминирует

А4 и А8

не сравнимы

А2 и А5

не сравнимы

А4 и А9

не сравнимы

А8 и А9

не сравнимы

А2 и А6

не сравнимы

А4 и А10

не сравнимы

А8 и А10

не сравнимы

А2 и А7

А7 доминирует

А2 и А8

А8 доминирует

А5 и А6

не сравнимы

А9 и А10

не сравнимы

А2 и А9

не сравнимы

А5 и А7

не сравнимы

А2 и А10

не сравнимы

А5 и А8

не сравнимы

Мн-во Парето

А3 А4 А6 А7 А8 А9 А10

Метод установления нижних границ

Част. GPU >=950

Объем VRAM >= 3

Част. VRAM >= 6100

Цена <= 9

Длина <= 270

Тех. Процесс <= 26

При установленных границах удовлетворяют варианты мн-ва

А4 А9

Субоптимизация

Объем VRAM >= 4

Удовлетворяют

А4 А6 А10

Лексико-графическая оптимизация

Ч. GPU>Об. VRAM>Част VRAM>Цена>Длина>Т. Проц

Ч. GPU>Длина>Част VRAM>Об. VRAM>Цена>Т. Проц

Метод Борда

120 голосов

А3 — А

А4 — B

A6 — C

A7 — D

A8 — E

A9 — F

A10 — G

Число гол.

Предпочтения

A=15*7+22*6+53+12*5+8*6+10*5

448

15

A>D>E>C>F>G>B

B=15+22*3+53*2+12*4+8*3+10*2

279

22

D>A>F>E>B>C>G

C=15*4+22*2+53*3+12*6+8*4+10*3

397

53

G>F>E>D>C>B>A

D=15*6+22*7+53*4+12+8+10*7

546

12

F>C>A>B>G>E>D

E=15*5+22*4+53*5+12*2+8*2+10

478

8

G>A>F>C>B>E>D

F=15*3+22*5+53*6+12*7+8*5+10*6

657

10

D>F>A>G>C>B>E

G=15*2+22+53*7+12*3+8*7+10*4

555

Победила альтернатива F

1.2 Метод анализа иерархий

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

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

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

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

  1. Название проекта
  2. Число уровней в иерархии
  3. Максимальное количество элементов
  4. Комментарии к проекту

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

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

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

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

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

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

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

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

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

Значение ОС меньше или равное 0.10 считается приемлемым, значит матрица «выбор видеокарты» согласована.

Проведем исследование матрицы

Рис. 5 Исследование матрицы выбора

Аналогично строим матрицы для каждого из критериев на втором уровне графа.

Рис. 6 Матрица относительно первого критерия

Значение ОС меньше или равное 0.10 считается приемлемым, значит матрица «Скорость работы» согласована.

Исследуем матрицу.

Рис. 7 Исследование матрицы первого критерия

Рис. 8 Матрица относительно второго критерия

Значение ОС меньше или равное 0.10 считается приемлемым, значит матрица «Цена» согласована.

Исследуем матрицу.

Рис. 9 Исследование матрицы второго критерия

Рис. 10 Матрица относительно третьего критерия

Значение ОС меньше или равное 0.10 считается приемлемым, значит матрица «Поддержка SLI» согласована.

Исследуем матрицу.

Рис. 11 Исследование матрицы третьего критерия

Рис. 12 Матрица относительно четвертого критерия

Значение ОС меньше или равное 0.10 считается приемлемым, значит матрица «Размер видеокарты» согласована.

Исследуем матрицу.

Рис. 13 Исследование матрицы четвертого критерия

Рис. 14 Матрица относительно пятого критерия

Значение ОС меньше или равное 0.10 считается приемлемым, значит матрица «Теплоотдача» согласована.

Исследуем матрицу.

Рис. 15 Исследование матрицы пятого критерия

Рис. 16 Матрица относительно шестого критерия

Значение ОС меньше или равное 0.10 считается приемлемым, значит матрица «Энергопотребление» согласована.

Исследуем матрицу.

Рис. 17 Исследование матрицы шестого критерия

Результат

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

Рис. 20 Диаграмма результатов

1.3 Метод Электра

Цель применения методов ЭЛЕКТРА - сужение паретовского множества альтернатив. Делается это так. Для каждого из критериев (предполагается, что они - числовые) определяется по результатам опроса ЛПР «вес» - число, характеризующее важность соответствующего критерия. Во всех модификациях метода ЭЛЕКТРА делается попытка получения от ЛПР информации качественного характера об относительной важности критериев (высказывания типа «критерии 3 и 4 имеют одинаковую важность и рассматриваемые совместно имеют большую важность, чем критерий 1») и преобразования ее в количественную, числовую. Проблема здесь состоит в том, что сделать это можно в общем случае множеством способов.

Далее, для каждой пары сравниваемых альтернатив x=(x1,.....,xn) и y=(y1,.......,yn) (где n - число критериев, а для дальнейшего мы через I обозначим множество критериев, т.е. I= n) выполняются такие действия. Множество I разбивается на 3 подмножества:

I+(x,y) - множество критериев, по которым х превосходит у: x>y.

I- (x,y) - множество критериев, по которым у превосходит х: у>х.

I=(x,y) - множество критериев, по которым х и у имеют одинаковые оценки: у=х.

Определяется относительная важность P P P каждого из этих подмножеств:

    ( ,  ,)

Pi. - коэффициент относительной важности i-го критерия. Теперь мы готовы сформировать правило сравнения альтернатив х и у:

- в методе ЭЛЕКТРА-I оно таково:

, .

- в методе ЭЛЕКТРА-II оно модифицировано:

, (c 21).

Всё рассмотренное до сих пор весьма традиционно, и содержит традиционную погрешность в логических рассуждениях: получается, что очень маленький выигрыш по одному критерию может компенсировать очень большой проигрыш по другому. Для того чтобы эту трудность (погрешность) исключить, в методе «Электра» пытаются НЕ сравнивать очень сильно различающиеся альтернативы. Они просто объявляются несравнимыми. Вводится так называемый «индекс несогласия»:

 х и у несравнимы, если dxy d,

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

в ЭЛЕКТРА-I

.

в ЭЛЕКТРА-II

.

Получаемое бинарное отношение, очевидно, уже не будет обладать свойством полноты. Это учитывается и в окончательном результате ЭЛЕКТРА. Он таков. В исходном паретовском множестве выделяется т.н. ядро, состоящее из не доминируемых по новому (описанному нами) бинарному отношению элементов и всех, несравнимых с ними (т.е. любой элемент, не вошедший в ядро, доминируется хотя бы одним элементом ядра). Отметим, что, к сожалению, нельзя гарантировать цикличность отношения, получаемого описанным способом.

Таблица критериев и весов критериев.

Список альтернатив

Оценки альтернатив


Сравнение альтернатив и выражение гипотез


Результаты Dxx

Граф связей

Граф с порогами D>2

Окончательный граф

Выводы по части 1

Было изучено три метода многокритериальной оптимизации:

- Метод Парето

- Метод анализа иерархий

- Метод Электра.

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


Часть 2: Линейное программирование

2.1 Графический метод

Рассмотрим графический метод решения ЗЛП в стандартной форме с двумя переменными, т.е. задачи вида:

Найти вектор удовлетворяющий системе ограничений:

для которого функция цели Z = c1x1+c2x2 достигает максимума.

Графический метод решения ЗЛП условно можно разбить на два этапа:

  1. Построение ОДР ЗЛП.
  2. Нахождение среди всех точек ОДР такой точки в которой целевая функция принимает максимальное значение.

Перейдем к рассмотрению этих этапов.

Этап 1

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

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

.

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

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

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

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

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

линейного неравенства

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

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

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

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

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

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

а

б

в

г

д

е

ж

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

Этап 2

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

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

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

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

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

в точке М

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


Условия

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

Таблица 1

Ресурсы

Внутр. рынок

Экспорт

Объем

Сырье

8

3

21,5

Электроэнергия

-1 (экологически чистое производство, выделяющее энергию)

2

3

Время

7

10

30

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

Задание:

Найти максимум функции

F(x1,x2)= 3x1-8x2

При ограничениях:

8x1+3x221,5

-x1+2x23

7x1+10x230

x10; x20

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

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

Таблица 2

X

Y=(21,5-8X)/9

Y=(3+X)/2

Y=(30-10X)/7

Y=3X/18

0

7,166666667

1,5

4,285714286

0

0,2

6,633333333

1,6

4

0,033333333

0,4

6,1

1,7

3,714285714

0,066666667

0,6

5,566666667

1,8

3,428571429

0,1

0,8

5,033333333

1,9

3,142857143

0,133333333

1

4,5

2

2,857142857

0,166666667

1,2

3,966666667

2,1

2,571428571

0,2

1,4

3,433333333

2,2

2,285714286

0,233333333

1,6

2,9

2,3

2

0,266666667

1,8

2,366666667

2,4

1,714285714

0,3

2

1,833333333

2,5

1,428571429

0,333333333

2,2

1,3

2,6

1,142857143

0,366666667

2,4

0,766666667

2,7

0,857142857

0,4

2,6

0,233333333

2,8

0,571428571

0,433333333

2,8

-0,3

2,9

0,285714286

0,466666667

3

-0,833333333

3

0

0,5

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

Рис. 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) = 15x1+17x2+13x3 при следующих условиях-ограничений.

0.9x1+0.8x2+1.2x3≤23

0.7x1+1.1x2+0.8x3≤25

0.6x1+0.7x2+0.9x3≤24

x1≤27

x2≤25

x3≤29

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

В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6. В 4-м неравенстве смысла (≤) вводим базисную переменную x7. В 5-м неравенстве смысла (≤) вводим базисную переменную x8. В 6-м неравенстве смысла (≤) вводим базисную переменную x9.

0.9x1 + 0.8x2 + 1.2x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 + 0x9 = 23

0.7x1 + 1.1x2 + 0.8x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 + 0x9 = 25

0.6x1 + 0.7x2 + 0.9x3 + 0x4 + 0x5 + 1x6 + 0x7 + 0x8 + 0x9 = 24

1x1 + 0x2 + 0x3 + 0x4 + 0x5 + 0x6 + 1x7 + 0x8 + 0x9 = 27

0x1 + 1x2 + 0x3 + 0x4 + 0x5 + 0x6 + 0x7 + 1x8 + 0x9 = 25

0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7 + 0x8 + 1x9 = 29

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

0.9

0.8

1.2

1

0

0

0

0

0

0.7

1.1

0.8

0

1

0

0

0

0

0.6

0.7

0.9

0

0

1

0

0

0

1

0

0

0

0

0

1

0

0

0

1

0

0

0

0

0

1

0

0

0

1

0

0

0

0

0

1

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

Решим систему уравнений относительно базисных переменных: x4, x5, x6, x7, x8, x9 

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

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

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

x4

23

0.9

0.8

1.2

1

0

0

0

0

0

x5

25

0.7

1.1

0.8

0

1

0

0

0

0

x6

24

0.6

0.7

0.9

0

0

1

0

0

0

x7

27

1

0

0

0

0

0

1

0

0

x8

25

0

1

0

0

0

0

0

1

0

x9

29

0

0

1

0

0

0

0

0

1

F(X0)

0

-15

-17

-13

0

0

0

0

0

0

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

Итерация №0.

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

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

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

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

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

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

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

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

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

min

x4

23

0.9

0.8

1.2

1

0

0

0

0

0

28.75

x5

25

0.7

1.1

0.8

0

1

0

0

0

0

22.73

x6

24

0.6

0.7

0.9

0

0

1

0

0

0

34.29

x7

27

1

0

0

0

0

0

1

0

0

-

x8

25

0

1

0

0

0

0

0

1

0

25

x9

29

0

0

1

0

0

0

0

0

1

-

F(X1)

0

-15

-17

-13

0

0

0

0

0

0

0

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

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

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

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

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

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

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

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

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

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

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

x4

4.82

0.39

0

0.62

1

-0.73

0

0

0

0

x2

22.73

0.64

1

0.73

0

0.91

0

0

0

0

x6

8.09

0.15

0

0.39

0

-0.64

1

0

0

0

x7

27

1

0

0

0

0

0

1

0

0

x8

2.27

-0.64

0

-0.73

0

-0.91

0

0

1

0

x9

29

0

0

1

0

0

0

0

0

1

F(X1)

386.36

-4.18

0

-0.64

0

15.45

0

0

0

0

Итерация №1.

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

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

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

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

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

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

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

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

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

min

x4

4.82

0.39

0

0.62

1

-0.73

0

0

0

0

12.33

x2

22.73

0.64

1

0.73

0

0.91

0

0

0

0

35.71

x6

8.09

0.15

0

0.39

0

-0.64

1

0

0

0

52.35

x7

27

1

0

0

0

0

0

1

0

0

27

x8

2.27

-0.64

0

-0.73

0

-0.91

0

0

1

0

-

x9

29

0

0

1

0

0

0

0

0

1

-

F(X2)

386.36

-4.18

0

-0.64

0

15.45

0

0

0

0

0

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

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

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

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

x1

12.33

1

0

1.58

2.56

-1.86

0

0

0

0

x2

14.88

0

1

-0.28

-1.63

2.09

0

0

0

0

x6

6.19

0

0

0.15

-0.4

-0.35

1

0

0

0

x7

14.67

0

0

-1.58

-2.56

1.86

0

1

0

0

x8

10.12

0

0

0.28

1.63

-2.09

0

0

1

0

x9

29

0

0

1

0

0

0

0

0

1

F(X2)

437.91

0

0

5.98

10.7

7.67

0

0

0

0

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

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

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

x1 = 12.33

x2 = 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

Транспонированная матрица AT.

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

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

0.9y1+0.7y2+0.6y3+y4≥15

0.8y1+1.1y2+0.7y3+y5≥17

1.2y1+0.8y2+0.9y3+y6≥13

23y1+25y2+24y3+27y4+25y5+29y6min 

y1 ≥ 0

y2 ≥ 0

y3 ≥ 0

y4 ≥ 0

y5 ≥ 0

y6 ≥ 0

Исходная задача I

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

x1 ≥ 0

0.9y1+0.7y2+0.6y3+y4≥15

x2 ≥ 0

0.8y1+1.1y2+0.7y3+y5≥17

x3 ≥ 0

1.2y1+0.8y2+0.9y3+y6≥13

15x1+17x2+13x3 → max

23y1+25y2+24y3+27y4+25y5+29y6 → min

0.9x1+0.8x2+1.2x3≤23

y1 ≥ 0

0.7x1+1.1x2+0.8x3≤25

y2 ≥ 0

0.6x1+0.7x2+0.9x3≤24

y3 ≥ 0

x1≤27

y4 ≥ 0

x2≤25

y5 ≥ 0

x3≤29

y6 ≥ 0

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

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

Из первой теоремы двойственности следует, что Y = C*A-1.

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

A(a1, a2, a6, a7, a8, a9) =

0.9

0.8

0

0

0

0

0.7

1.1

0

0

0

0

0.6

0.7

1

0

0

0

1

0

0

1

0

0

0

1

0

0

1

0

0

0

0

0

0

1

Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:

А-1 =

2.56

-1.86

0

0

0

0

-1.63

2.09

0

0

0

0

-0.4

-0.35

1

0

0

0

-2.56

1.86

0

1

0

0

1.63

-2.09

0

0

1

0

0

0

0

0

0

1

Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .

Тогда Y = C*A-1 =

(15, 17, 0, 0, 0, 0) x

2.56

-1.86

0

0

0

0

-1.63

2.09

0

0

0

0

-0.4

-0.35

1

0

0

0

-2.56

1.86

0

1

0

0

1.63

-2.09

0

0

1

0

0

0

0

0

0

1

= (10,7;7,67;0;0;0;0)

Оптимальный план двойственной задачи равен:

y1 = 10.7

y2 = 7.67

y3 = 0

y4 = 0

y5 = 0

y6 = 0

Z(Y) = 23*10.7+25*7.67+24*0+27*0+25*0+29*0 = 437.91

Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.

Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности.

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

0.9*12.33 + 0.8*14.88 + 1.2*0 = 23 = 23

0.7*12.33 + 1.1*14.88 + 0.8*0 = 25 = 25

0.6*12.33 + 0.7*14.88 + 0.9*0 = 17.81 < 24

1*12.33 + 0*14.88 + 0*0 = 12.33 < 27

0*12.33 + 1*14.88 + 0*0 = 14.88 < 25

0*12.33 + 0*14.88 + 1*0 = 0 < 29

1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y1>0).

2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y2>0).

3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y3 = 0.

Неиспользованный резерв ресурса 3 составляет 6.19 (24-17.81).

4-ое ограничение выполняется как строгое неравенство, т.е. ресурс 4-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y4 = 0.

Неиспользованный резерв ресурса 4 составляет 14.67 (27-12.33).

5-ое ограничение выполняется как строгое неравенство, т.е. ресурс 5-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y5 = 0.

Неиспользованный резерв ресурса 5 составляет 10.12 (25-14.88).

6-ое ограничение выполняется как строгое неравенство, т.е. ресурс 6-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y6 = 0.

Неиспользованный резерв ресурса 6 составляет 29 (29-0).

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

Обоснование эффективности оптимального плана.

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

0.9*10.7 + 0.7*7.67 + 0.6*0 + 1*0 + 0*0 + 0*0 = 15 = 15

0.8*10.7 + 1.1*7.67 + 0.7*0 + 0*0 + 1*0 + 0*0 = 17 = 17

1.2*10.7 + 0.8*7.67 + 0.9*0 + 0*0 + 0*0 + 1*0 = 18.98 > 13

1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый продукт выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x1>0).

2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый продукт выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x2>0).

3-ое ограничение выполняется как строгое неравенство, т.е. продукцию 3-го вида использовать не выгодно. И действительно в оптимальном плане прямой задачи x3 = 0.


Заключение

В ходе выполнения курсовой работы были получены навыки по решению задач линейного программирования и нахождения оптимальных альтернатив для многокритериальных задач. Были разобраны методы Парето, Электра МАИ для многокритериальных задач, а также графический и симплекс методы решения задач линейного программирования. Также был разобран алгоритм составления и решения двойственных задач.


Список литературы

  1. Акулич М.И. “Математическое программирование в примерах и задачах” СПб.: “Лань” 2011 – 352 с.
  2. Ногин В. Д. Принятие решений в многокритериальной среде: количественный подход. –М.: ФИЗМАТЛИТ, 2002. – 144 с
  3. Лекционные материалы
  4. Интернет ресурс Wikipedia.org

 

А также другие работы, которые могут Вас заинтересовать

34810. Антропологический материализхм Фейербаха 31 KB
  Фейербаха Фейербах последний великий представитель классической немецкой философии. В отличие от других немецких философов этого периода которые были идеалистами Фейербах материалист. Самая известная книга Сущность христианства Если Гегель отрывал разум мышление от человека от его чувственной деятельности то Фейербах реальным субъектом разума считает только человека.
34811. Принцип делай добро (модель Парацельса) 30.5 KB
  Модель Парацельса это форма врачебной этики в рамках которой нравственное отношение с пациентом понимается как составляющая стратегии терапевтического поведения врача. В границах модели Парацельса в полной мере развивается патернализм как тип взаимосвязи врача и пациента. Смысл слова отец в патернализме фиксирует что образцом связей между врачом и пациентом являются не только кровнородственные отношения для которых характерны положительные психоэмоциональные привязанности и социальноморальная ответственность но и целебность ...
34812. Принцип соблюдения долга (деонтологическая модель) 32 KB
  Петров использовал этот термин чтобы обозначить реально существующую область медицинской практики врачебную этику которая в России была отменена после переворота 1917 года за ее связь с религиозной культурой. Деонтологическая модель врачебной этики это совокупность должных правил соответствующих той или иной конкретной области медицинской практики. Еще одним примером деонтологической модели являются правила относительно интимных связей между врачом и пациентом разработанные Комитетом по этическим и правовым вопросам при Американской...
34813. Принцип уважения прав и достоинства человека (биоэтика) 32.5 KB
  Эти процессы высвечивают почему в 6070х годах XX века формулируется такая форма медицинской этики как биоэтика которая начинает рассматривать медицину в контексте прав человека. Основным моральным принципом биоэтики становится принцип уважения прав и достоинства человека. Под влиянием этого принципа меняется решение основного вопроса медицинской этики вопроса об отношении врача и пациента.
34814. Особенности становления русской философии. Славянофилы и западники 53 KB
  Возникновение русской философии Термин философия или любомудрие начинает встречаться в церковных поучениях и светских рукописных книгах в XI XII вв В XIXV вв. Исторические формы русской философии возникали и существовали внутри крупных эпох развития русской культуры с XI по XIX в. начало формирования русской философии эволюция древнерусской мудрости.
34815. Религиозно-философские концепции . соловьев, Достоевский, толстой 32.5 KB
  соловьев Достоевский толстой. Соловьева Одной из важнейших концепций русской философии XIX в. Соловьева. Он может быть гарантом целостности Соловьев вопреки многим своим современникам настроенным сугубо научно не мог допустить отсутствия принципа абсолютной личности.
34816. Экзистенциальная философия Бердяева 44 KB
  Представители этого направления отвергая господствовавшие в истории классической философии принципы рационализма характерные прежде всего для философии Гегеля обратились в своем творчестве к интуитивным эмоциональноволевым и Iт. Предмет и задачи философии Бердяев однозначно определяет с экзистенциальноантропологических позиций: философия призвана познавать бытие из человека и через человека черпая содержание свое в духовном опыте и духовной жизни. Показав что объект порождается субъектом Кант раскрыл возможность построения...
34817. Русский космизм. Федоров Вернадский Циолковский 31 KB
  Федоров Вернадский Циолковский Косми́зм греч. Вернадский Владимир Иванович Вернадский 1863 1945. Ныне подобные эксперименты кажутся губительными для окружающей среды но Вернадский был оптимистом.
34818. Проблемы научной рациональности в современной «философии науки»: позитивизм, неопозивитивизм, постопозитивизм, прагматизм 39 KB
  Направление в философии утверждающее что единственным источником подлинного знания являются специальные науки и отрицающее философию как особую отрасль знаний НЕОПОЗИТИВИЗМ одно из основных направлений философии 20 в. Неопозитивизм сыграл значительную роль в развитии современной логики семиотики и философии науки. Постпозитиви́зм общее название для нескольких школ философии науки объединённых критическим отношением к эпистемологическим учениям которые были развиты в рамках неопозитивизма и обосновывали получение объективного знания из...