Анализ модели на чувствительность

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И  НАУКИ РФ

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

высшего профессионального образования

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

ИНСТИТУТ  ГЕОЛОГИИ И НЕФТЕГАЗОДОБЫЧИ 

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

Курсовая  работа

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

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

Вариант № 29 
 
 
 
 
 
 
 
 

Выполнил:

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

                        АСОиУзс-09-3

                        Хафизов А.Х.

                        Проверила:

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

Тюмень, 2012

Содержание 
 

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

 

2. Построение  математической модели……………………………………………………..3

 

3. Выбор, обоснование  и описание метода решения рассматриваемой задачи…………..4

 

4. Решение сформулированной задачи…………………………………………………...…6

 

5. Анализ  модели на чувствительность……………………………………………………..7

 

6. Список  литературы………………………………………………………………………...8

 

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

    На  производство поступила  партия стержней длиной 250 и 190 см, причем количество стержней длиной 250 см ограничено и равно 200 шт. Из этих стержней необходимо получить 470 заготовок длиной 120 см и 450 заготовок длиной 80 см. Как следует разрезать стержни, чтобы количество отходов было минимальным? 

 

2. Построение математической модели

Словесная формулировка проблемы

    Требуется определить как лучше разрезать  стержни чтобы минимизировать остатки.

Математическая  формулировка

Длина стержня	Кол-во стержней	Заготовка длинной 120 см	Заготовка длинной 80 см	Величина отходов, см
250	Х11	2	0	10
	Х12	1	1	50
	Х13	0	3	10
190	Х21	1	0	70
	Х22	0	2	30

 

Из полученного  видно что рациональных способов разреза с минимальным остатком для стержней длиной 250 см два вида (х11 и х13 способы), а для длинны 190 см только один х22 способ. 

Решение. Пусть xij – кол-во стержней i-типа, разрезанных по j-способу, тогда

    Х11+х12+х13 ≤ 200

    2х11+х12+х2 1≥ 470

    Х12+3х13+2х22 ≥ 450 (1)

Требование целостности 

xij-целые 

Требование неотрицательности  переменных:

 (2) 

Целевая функция  – минимизация остатков:

f(х)=10x11+50x12+10x13+70x21+30x22 →min. (3) 

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

Определить  как лучше разрезать стержни  чтобы минимизировать остатки, т.е. переменные x_ij, при которых достигается min f(x) =10x11+50x12+10x13+70x21+30x22 (целевая функция) и которые удовлетворяют условиям:

     Х11+х12+х13 ≤ 200

    2х11+х12+х2 1≥ 470

    Х12+3х13+2х22 ≥ 450

   

 

   3. Выбор и обоснование  метода решений  поставленной задачи

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

Расширенная задача имеет опорный план определяемый системой единичных векторов P_n+1, P_n+2, …, P_n+m, образующих базис m-мерного пространства, который называется искусственным. Сами векторы, так же как и переменные x_n+i (i=1,m), называются искусственными. Так как расширенная задача имеет опорный план, то ее решение может быть найдено симплексным методом.

Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным конусом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

Последовательность  вычислений симплекс-методом можно  разделить на две основные фазы:

1. нахождение исходной вершины множества допустимых решений,
2. последовательный переход от одной вершины к другой, ведущий к оптимизации значения целевой функции.

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

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

     Сначала все знаки неравенства поменяем на «£» для того, чтобы при переходе к равенству получить переменные, которые будут входить в список базисных переменных, таким образом, получаем систему следующего вида:

     Х11+х12+х13 ≤ 200

    -2х11-х12-х2 1≤ -470

    -Х12-3х13-2х22 ≤ -450

     
 

Преобразуем ограничения:

     Х11+х12+х13-у1 = 200

    2х11+х12+х21-у2= 470

    Х12+3х13+2х22 –у3= 450

     
 

Найдем ИОР  с помощью М-метода:

     Х11+х12+х13-у1 = 200

    2х11+х12+х21-у2+z1= 470

    Х12+3х13+2х22 –у3+z2= 450

     

Наложим штраф  F=f(x)+M(z1+z2) 

F = 10x11+50x12+10x13+70x21+30x22+М((470-2х11-х12-х21+у2) +( 450-Х12-3х13-2х22 +у3)) 

  Раскроем  скобки и приведем подобные 

