Теория принятия решений

Федеральное агентство  по образованию

Государственное образовательное учреждение высшего  профессионального образования

ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ  НЕФТЕГАЗОВЫЙ УНИВЕРСИТЕТ

ИНСТИТУТ НЕФТИ И  ГАЗА

КАФЕДРА ИНФОРМАТИКИ  И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

 

 

 

 

 

 

КУРСОВОЙ ПРОЕКТ

по дисциплине «Теория принятия решений»

 

 

 

 

 

 

Выполнил:

студент группы

 

Проверил:

Гапанович И.В.

 

 

 

 

 

 

 

Тюмень, 2013

 

СОДЕРЖАНИЕ

 

1. ПОСТАНОВКА ЗАДАЧИ

 

В аптеке продается семь наименований поливитаминов. Каждое наименование содержит витамины трех различных типов. Цены на витамины различны. Необходимо пройти профилактический курс, в течение которого с минимальными суммарными затратами получить 100 единиц витамина А, 80 – витамина С и 120 единиц витамина В₆. Необходимое количество поливитаминов покупается одновременно.

 

Витамины	Содержание витаминов, ед./г							Всего необходимо
	Р1	Р2	Р3	Р4	Р5	Р6	Р7
А С В6	5 3 1	0 1 0	2 5 3	0 0 1	3 2 2	1 0 0	2 1 6	100 80 120
Цена за 1 г, тыс.р	4	1	5	6	3,5	7	4

 

Каковы минимальные  затраты на профилактический курс?

 

 

2. ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ

 

Переменные. Так как необходимо определить объем затрат на профилактический курс, т.е. необходимо определить объём затрат на каждый вид витаминов, то переменными в модели являются:

x₁ – количество поливитамина 1 вида

x₂ – количество поливитамина 2 вида

x₃ – количество поливитамина 3 вида

x₄ – количество поливитамина 4 вида

x₅ – количество поливитамина 5 вида

x₆ – количество поливитамина 6 вида

x₇ – количество поливитамина 7 вида

 

Целевая функция.

1. Так как цена на поливитамины 1 вида равна 4 тыс.р., то расход на x₁ грамм будет равен 4x₁ тыс р.
2. Так как цена на поливитамины 2 вида равна 1 тыс.р., то расход на x₂ грамм будет равен 1x₂ тыс р.
3. Так как цена на поливитамины 3 вида равна 5 тыс.р., то расход на x₃ грамм будет равен 5x₃ тыс р.
4. Так как цена на поливитамины 4 вида равна 6 тыс.р., то расход на x₄ грамм будет равен 6x₄ тыс р.
5. Так как цена на поливитамины 5 вида равна 3.5 тыс.р., то расход на x₅ грамм будет равен 3.5x₅ тыс р.
6. Так как цена на поливитамины 6 вида равна 7 тыс.р., то расход на x₆ грамм будет равен 7x₆ тыс р.
7. Так как цена на поливитамины 7 вида равна 4 тыс.р., то расход на x₇ грамм будет равен 4x₇ тыс р.

 

Обозначив общие затраты (в тысячах рублей) через F, можно дать следующую математическую формулировку целевой функции: определить допустимые значения x₁, x₂, x₃, x₄, x_5, x_6, x₇ минимизирующие величину общего расхода

 

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

 

5x₁ + 2x₃ +3х₅ + 6х₆ + 2х₇ ≥100  

3x₁ + х₂ + 5x₃ +2х₅ + х₈ ≥ 80  

x₁ + 3x₃ + х₄ + х₅ + 6х₉ ≥ 120  

 

Неявное ограничение:

 

x₁, x₂, x₃, x₄, х_5, х_6, х_{7, X8,}  x₉ >=  0

 

Итак, математическую задачу можно  записать следующим образом:

 

Определить минимальные затраты на витамины т.е. определить значения переменных x₁, x₂, x₃, x₄, х_5, х_6, х₇ при которых:

 

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

5x₁ + 2x₃ +3х₅ + 6х₆ + 2х₇ ≥ 100  

3x₁ + х₂ + 5x₃ +2х₅ + х₈ ≥ 80  

x₁ + 3x₃ + х₄ + х₅ + 6х₉ ≥120  

 

 

 

 

 

 

3. ВЫБОР, ОБОСНОВАНИЕ  И ОПИСАНИЕ МЕТОДА РЕШЕНИЙ  ПОСТАВЛЕННОЙ ЗАДАЧИ

 

Т.к. все входящие в модель функции (ограниченная и целевая функция) являются линейными, то данная задача относится к классу задач линейного программирования (ЛП), поэтому для её решения необходимо применить один из методов решения задач ЛП. Универсальный метод решения таких задач – симплекс-метод.

 

Описание  симплекс-метода

