Теория принятия решений
Постановка задачи и построение ее математической модели. Запись переменных, целевой функции, неявного ограничения. Выбор, обоснование и описание метода решений поставленной задачи. Описание симплекс-метода. Проведение анализа модели на чувствительность.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 29.01.2014 |
| Размер файла | 29,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЕГАЗОВЫЙ УНИВЕРСИТЕТ
ИНСТИТУТ НЕФТИ И ГАЗА
КАФЕДРА ИНФОРМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
КУРСОВОЙ ПРОЕКТ
по дисциплине "Теория принятия решений"
Тюмень, 2013
Содержание
- 1. Постановка задачи
- 2. Построение математической модели
- 3. Выбор, обоснование и описание метода решений поставленной задачи
- 4. Решение сформулированной задачи
- 5. Анализ модели на чувствительность
- Список литературы
1. Постановка задачи
В аптеке продается семь наименований поливитаминов. Каждое наименование содержит витамины трех различных типов. Цены на витамины различны. Необходимо пройти профилактический курс, в течение которого с минимальными суммарными затратами получить 100 единиц витамина А, 80 - витамина С и 120 единиц витамина В6. Необходимое количество поливитаминов покупается одновременно.
|
Витамины |
Содержание витаминов, ед./г |
Всего необходимо |
|||||||
|
Р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. Построение математической модели
Переменные. Так как необходимо определить объем затрат на профилактический курс, т.е. необходимо определить объём затрат на каждый вид витаминов, то переменными в модели являются:
x1 - количество поливитамина 1 вида
x2 - количество поливитамина 2 вида
x3 - количество поливитамина 3 вида
x4 - количество поливитамина 4 вида
x5 - количество поливитамина 5 вида
x6 - количество поливитамина 6 вида
x7 - количество поливитамина 7 вида
Целевая функция.
1) Так как цена на поливитамины 1 вида равна 4 тыс.р., то расход на x1 грамм будет равен 4x1 тыс р.
2) Так как цена на поливитамины 2 вида равна 1 тыс.р., то расход на x2 грамм будет равен 1x2 тыс р.
3) Так как цена на поливитамины 3 вида равна 5 тыс.р., то расход на x3 грамм будет равен 5x3 тыс р.
4) Так как цена на поливитамины 4 вида равна 6 тыс.р., то расход на x4 грамм будет равен 6x4 тыс р.
5) Так как цена на поливитамины 5 вида равна 3.5 тыс.р., то расход на x5 грамм будет равен 3.5x5 тыс р.
6) Так как цена на поливитамины 6 вида равна 7 тыс.р., то расход на x6 грамм будет равен 7x6 тыс р.
7) Так как цена на поливитамины 7 вида равна 4 тыс.р., то расход на x7 грамм будет равен 4x7 тыс р.
Обозначив общие затраты (в тысячах рублей) через F, можно дать следующую математическую формулировку целевой функции: определить допустимые значения x1, x2, x3, x4, x5, x6, x7 минимизирующие величину общего расхода
Ограничения. При решении рассматриваемой задачи должны быть учтены ограничения на необходимость поливитаминов. Ограничения можно записать следующим образом:
5x1 + 2x3 +3х5 + 6х6 + 2х7 ?100
3x1 + х2 + 5x3 +2х5 + х8 ? 80
x1 + 3x3 + х4 + х5 + 6х9 ? 120
Неявное ограничение:
x1, x2, x3, x4, х5, х6, х7, X8, x9 >= 0
Итак, математическую задачу можно записать следующим образом:
Определить минимальные затраты на витамины т.е. определить значения переменных x1, x2, x3, x4, х5, х6, х7 при которых:
при ограничениях:
5x1 + 2x3 +3х5 + 6х6 + 2х7 ? 100
3x1 + х2 + 5x3 +2х5 + х8 ? 80
x1 + 3x3 + х4 + х5 + 6х9 ?120
3. Выбор, обоснование и описание метода решений поставленной задачи
Т.к. все входящие в модель функции (ограниченная и целевая функция) являются линейными, то данная задача относится к классу задач линейного программирования (ЛП), поэтому для её решения необходимо применить один из методов решения задач ЛП. Универсальный метод решения таких задач - симплекс-метод.
Описание симплекс-метода
Экстремум целевой функции всегда достигается в угловых точках области допустимых решений. Симплекс-метод, называемый также методом последовательного улучшения плана, реализует перебор угловых точек области допустимых решений в направлении улучшения значения целевой функции. Основная идея этого метода следующая. Прежде всего, находится какое-либо допустимое начальное (опорное) решение, т.е. какая-либо угловая точка области допустимых решений. Процедура метода позволяет ответить на вопрос, является ли это решение оптимальным. Если "да", то задача решена. Если "нет", то выполняется переход к смежной угловой точке области допустимых решений, где значение целевой функции улучшается, т.е. к нехудшему допустимому решению. Если некоторая угловая точка имеет несколько смежных, то вычислительная процедура метода обеспечивает переход к той из них, для которой улучшение целевой функции будет наибольшим. Процесс перебора угловых точек области допустимых решений повторяется, пока не будет найдена точка, которой соответствует экстремум целевой функции Z.
Поскольку рассматриваемая задача решается с помощью симплекс метода, то необходимо ограничения записать в виде равенств, вводя в каждое ограничение соответствующую остаточную переменную:
5x1 + 2x3 +3х5 + 6х6 + 2х7 - x8 = 100
3x1 + х2 + 5x3 +2х5 + х7 - x9= 80
x1 + 3x3 + х4 + х5 + 6х7 - x10= 120
4. Решение сформулированной задачи
Решим сформулированную задачу с помощью симплекс-метода. Для этого запишем целевую функцию в виде: F-4x1-x2-5x3-6x4-3.5x5-7x6-4x7=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. Анализ модели на чувствительность
математический ограничение симплекс чувствительность
Оптимальное решение
Используя данные, содержащиеся в симплекс-таблице для оптимального решения, основные результаты можно представить так (округление до тысячных):
|
Управляемые переменные |
Оптимальное значение |
|
|
x1 |
6.06 |
|
|
x2 |
0 |
|
|
x3 |
6.06 |
|
|
x4 |
0 |
|
|
x5 |
0 |
|
|
x6 |
0 |
|
|
x7 |
15.05 |
|
|
F |
136.7 |
Максимальное изменение коэффициентов стоимости
1) Предположим, что стоимость 1 грамма поливитаминов 1 вида изменяется до 4 + д1, где д1 может принимать как положительное, так и отрицательное значение. Целевая функция в этом случае имеет вид:
Проведя необходимые симплексные преобразования получим следующее F-уравнение в последней симплекс-таблице (округление до тысячных):
Таблица
|
Решение |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
||
|
Z |
136.7+ 11.56д1 |
0 |
0.41-0.06д1 |
0 |
5.55-0.07д1 |
0.35+0.49д1 |
6.64+0.25д1 |
0 |
0.36-0.25д1 |
0.59 + 0.06д1 |
0.45 +0.07д1 |
Оптимальные значения переменных будут оставаться неизменными при значениях д1, удовлетворяющих условию неотрицательности всех коэффициентов при небазисных переменных в F-уравнении. Таким образом, должны выполняться следующие неравенства:
0.41-0.06д1? 0
5.55-0.07д1? 0
0.35+0.49д1? 0
6.64+0.25д1? 0
.36-0.25д1? 0
0.59 + 0.06д1? 0
0.45 +0.07д1? 0
Решая эту систему, получаем (округление до тысячных):
-26.56 ? д1 ? 79.3
Таким образом, если -26.56 ? д1 ? 79.3, то оптимальные значения переменных останутся неизменными, а оптимальное значение F изменится в соответствии с выражением:
136.7+ 11.56д1
Список литературы
1. Аснина А. Я., Баева Н. Б., Чернышова Г. Д. вычислительные методы линейной оптимизации - Воронеж: Издательство воронежского университета, 1987
2. Банди Б. Основы линейного программирования - М: Радио и связь, 1989
3. Таха. Х. А. Введение в исследование операций. - М: Вильямс, 2005.
4. Шевченко В. Н., Золотых Н. Ю. - Линейное и целочисленное линейное программирование - Н. Новгород: Издательство Нижегородского университета им. Н. И. Лобачевского, 2004
Размещено на Allbest.ru
Подобные документы
Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.
контрольная работа [66,3 K], добавлен 06.04.2012Теоретические положения симплекс-метода и постоптимального анализа. Построение математической модели задачи. Нахождение ценностей ресурсов. Определение относительных и абсолютных диапазонов изменения уровней запасов дефицитных и недефицитных ресурсов.
курсовая работа [86,7 K], добавлен 19.11.2010Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.
курсовая работа [219,4 K], добавлен 17.04.2013Нахождение экстремумов функций методом множителей Лагранжа. Выражение расширенной целевой функции. Схема алгоритма численного решения задачи методом штрафных функций в сочетании с методом безусловной минимизации. Построение линий ограничений.
курсовая работа [259,9 K], добавлен 04.05.2011Составление математической модели задачи. Определение всевозможных способов распила 5-метровых бревен на брусья 1,5, 2,4, 3,2 в отношении 1:2:3 так, чтобы минимизировать общую величину отходов. Решение задачи линейного программирования симплекс-методом.
задача [26,1 K], добавлен 27.11.2015Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.
задача [58,6 K], добавлен 16.02.2016Описание метода потенциалов Математическая постановка задачи об оптимальных перевозках. Метод решения задачи об оптимальных перевозках средствами Ms Excel. Постановка параметрической транспортной задачи, ее математическое и компьютерное моделирование.
курсовая работа [802,5 K], добавлен 21.10.2014Сущность графического метода нахождения оптимального значения целевой функции. Особенности и этапы симплексного метода решения задачи линейного программирования, понятие базисных и небазисных переменных, сравнение численных значений результатов.
задача [394,9 K], добавлен 21.08.2010Решение задачи об оптимальном направлении капиталовложений в строительную отрасль и оптимизации поставки грузов. Применение симплекс-метода для оптимальной организации ремонтно-строительных работ. Изучение методов динамического программирования.
контрольная работа [2,2 M], добавлен 08.01.2011Способы построения искусственного базиса задачи. Выражение искусственной целевой функции. Математическая модель задачи в стандартной форме. Получение симплекс-таблиц. Минимизации (сведения к нулю) целевой функции. Формы преобразования в задаче равенства.
задача [86,0 K], добавлен 21.08.2010
