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

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-0.25). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.

 
Пересчитаем таблицу

Базисные  переменные	Свободные  члены	X9	X2	X5
X4	0.23	0.08	0.78	-0.96
X3	0.25	-0.25	0.75	-0.13
X1	3	1	-2	0
X7	20	-4	16	0
X8	1	-1	3	0
X6	2	1	-3	0
F	-0.25	0.25	-0.75	0.13

 

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-0.75). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца. 
Пересчитаем таблицу

 

Базисные  переменные	Свободные  члены	X9	X4	X5
X2	0.29	0.1	1.29	-1.24
X3	0.03	-0.32	-0.97	0.81
X1	3.58	1.19	2.58	-2.48
X7	15.35	-5.55	-20.65	19.87
X8	0.13	-1.29	-3.87	3.73
X6	2.87	1.29	3.87	-3.73
F	-0.03	0.32	0.97	-0.81

 

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-0.81). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.

Пересчитаем таблицу

Базисные  переменные	Свободные  члены	X9	X4	X8
X2	0.33	-0.33	0	0.33
X3	0	-0.04	-0.13	-0.22
X1	3.67	0.33	0	0.67
X7	14.67	1.33	0	-5.33
X5	0.03	-0.35	-1.04	0.27
X6	3	0	0	1
F	-0	0.04	0.13	0.22

 
Найдено оптимальное решение.

Если использовать метрику s=1, необходимо решить задачу следующего вида:

j(x) = -f1 (x)-f2 (x) ®  min    

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

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

-1X1-1X2+X3=-1 
4X1+8X2+X4=32 
1X1+1X2+X5=4 
1X1-2X2+X6=3 
Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции. Так как нам необходимо найти максимум целевой функции, то в таблицу заносятся коэффициенты с противоположным знаком. 
Из данных задачи составляем исходную симплекс таблицу.

 

	X1	X2	Свободный член
F	-4	-3	0
X3	-1	-1	-1
X4	4	8	32
X5	1	1	4
X6	1	-2	3

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

 

 

 

 

	X3	X2	Свободный       член
F	-4	1	4
X1	-1	1	1
X4	4	4	28
X5	1	0	3
X6	1	-3	2

 
Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. В строке F имеются отрицательные элементы, это означает что полученное решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент - это -4 Ведущей строкой будет та, для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X6, а ведущий элемент: 1.

 

	X6	X2	Свободный       член
F	4	-11	12
X1	1	-2	3
X4	-4	16	20
X5	-1	3	1
X3	1	-3	2

 

В строке F имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент - это -11 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X5, а ведущий элемент: 3.

 

	X6	X5	Свободный       член
F	0.3	3.7	15.7
X1	0.3	0.7	3.7
X4	1.3	-5.3	14.7
X2	-0.3	0.3	0.3
X3	0	1	3

 

 

 

 

 

 

 

 

 

 

Так как в строке F нет отрицательных элементов, то найдено оптимальное решение F=15.7 
при значениях переменных равных: X1=3.7, X2=0.3.

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

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

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

 

 

 

Список использованных источников

 

1. Ларичев О.И. Теория и методы принятия решений, а также Хроника событий в Волшебных странах: Учебник. Изд.третье, перераб. и доп.- М.:       Университетская книга, Логос, 2006.-392 с.: ил.
2. В.Н.Добрынин и др. Математические методы системного анализа
3. С.А.Ашманов. Линейное программирование
1.   О. А .Косоруков. Исследование операций
4. Таха, Хемди А. Введение в исследование операций, 7-е издание.: Пер. с    англ. - М.: Издательский дом "Вильямс", 2005. - 912 с: ил.
5. Е.Г.Пьяных. Методы оптимизации
6. А.В.Пантелеев, Т.А.Летова. Методы оптимизации в примерах и задачах
7. М.В.Гречишкина, Д.Е.Ивахник. Выбор оптимального варианта инвестиций (оптимизационный подход) // Финансовый менеджмент. - №3. - 2003.