Лабораторная работа №1 Двойственная задача линейного программирования по дисциплине \" Математические методы исследования операций \" icon

Лабораторная работа №1 Двойственная задача линейного программирования по дисциплине " Математические методы исследования операций "




Скачати 67.14 Kb.
НазваЛабораторная работа №1 Двойственная задача линейного программирования по дисциплине " Математические методы исследования операций "
Дата конвертації09.04.2013
Розмір67.14 Kb.
ТипЛабораторная работа

Министерство образования и науки Украины

Национальный горный университет


Институт электроэнергетики

Факультет информационных технологий




Кафедра СА и У




Лабораторная работа №1


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

по дисциплине



Математические методы исследования операций ”


ВЫПОЛНИЛА:

студент группы КС-06-2

Спектр Е.И.

ПРОВЕРИЛА:


ас. Шевченко Ю.А.





Днепропетровск
2009




  1. Цель работы: получить навыки в решении многокритериальных задач ИСО.

  2. Краткие теоретические сведения.

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

1) Замена некоторых критериев ограничениями вида ≤ или ≥. Например, минимизация стоимости , может быть заменена ограничением вида , где A некоторая верхняя оценка стоимости, т.е. максимально допустимая стоимость.

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

3) Ранжирование критериев. Критерии ранжируются по степени важности.

4) Отыскание решений, лучших хотя бы по одному критерию.

Подходы 1) и 2) приводят к однокритериальной задаче.

Подход 3) приводит к задаче с упорядоченными критериями.

Подход 4) приводит к задаче с независимыми критериями.

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




В задаче с независимыми критериями требуется найти множество недоминируемых (эффективных) решений. Недоминируемое решение лучше любого другого допустимого решения хотя бы по одному критерию либо не хуже по всем критериям. Множество недоминируемых решений также называется множеством Парето.

  1. Постановка задачи.

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

Обозначим, соответственно, через - номер, - время изготовления и доставки, - закупочную стоимость варианта закупки оборудования. Значения функций и ( ) заданы таблицей:


Вариант № 17


xi

1

2

3

4

5

6

7

8

F1(xi)

17

17

17

18

18

19

19

20

F2(xi)

19

20

21

18

19

19

20

18


Задание № 1

Для заданной двухкритериальной задачи, задавшись коэффициентами α и β провести свертку критериев F1(x) и F2(x) и определить минимальное решение.


Пусть α=0.1, β=0.2

ψ(xi) = α * F1(xi) + β* F2(xi)


xi

1

2

3

4

5

6

7

8

F1(xi)

17

17

17

18

18

19

19

20

F2(xi)

19

20

21

18

19

19

20

18

ψ(xi)

5,5

5,7

5,9

5
*
,4

5,6

5,7

5,9

5,6


ƒ(х)→min, при ψ(x) = 5,4 (Вариант 4)


Ответ: ƒ(х)→min, при ψ(x) = 5,4 (Вариант 4)


Задание № 2

Для заданной двухкритериальной задачи, считая критерий F2(x) более важным, чем F1(x) определить минимальное решение.


xi

1

2

3

4

5

6

7

8

F1(xi)

17

17

17

18

18

19

19

20

F2(xi)

19

20

21

1
*
8

19

19

20

1
*
8


Минимизировав по F2(x) выбираем варианты (4) и (8).

Затем, минимизировав по F1 выбираем вариант (4), где F1(xi) = 18


Ответ: ƒ(х)→min, при F1(xi) = 18 (Вариант 4)


Задание № 3

Для заданной двухкритериальной задачи найти множество Парето в случае двух критериев вида F1(x)→min и F2(x)→min


Задача отыскивания множества Парето в случае двух критериев может быть решена графически:



  1. Строим график





  1. Находим все точки с наименьшим min значением F1(x). Если их несколько, выбираем точку с наименьшим значением F2(x). В нашем случае это точка (17,19).

  2. Отсекаем точки с большими либо равными значениями F1(x) и F2(x) Повторяем процедуру для остальной части допустимой области. Находим точку (18,18).


Итак, мы получили точки (17,19) и (18,18). Множество Парето состоит из двух точек. Они соответствуют вариантам (1) и (4) соответственно.


Ответ: х={1,4}




Схожі:

Лабораторная работа №1 Двойственная задача линейного программирования по дисциплине \" Математические методы исследования операций \" iconЛабораторная работа №2 Двойственная задача линейного программирования по дисциплине: " Математические методы исследования операций "
Цель работы: получить навыки в переходе к двойственной задаче линейного программирования и решении задач линейного программирования...
Лабораторная работа №1 Двойственная задача линейного программирования по дисциплине \" Математические методы исследования операций \" iconЛабораторная работа №3 Решение задач безусловной оптимизации по дисциплине: " Математические методы исследования операций "
Проверить заданные функции одной переменной на наличие локальных и глобальных экстремумов
Лабораторная работа №1 Двойственная задача линейного программирования по дисциплине \" Математические методы исследования операций \" iconЛабораторная работа №1 Изучение способов разработки простейших com-объектов в среде delphi по дисциплине " тпспп "
Разработать в среде Delphi простой com-объект в составе внутреннего сервера, реализующий набор методов, согласно заданному варианту....
Лабораторная работа №1 Двойственная задача линейного программирования по дисциплине \" Математические методы исследования операций \" iconКонтрольная работа по дисциплине: теории технических систем расчет оптимального маршрута обработки заготовки, обеспечивающего наименьшую себестоимость, методом динамического программирования
...
Лабораторная работа №1 Двойственная задача линейного программирования по дисциплине \" Математические методы исследования операций \" iconЛабораторная работа №2 разработка объекта автоматизации в среде delphi по дисциплине " тпспп "
Определение наибольшей из сторон треугольника, координаты вершин (x1, y1), (x2, y2) и (x3, y3)
Лабораторная работа №1 Двойственная задача линейного программирования по дисциплине \" Математические методы исследования операций \" iconЛабораторная работа №3 разработка элементов activex в среде delphi по дисциплине " тпспп "
Определение наибольшей из сторон треугольника, координаты вершин (x1, y1), (x2, y2) и (x3, y3)
Лабораторная работа №1 Двойственная задача линейного программирования по дисциплине \" Математические методы исследования операций \" iconЛабораторная работа №9 Исключение кириллизованного текста в информации классов по дисциплине " авпз "
Переименуем классы и их спецификации таким образом, чтобы использовался только латинский шрифт. Заменим имя класса
Лабораторная работа №1 Двойственная задача линейного программирования по дисциплине \" Математические методы исследования операций \" iconПрактикум по программированию Лабораторная работа №3 Лабораторная работа №3 Обработка естественного языка
Цель: познакомиться с основными понятиями исчисления высказываний; изучить понятие правило вывода, научиться строить правила вывода...
Лабораторная работа №1 Двойственная задача линейного программирования по дисциплине \" Математические методы исследования операций \" iconЛабораторная работа №8 Описание связей между классами по дисциплине " авпз "
Цель работы. В данной лабораторной работе определяются связи между классами, участвующими в варианте использования "Ввести новый...
Лабораторная работа №1 Двойственная задача линейного программирования по дисциплине \" Математические методы исследования операций \" iconЛабораторная работа №3. Статистические методы планирования экспериментов при идентификации систем управления
...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©te.zavantag.com 2000-2017
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи