Автор работы: Пользователь скрыл имя, 02 Февраля 2015 в 14:21, курсовая работа
Цель работы - исследование метода идеальной точки при решении многоцелевых задач линейного программирования.
Исходя из цели работы, можно поставить следующие задачи:
Изучить теоретические сведения, необходимые для решения задач линейного программирования методом идеальной точки.
2) Решить поставленные задачи, используя рассмотренный метод решения задач линейного программирования.
Введение 3
1 Общая постановка многоцелевой задачи линейного программирования 5
2 Метод идеальной точки решения многоцелевых задач линейного программирования 7
3 ЕЩЕ ОДИН АНАЛИТИЧЕСКИЙ МЕТОД РЕШЕНИЯ МНОГОЦЕЛЕВОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ …………………...16
Заключение 25
Список использованных источников 26
Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не
оптимально. Для определения ведущего столбца найдем максимальный по
модулю отрицательный элемент в строке F (-2). А ведущая строка та, у которой наименьшее
положительное отношение свободного члена к соответствующему элементу ведущего столбца.
Пересчитаем таблицу
Базисные |
Свободные |
X6 |
X2 |
X1 |
3 |
1 |
-2 |
X4 |
20 |
-4 |
16 |
X5 |
1 |
-1 |
3 |
X3 |
2 |
1 |
-3 |
F |
6 |
2 |
-5 |
Так
как в столбце свободных членов нет отрицательных элементов, то
найдено допустимое решение. Так как
в строке F есть отрицательные элементы, то полученное решение не
оптимально. Для определения ведущего столбца найдем максимальный по
модулю отрицательный элемент в строке F (-5). А ведущая строка та,
у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.
Пересчитаем таблицу
Базисные |
Свободные |
X6 |
X5 |
X1 |
3.7 |
0.3 |
0.7 |
X4 |
14.7 |
1.3 |
-5.3 |
X2 |
0.3 |
-0.3 |
0.3 |
X3 |
3 |
0 |
1 |
F |
7.7 |
0.3 |
1.7 |
Найдено оптимальное решение.
Решим симплекс - методом для второй целевой функции.
Помножим 1-e неравенство на -1. Введем дополнительные переменные X3, X4, X5, X6.
F(X)=2X1+2X2 (max)
Ограничения:
-1 |
X1 |
- |
1 |
X2 |
+ |
X3 |
= |
-1 |
4 |
X1 |
+ |
8 |
X2 |
+ |
X4 |
= |
32 |
1 |
X1 |
+ |
1 |
X2 |
+ |
X5 |
= |
4 |
1 |
X1 |
- |
2 |
X2 |
+ |
X6 |
= |
3 |
Xi≥0
Составим симплекс таблицу:
Базисные |
Свободные |
X1 |
X2 |
X3 |
-1 |
-1 |
-1 |
X4 |
32 |
4 |
8 |
X5 |
4 |
1 |
1 |
X6 |
3 |
1 |
-2 |
F |
0 |
-2 |
-2 |
Для нахождения ведущей строки найдем максимальный по
модулю отрицательный свободный член (-1). Ведущая строка - X3. В строке X3 так же найдем максимальный по модулю отрицательный свободный член (-1). Столбец X1- ведущий.
Пересчитаем таблицу
Базисные |
Свободные |
X3 |
X2 |
X1 |
1 |
-1 |
1 |
X4 |
28 |
4 |
4 |
X5 |
3 |
1 |
0 |
X6 |
2 |
1 |
-3 |
F |
2 |
-2 |
0 |
Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-2). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.
Пересчитаем таблицу
Базисные |
Свободные |
X6 |
X2 |
X1 |
3 |
1 |
-2 |
X4 |
20 |
-4 |
16 |
X5 |
1 |
-1 |
3 |
X3 |
2 |
1 |
-3 |
F |
6 |
2 |
-6 |
Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-6). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.
Пересчитаем таблицу
Базисные |
Свободные |
X6 |
X5 |
X1 |
3.7 |
0.3 |
0.7 |
X4 |
14.7 |
1.3 |
-5.3 |
X2 |
0.3 |
-0.3 |
0.3 |
X3 |
3 |
0 |
1 |
F |
8 |
0 |
2 |
Найдено оптимальное решение.
3 ЕЩЕ ОДИН АНАЛИТИЧЕСКИЙ МЕТОД РЕШЕНИЯ МНОГОЦЕЛЕВОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
На основе полученных решений в предыдущей главе, для нашего примера составим новую задачу: . Применим также симплекс - метод.
Помножим 1-e, 2-e, 3-e неравенства на -1. Введем дополнительные переменные X4, X5, X6, X7, X8, X9.
F(X)=+1X3 (min)
Ограничения:
-2X1 |
- |
1X2 |
- |
7.7X3 |
+X4 |
= |
-7.7 |
-2X1 |
- |
2X2 |
- |
8X3 |
+X5 |
= |
-8 |
-1X1 |
- |
1X2 |
+ |
0X3 |
+X6 |
= |
-1 |
4X1 |
+ |
8X2 |
+ |
0X3 |
+X7 |
= |
32 |
1X1 |
+ |
1X2 |
+ |
0X3 |
+X8 |
= |
4 |
1X1 |
- |
2X2 |
+ |
0X3 |
+X9 |
= |
3 |
Xi≥0
Составим симплекс таблицу:
Базисные |
Свободные |
X1 |
X2 |
X3 |
X4 |
-7.7 |
-2 |
-1 |
-7.7 |
X5 |
-8 |
-2 |
-2 |
-8 |
X6 |
-1 |
-1 |
-1 |
0 |
X7 |
32 |
4 |
8 |
0 |
X8 |
4 |
1 |
1 |
0 |
X9 |
3 |
1 |
-2 |
0 |
F |
0 |
0 |
0 |
1 |
Для нахождения ведущей строки найдем максимальный по модулю отрицательный свободный член (-8). Ведущая строка - X5. В строке X5 так же найдем максимальный по модулю отрицательный свободный член (-8). Столбец X3- ведущий.
Пересчитаем таблицу
Базисные |
Свободные |
X1 |
X2 |
X5 |
X4 |
0 |
-0.08 |
0.93 |
-0.96 |
X3 |
1 |
0.25 |
0.25 |
-0.13 |
X6 |
-1 |
-1 |
-1 |
0 |
X7 |
32 |
4 |
8 |
0 |
X8 |
4 |
1 |
1 |
0 |
X9 |
3 |
1 |
-2 |
0 |
F |
-1 |
-0.25 |
-0.25 |
0.13 |
Для нахождения ведущей строки найдем максимальный по модулю отрицательный свободный член (-1). Ведущая строка - X6. В строке X6 так же найдем максимальный по модулю отрицательный свободный член (-1). Столбец X1- ведущий.
Пересчитаем таблицу
Базисные |
Свободные |
X6 |
X2 |
X5 |
X4 |
0.08 |
-0.08 |
1 |
-0.96 |
X3 |
0.75 |
0.25 |
0 |
-0.13 |
X1 |
1 |
-1 |
1 |
0 |
X7 |
28 |
4 |
4 |
0 |
X8 |
3 |
1 |
0 |
0 |
X9 |
2 |
1 |
-3 |
0 |
F |
-0.75 |
-0.25 |
0 |
0.13 |