F=10x11+50x12+10x13+70x21+30x22+M(920-2х11-3x13-2x22-x21-2x12+y2+y3)= 10x11+50x12+10x13+70x21+30x22+920M-2МХ11-3MX13-2MX22-MX21-2M12+MY2+MY3=8МX11+920M+M(Y2+Y3)+X12(50-2M)+X13(10-3M)+X21(70-M)+X22(30-2M) 

F- M(Y2+Y3)-8МX11-X12(50-2M)-X13(10-3M)-X21(70-M)-X22(30-2M) = 920M 
 
 
 
 
 
 
 
 
 
 
 
 
 

4. Решение сформулированной задачи

    F- M(Y2+Y3)-8МX11-X12(50-2M)-X13(10-3M)-X21(70-M)-X22(30-2M) = 920M

    Запишем полученные данные в симплекс-таблицу. Процесс нахождения оптимального решения приведен в таблице 1.

    Для того чтобы программа восприняла итерации представим М = 1000

    Таблица 1

Базисные  переменные Свободные члены х11 х12 х13 х21 х22 у1 у2 у3 у1 200 1 1 1 0 0 1 0 0 z1 470 2 1 0 1 0 0 -1 0 z2 450 1 0 3 0 2 0 0 -1 F 920000 -8000 1950 2990 930 1970 0 -1000 -1000 1 итерация y1 50 1 1 0 0 -1 1 0 0 z1 470 2 1 0 1 0 0 -1 0 x13 150 1/3 0 1 0 2/3 0 0 - 1/3 F 471500 -8997 1950 0 930 -23 0 -1000 -3 2 итерация x12 50 1 1 0 0 -1 1 0 0 z1 420 1 0.0 0.0 1.0 0.7 -1.0 -1.0 -0.3 x13 150 1/3 0.0 1.0 0.0 0.7 0.0 0.0 -0.3 F 374000 -10297 0.0 0.0 930.0 1276.7 -1950.0 -1000.0 -653.3 3 итерация x12 200 40239 0.7 1.0 0.0 0.0 1.0 0.0 0.0 z1 270 -40237 0.0 -1.0 1.0 0.0 -1.0 -1.0 0.0 x22 225 60357 0.0 1.5 0.0 1.0 0.0 0.0 -0.5 F 86750 -77066067 0.0 -1915.0 930.0 0.0 -1950.0 -1000.0 -15.0 4 итерация x12 200 40239 0.7 1.0 0.0 0.0 1.0 0.0 0.0 x21 270 -40237 0.0 -1.0 1.0 0.0 -1.0 -1.0 0.0 x22 225 60357 0.0 1.5 0.0 1.0 0.0 0.0 -0.5 F -164350 -39645967 0.0 -985.0 0.0 0.0 -1020.0 -70.0 -15.0

 

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

    Х12=200,х21=270, х22=225, а f(x)=164350

 

    5. Анализ модели  на чувствительность

    Проведем  анализ полученного решения. Результирующая симплекс-таблица «насыщена» весьма важными данными, лишь небольшую часть которых составляют оптимальные значения переменных. Из симплекс-таблицы непосредственно, либо при помощи простых дополнительных вычислений можно получить информацию относительно

• оптимального решения,
• статуса ресурсов,
• ценности каждого ресурса,
• чувствительности оптимального решения к изменению запасов ресурсов, вариациям коэффициентов целевой функции.

 

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

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

Управляемые переменные	Оптимальное значение	Решение
Х12	200	Кол-во стержней длинной 250 см разрезанных по 2 способу
х21	270	Кол-во стержней длинной 190 см разрезанных по 1 способу
х22	225	Кол-во стержней длинной 190 см разрезанных по 2 способу
f(x)	164350	Минимальное кол-во остатков от разрезания стержней в общем кол-ве 820 шт.

 

    Статус  ресурсов

    Все ресурсы могут быть разделены  на дефицитные и недефицитные в зависимости  от того, полное или частичное их использование предусматривает  оптимальное решение задачи. В модели рассматриваемой задачи фигурирует одно ограничение со знаком  ≤. (кол-во стержней длинной 250 см равное 200 шт.)

    Применительно к рассматриваемой задаче можно  привести следующую сводку результатов.

Ресурс	Остаточная  переменная	Статус ресурса
Стержни длинной 250 см	Y1 = 0	Дефицитный

 

    Так как остаточная переменная равна  нулю, то это свидетельствует о  полном потреблении соответствующего ресурса. 
 

 

Список  литературы 

1. Методическое  пособие. Гапанович И.В.
2. Лекции. Гапанович И.В.
3. www.Wikipedia.ru