Экстремум целевой функции всегда достигается в угловых точках области допустимых решений. Симплекс-метод, называемый также методом последовательного улучшения плана, реализует перебор угловых точек области допустимых решений в направлении улучшения значения целевой функции. Основная идея этого метода следующая. Прежде всего, находится какое-либо допустимое начальное (опорное) решение, т.е. какая-либо угловая точка области допустимых решений. Процедура метода позволяет ответить на вопрос,  является ли это решение оптимальным. Если "да", то задача решена. Если "нет", то выполняется переход к смежной угловой точке области допустимых решений, где значение целевой функции улучшается, т.е. к нехудшему допустимому решению. Если некоторая угловая точка имеет несколько смежных, то вычислительная процедура метода обеспечивает переход к той из них, для которой улучшение целевой функции будет наибольшим. Процесс перебора угловых точек области допустимых решений повторяется, пока не будет найдена точка, которой соответствует экстремум целевой функции Z.

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

5x₁ + 2x₃ +3х₅ + 6х₆ + 2х₇ – x₈ = 100  

3x₁ + х₂ + 5x₃ +2х₅ + х₇ – x₉= 80  

x₁ + 3x₃ + х₄ + х₅ + 6х₇ – x₁₀= 120  

 

 

 

4. РЕШЕНИЕ СФОРМУЛИРОВАННОЙ ЗАДАЧИ

Решим сформулированную задачу с помощью  симплекс-метода. Для этого запишем  целевую функцию в виде: F-4x₁-x₂-5x₃-6x₄-3.5x₅-7x₆-4x₇=0 и запишем исходные данные в симплекс-таблицу.

Поскольку задача на минимум для  решения умножим все строки на -1:

x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
-5	0	-2	0	-3	-1	-2	1	0	0
-3	-1	-5	0	-2	0	-1	0	1	0
-1	0	-3	-1	-2	0	-6	0	0	1
4	1	5	6	3.5	7	4	0	0	0

 

 

 

 

 

 

 

Находим исходное опорное решение:

	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9	x 10		min
x8	0	0	13	5	7	-1	28	1	0	-5	500	100
x9	0	-1	4	3	4	0	17	0	1	-3	280	93.33
x1	1	0	3	1	2	0	6	0	0	-1	120	120
F	0	1	-7	2	-4.5	7	-20	0	0	4	-480	0

 

 

 

 

 

 

 

 

Все элементы в базисном столбце  положительные, т.е. перходим к основному алгоритму симплекс метода:

 

	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9	x 10		min
x8	0	1.67	6.33	0	0.33	-1	-0.33	1	-1.67	0	33.33	0
x4	0	-0.33	1.33	1	1.33	0	5.67	0	0.33	-1	93.33	16.47
x1	1	0.33	1.67	0	0.67	0	0.33	0	-0.33	0	26.67	80
F	0	1.67	-9.67	0	-7.17	7	-31.33	0	-0.67	6	-666.67	0

 

	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9	x 10	В	min
x8	0	1.65	6.41	0.06	0.41	-1	-0	1	-1.65	-0.06	38.82	6.06
x7	0	-0.06	0.24	0.18	0.24	0	1	0	0.06	-0.18	16.47	70
x1	1	0.35	1.59	-0.06	0.59	0	0	0	-0.35	0.06	21.18	13.33
F	0	-0.18	-2.29	5.53	0.21	7	-0	0	1.18	0.47	-150.59	0

 

Базис	x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8	x 9	x 10		min
x3	0	0.26	1	0.01	0.06	-0.16	0	0.16	-0.26	-0.01	6.06	6.06
x7	0	-0.12	0	0.17	0.22	0.04	1	-0.04	0.12	-0.17	15.05	70
x1	1	-0.06	0	-0.07	0.49	0.25	0	-0.25	0.06	0.07	11.56	13.33
F	0	0.41	-0	5.55	0.35	6.64	0	0.36	0.59	0.45	-136.7	0

 

 

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

F(X) = 4*11.56 + 5*6.06 + 4*15.05 = 136.7

 

 x1 = 11.56;   x2 = 0;   x3 = 6.06;   x4 = 0;   x5 = 0;   x6 = 0;  x7 = 15.05

 

 

 

 

5. АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ

 

Оптимальное решение

 

Используя данные, содержащиеся в  симплекс-таблице для оптимального решения, основные результаты можно  представить так (округление до тысячных):

 

Таблица 2

Управляемые переменные	Оптимальное значение
x1	6.06
x2	0
x3	6.06
x4	0
x5	0
x6	0
x7	15.05
F	136.7

 

 

Максимальное изменение  коэффициентов стоимости

1) Предположим, что стоимость  1 грамма поливитаминов 1 вида изменяется до 4 + δ₁, где δ₁ может принимать как положительное, так и отрицательное значение. Целевая функция в этом случае имеет вид: