Контрольная работа на тему Исследование операций и принятие решения
Работа добавлена на сайт bukvasha.net: 2014-07-03Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
от 25%
договор
Министерство общего и профессионального образования РФ
Южно-Уральский государственный университет
Кафедра «Системы управления»
Курсовая работа по дисциплине исследование операций
Вариант 4
Проверил: Плотникова Н.В.
Челябинск 2004
Содержание
ЗАДАНИЕ N1. 3
Условие. 3
Решение. 4
Ответ. 11
ЗАДАНИЕ N2. 12
Условие. 12
Решение. 12
Ответ. 14
ЗАДАНИЕ N3. 15
Условие. 15
Решение. 15
Ответ. 19
ЗАДАНИЕ N4. 20
Условие. 20
Решение. 20
Ответ. 25
Литература. 26
За элементы решения примем xi- количество i-го товара (элементов решений 4) i =
2. Составление системы ограничений
bj ,j = имеем 3 ограничения
3. Запишем целевую функцию.
L= max
4. Опираясь на условие задания и на перечисленные выше пункты, запишем математическую модель задачи.
L = 9*x1+6*x2+4*x3+7*x4 max
Приведем нашу математическую модель к виду ОЗЛП с помощью добавочных неотрицательных переменных, число которых равно числу неравенств. Так как имеем неравенство вида меньше/ равно, тодобавочные переменные вводим в левую часть со знаком “+”. Получаем следующее:
ОЗЛП
L = 9*x1+6*x2+4*x3+7*x4 max
Теперь определимся с существованием решения найденной ОЗЛП. Подсчитаем число уравнений(m) и число переменных(n), найдем их разность(k) и сделаем вывод. Итак, m=3, n=7, k=n-m=4. Так как число линейно независимых уравнений(m) меньше числа переменных(n),то система совместна и у нее существует бесчисленное множество решений. При этом (n-m) переменным мы можем придавать произвольные значения (свободные) и остальные m переменных (базисные) будем выражать через свободные.
Свободные: x1, x2, x3, x4
Базисные: x5, x6, x7
L = 9*x1+6*x2+4*x3+7*x4 max
опорное решение
Так как в L коэффициент при x1 больше 0 и больше всех остальных коэффициентов при переменных, то переменную x1 будем увеличивать. Определим границу увеличения x1 следующим образом: возьмем два уравнения из системы ограничений;
x5 = -x1-2x3-x4+180
x7=-4x1-2x2-4x4+800
Определим значения x1, при которых каждая из переменных x5 , x7 обратится в 0.
x5 =0
x7=0
Увеличивать x1 можно до наименьшего из найденных значений необходимо поменять местами переменные x1 и x5.
Новое решение будет следующим:
Свободные: x2, x3, x4, x5 =0
Базисные: x1, x6, x7
L=9*(180-2*x3-x4-x5)+6*x2+4*x3+7*x4=1620-18*x3-9*x4-9*x5+6*x2+4*x3+7*x4 =1620+6*x2-14*x3-2*x4-9*x5 max
L = 1620+6*x2-14*x3-2*x4-9*x5 max
Так как в L коэффициент при x2 больше 0, то переменную x2 будем увеличивать. Определим границу увеличения x2 по уже описанной выше схеме.
x6 = 210-x2-3x3-2x4
x7 = 80-2x2+8x3+4x5
x6 =0
x7=0
необходимо поменять местами переменные x2 и x7.
Новое решение будет следующим:
Свободные: x7, x3, x4, x5 =0
Базисные: x1, x6, x2
L = 1620+6*(40-0,5*x7+4*x3+2*x5)-14*x3-2*x4-9*x5= 1620+240-3*x7+24* x3+12*x5-14*x3-2*x4-9*x5= 1860+10* x3-2*x4+3* x5-3*x7
L = 1860+10* x3-2*x4+3* x5-3*x7
Так как в L коэффициент при x3 больше 0, то переменную x3 будем увеличивать. Определим границу увеличения x3 по уже описанной выше схеме.
x6=170-2x4-7x3-2x5+0.5x7
x2=40-0.5x7+4x3+2x5
x6 =0
x2=0
необходимо поменять местами переменные x3 и x2.
Новое решение будет следующим:
Свободные: x7, x2, x4, x5 =0
Базисные: x1, x6, x3
Видно, что получается отрицательная базисная переменная х3, поэтому очевидно, что x3 увеличивать нельзя. Поработаем с х5.
x1=180-2x3-x4-x5
x6=170-7x3-2x4-2x5+0.5x7
x2=40+4x3+2x5-0.5x7
x1 =0
x6=0
x2=0
Видим, что необходимо поменять местами х2 и х5
Новое решение будет следующим:
Свободные: x7, x3, x4, x2 =0
Базисные: x1, x6, x5
x6=170-7x3-2x4-2x5+0.5x7 x5= -40+x2-4x3+0.5x7
Видно, что получается отрицательная базисная переменная х5, поэтому очевидно, что x5 и х2 менять нельзя. Поменяем х5 с х6.
L=1860+10x3-2x4+3(85-3.5x3-x4-0.5x6+0.25x7)-3x7=2115-0.5x3-5x4-1.5x6-2.25x7
5. Симплекс-таблицы.
L = 9*x1+6*x2+4*x3+7*x4 L = 0 – (-9*x1-6*x2-4*x3-7*x4)
L = 0- (-1620+9x5-6x2+14x3+2x4)
где CT = [ c1 c2 . . . c6 ]T , ВT = [ b1 b2 . . . b6 ]T ,
XT = [ x1 x2 . . . x6]T , А= [aij] (i=1,6; j=1,3).
L = 5*x1+x2-x3+x4 +2x5 max
L = 0 –(-5*x1-x2+x3-x4 -2x5 ) max
Видим, что x1,x2-свободные переменные и x3,x4,x5 – базисные; n= 5, m=3, k= 2.
Заполним стандартную таблицу
Поясним действия, проделанные выше за пределами таблицы. Выбрав в качестве разрешающего столбца x2. Далее в этом столбце нужно выбрать разрешающий элемент. Для этого рассмотрим все элементы данного столбца, имеющие одинаковый знак со своим свободным членом. Из них в качестве разрешающего выберем тот, для которого отношение к нему свободного члена будет минимально. Отсюда понятно, почему в качестве разрешающей строки мы выбрали x4.
Полученное решение удовлетворяет системе ограничений!
x*4,x*5=0 – свободные
- базисные
и общее количество заявок . Понятно что имеем транспортную задачу с избытком заявок . Потребуем, чтобы все пункты назначения были удовлетворены в равной доле. При таком подходе задача сводится к задаче с правильным балансом: необходимо исправить поданные заявки, умножив каждую на коэффициент
k = å ai / å bj . Рассчитаем k.
Тогда получим транспортную задачу с правильным балансом.
Южно-Уральский государственный университет
Кафедра «Системы управления»
Курсовая работа по дисциплине исследование операций
Вариант 4
Группа ПС-317
Выполнил: Гречишникова Л.А.Проверил: Плотникова Н.В.
Челябинск 2004
Содержание
ЗАДАНИЕ N1. 3
Условие. 3
Решение. 4
Ответ. 11
ЗАДАНИЕ N2. 12
Условие. 12
Решение. 12
Ответ. 14
ЗАДАНИЕ N3. 15
Условие. 15
Решение. 15
Ответ. 19
ЗАДАНИЕ N4. 20
Условие. 20
Решение. 20
Ответ. 25
Литература. 26
ЗАДАНИЕ N1
Условие
На швейной фабрике «Шанель» для изготовления четырех видов изделий может быть использована ткань трех артикулов. Нормы расхода тканей всех артикулов на пошив одного изделия приведены в таблице. Там же указаны имеющееся в распоряжении фабрики общее количество тканей каждого артикула и цена одного изделия данного вида. Определить, сколько изделий каждого вида должна произвести фабрика, чтобы стоимость изготовленной продукции была максимальной. Артикул ткани | Норма расхода ткани (м) на одно изделие вида | Общее коли- чество ткани | |||
1 | 2 | 3 | 4 | ||
I | а11 | а12 | а13 | а14 | b1 |
II | а21 | а22 | а23 | а24 | b2 |
III | а31 | а32 | а33 | а34 | b3 |
Цена одного изделия (руб.) | с1 | с2 | с3 | с4 |
№ вар. | а11 | а12 | а13 | а14 | а21 | а22 | а23 | а24 | а31 | а32 | а33 | а34 | b1 | b2 | b3 | с1 | с2 | с3 | с4 |
1 | 1 | 0 | 2 | 1 | 0 | 1 | 3 | 2 | 4 | 2 | 0 | 4 | 180 | 210 | 800 | 9 | 6 | 4 | 7 |
Решение
1. Выберем элементы решения.За элементы решения примем xi- количество i-го товара (элементов решений 4) i =
2. Составление системы ограничений
3. Запишем целевую функцию.
L=
4. Опираясь на условие задания и на перечисленные выше пункты, запишем математическую модель задачи.
L = 9*x1+6*x2+4*x3+7*x4
Приведем нашу математическую модель к виду ОЗЛП с помощью добавочных неотрицательных переменных, число которых равно числу неравенств. Так как имеем неравенство вида меньше/ равно, тодобавочные переменные вводим в левую часть со знаком “+”. Получаем следующее:
ОЗЛП
L = 9*x1+6*x2+4*x3+7*x4
Теперь определимся с существованием решения найденной ОЗЛП. Подсчитаем число уравнений(m) и число переменных(n), найдем их разность(k) и сделаем вывод. Итак, m=3, n=7, k=n-m=4. Так как число линейно независимых уравнений(m) меньше числа переменных(n),то система совместна и у нее существует бесчисленное множество решений. При этом (n-m) переменным мы можем придавать произвольные значения (свободные) и остальные m переменных (базисные) будем выражать через свободные.
Свободные: x1, x2, x3, x4
Базисные: x5, x6, x7
L = 9*x1+6*x2+4*x3+7*x4
Так как в L коэффициент при x1 больше 0 и больше всех остальных коэффициентов при переменных, то переменную x1 будем увеличивать. Определим границу увеличения x1 следующим образом: возьмем два уравнения из системы ограничений;
x7=-4x1-2x2-4x4+800
Определим значения x1, при которых каждая из переменных
x5 =0
x7=0
Новое решение будет следующим:
Свободные: x2, x3, x4, x5 =0
Базисные: x1, x6, x7
L=9*(180-2*x3-x4-x5)+6*x2+4*x3+7*x4=1620-18*x3-9*x4-9*x5+6*x2+4*x3+7*x4 =1620+6*x2-14*x3-2*x4-9*x5
L = 1620+6*x2-14*x3-2*x4-9*x5
Так как в L коэффициент при x2 больше 0, то переменную x2 будем увеличивать. Определим границу увеличения x2 по уже описанной выше схеме.
x6 = 210-x2-3x3-2x4
x7 = 80-2x2+8x3+4x5
x6 =0
x7=0
Новое решение будет следующим:
Свободные: x7, x3, x4, x5 =0
Базисные: x1, x6, x2
L = 1620+6*(40-0,5*x7+4*x3+2*x5)-14*x3-2*x4-9*x5= 1620+240-3*x7+24* x3+12*x5-14*x3-2*x4-9*x5= 1860+10* x3-2*x4+3* x5-3*x7
L = 1860+10* x3-2*x4+3* x5-3*x7
Так как в L коэффициент при x3 больше 0, то переменную x3 будем увеличивать. Определим границу увеличения x3 по уже описанной выше схеме.
x6=170-2x4-7x3-2x5+0.5x7
x2=40-0.5x7+4x3+2x5
x6 =0
x2=0
Новое решение будет следующим:
Свободные: x7, x2, x4, x5 =0
Базисные: x1, x6, x3
Видно, что получается отрицательная базисная переменная х3, поэтому очевидно, что x3 увеличивать нельзя. Поработаем с х5.
x1=180-2x3-x4-x5
x6=170-7x3-2x4-2x5+0.5x7
x2=40+4x3+2x5-0.5x7
x1 =0
x6=0
x2=0
Видим, что необходимо поменять местами х2 и х5
Новое решение будет следующим:
Свободные: x7, x3, x4, x2 =0
Базисные: x1, x6, x5
x6=170-7x3-2x4-2x5+0.5x7
Видно, что получается отрицательная базисная переменная х5, поэтому очевидно, что x5 и х2 менять нельзя. Поменяем х5 с х6.
L=1860+10x3-2x4+3(85-3.5x3-x4-0.5x6+0.25x7)-3x7=2115-0.5x3-5x4-1.5x6-2.25x7
5. Симплекс-таблицы.
L = 9*x1+6*x2+4*x3+7*x4 L = 0 – (-9*x1-6*x2-4*x3-7*x4)
b | | | | | |
L | | | | | |
| | | | | |
| | | | | |
| | | | | |
b | | | | | |
L | 1620 | 9 | -6 | 14 | |
| 180 | 1 | 0 | 2 | 1 |
| 210 | 0 | 1 | 3 | 2 |
| 80 | -4 | 2 | -8 | 0 |
b | | | | | |
L | | | | | |
| | | | | |
| | | | | |
| | | | | |
b | | | | | |
L | 1860 | -3 | 3 | -10 | 2 |
| 180 | 1 | 0 | 2 | 1 |
| 170 | 2 | | 7 | 2 |
| 40 | -2 | | -4 | 0 |
b | | | | | |
L | | | | | |
| | | | | |
| | | | | |
| | | | | |
b | | | | | |
L | 2115 | 1.5 | 2.25 | 0.5 | 5 |
| 95 | -0.5 | 0.25 | -1.5 | 0 |
| 85 | 0.5 | -0.25 | 3.5 | 1 |
| 210 | 1 | 1 | 3 | 2 |
Ответ
Если фабрика произведет 95 штук первого изделия, 210 штук второго изделия, то стоимость произведенной продукции будет максимальной и будет равна 2115 единиц.ЗАДАНИЕ N2
Условие
Решить симплекс-методом задачу линейного программирования. С помощью симплекс–таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции Q=CTx при условии Ax ³ £B,где CT = [ c1 c2 . . . c6 ]T , ВT = [ b1 b2 . . . b6 ]T ,
XT = [ x1 x2 . . . x6]T , А= [aij] (i=1,6; j=1,3).
L = 5*x1+x2-x3+x4 +2x5
Решение
Приведем данное нам условие к стандартной форме записи и получим следующееL = 0 –(-5*x1-x2+x3-x4 -2x5 )
Видим, что x1,x2-свободные переменные и x3,x4,x5 – базисные; n= 5, m=3, k= 2.
Заполним стандартную таблицу
b | | | ||
L | | | | |
| | | | |
| | | | |
| | | | |
b | | | |
L | | | |
| | | |
| | | |
| | | |
b | | | |
L | | | |
| | | |
| | | |
| | | |
b | | | |
L | | | |
| | | |
| | | |
| | | |
b | | | |
L | 8 | 4.5 | 1 |
| 2 | 0.5 | 1 |
| 2/3 | 1/6 | -1/3 |
| 4/3 | 5/6 | 1/3 |
Ответ
L* = 8x*4,x*5=0 – свободные
ЗАДАНИЕ N3
Условие
Решение транспортной задачи, все данные приведены ниже в таблице. B1 | B2 | B3 | B4 | B5 | ai | |
A1 | 0.09 | 0.12 | 0.14 | 0.1 | 0.09 | 3000 |
A2 | 0.08 | 0.1 | 0.15 | 0.05 | 0.07 | 6000 |
A3 | 0.1 | 0.15 | 0.15 | 0.08 | 0.06 | 8000 |
bj | 1000 | 8000 | 3000 | 3000 | 4000 |
Решение
Перед тем как приступить к решению, подсчитаем общее количество запасовk = å ai / å bj . Рассчитаем k.
Тогда получим транспортную задачу с правильным балансом.
B1 | B2 | B3 | B4 | B5 | ai | |
A1 | 0.09 | 0.12 | 0.14 | 0.1 | 0.09 | 3000 |
A2 | 0.08 | 0.1 | 0.15 | 0.05 | 0.07 | 6000 |
A3 | 0.1 | 0.15 | 0.15 | 0.08 | 0.06 | 8000 |
bj | | | | | | 17000 |
Найдем опорное решение с помощью метода северо-западного угла.
r = 3+5-1 =7
Проверим сумму по столбцам, сумму по строкам и количество базисных (заполненных) клеток.
Проверка по столбцам:
Проверка по строкам:
Количество заполненных клеток равно r =7. Найденный план является опорным.
Постараемся улучшить план перевозок
Подсчитаем цены выделенных пунктирными прямоугольниками циклов.
Цикл1
(1;1)-(1;2)-(2;2)-(2;1)
, где цена цикла
Цикл2
(2;3)-(2;4)-(3;4)-(3;3)
Для того чтобы стоимость плана уменьшилась, имеет смысл совершать перевозки только по тем циклам, цена которых отрицательна. Цена Цикла2 отрицательна, поэтому выбираем его. Цикл1 в данном случае рассматривать не будем: так как цена его положительна, поэтому план перевозок с помощью перерасчета этого цикла не улучшится.
После всех рассуждений получим следующее:
Итак, улучшаем план перевозок с помощью Цикла1. Для этого перенесем по циклу мнимальное количество груза, стоящее в отрицательной вершине.
Подсчитаем L для таблицы с изменениями.
L =
Допустим, что найдено оптимальное решение. Проверим его с помощью метода потенциалов.
Примем a1 = 0, тогда bj = cij – ai (для заполненных клеток). Если найденное решение справедливо, то во всех пустых клетках таблицы Δij = cij – (ai + bj )≥0. Ясно, что Δij = 0 для заполненных клеток. Получим следующее.
Из таблицы видно, что найденное оптимальное решение верно, так как Δij ≥0.
Решение задачи нелинейного программирования
Определить экстремум целевой функции вида
F = c11x12+c22x22+c12x1x2+b1x1+b2x2
при условиях
a11x1+a12x2<=>p1
a21x1+a22x2<=>p2 .
1. Нужно определить относительный максимум функции для этого нужно определить стационарную точку .
стационарная точка (-0,25;1.25)
2. Исследовать найденную стационарную точку на максимум для чего определить вогнутость функции f.
-2<0
Условия выполняются, следовательно, целевая функция является строго вогнутой в окрестности стационарной точки.
3. Составление функции Лагранжа.
A Б
Перепишем систему А.
А1
4. Вводим дополнительные переменные v1,v2,w1,w2 ,превращающие неравенства системы А1 в равенства.
A2
перепишем систему Б
Б2 - условия дополняющей нежесткости
5. Решить систему А2 с помощью метода искусственных переменных.
в 1 и 2-ое уравнение системы А2.
Вводим псевдоцелевую функцию
базисные переменные: y1,y2,w1,w2
свободные переменные:x1,x2,v1,v2,u1,u2
Оптимальное решение:
y1=x1=u1=y2=w1=v2=0
x2=10
w1=50 оптимальное решение
u2=13.5
v1=58.5
6. проверим условие дополняющей нежесткости
xi*vi=0
ui*wi=0 условия выполняются
x1=0
x2=10- решение исходной задачи квадратичного программирования
x2=10
r = 3+5-1 =7
B1 | B2 | B3 | B4 | B5 | ai | |
A1 | | | 0.14 | 0.1 | 0.09 | 3000 |
A2 | 0.08 | | | 0.05 | 0.07 | 6000 |
A3 | 0.1 | 0.15 | | | | 8000 |
bj | | | | | | 17000 |
Проверка по столбцам:
Проверка по строкам:
Количество заполненных клеток равно r =7. Найденный план является опорным.
Постараемся улучшить план перевозок
B1 | B2 | B3 | B4 | B5 | ai | |
A1 | | | 0.14 | 0.1 | 0.09 | 3000 |
A2 | 0.08 | | | 0.05 | 0.07 | 6000 |
A3 | 0.1 | 0.15 | | | | 8000 |
bj | | | | | | 17000 |
Цикл1
(1;1)-(1;2)-(2;2)-(2;1)
Цикл2
(2;3)-(2;4)-(3;4)-(3;3)
Для того чтобы стоимость плана уменьшилась, имеет смысл совершать перевозки только по тем циклам, цена которых отрицательна. Цена Цикла2 отрицательна, поэтому выбираем его. Цикл1 в данном случае рассматривать не будем: так как цена его положительна, поэтому план перевозок с помощью перерасчета этого цикла не улучшится.
После всех рассуждений получим следующее:
B1 | B2 | B3 | B4 | B5 | ai | |
A1 | | | 0.14 | 0.1 | 0.09 | 3000 |
A2 | 0.08 | | | 0.05 | 0.07 | 6000 |
A3 | 0.1 | 0.15 | | | | 8000 |
bj | | | | | | 17000 |
B1 | B2 | B3 | B4 | B5 | ai | |
A1 | | | 0.14 | 0.1 | 0.09 | 3000 |
A2 | 0.08 | | | | 0.07 | 6000 |
A3 | 0.1 | 0.15 | | | | 8000 |
bj | | | | | | 17000 |
L =
Допустим, что найдено оптимальное решение. Проверим его с помощью метода потенциалов.
Примем a1 = 0, тогда bj = cij – ai (для заполненных клеток). Если найденное решение справедливо, то во всех пустых клетках таблицы Δij = cij – (ai + bj )≥0. Ясно, что Δij = 0 для заполненных клеток. Получим следующее.
b1=0.09 | b2=0.12 | b3=0.14 | b4=0.07 | b5=0.05 | ai | |
a1=0 | | | | | | 3000 |
a2=-0.02 | | | | | | 6000 |
a3=0.01 | | | | | | 8000 |
bj | | | | | | 17000 |
Ответ
B1 | B2 | B3 | B4 | B5 | ai | |
A1 | | | 0.14 | 0.1 | 0.09 | 3000 |
A2 | 0.08 | | | | 0.07 | 6000 |
A3 | 0.1 | 0.15 | | | | 8000 |
bj | | | | | | 17000 |
ЗАДАНИЕ N4
Условие
№ | b1 | b2 | c11 | c12 | c22 | extr | a11 | a12 | a21 | a22 | p1 | p2 | Знаки огр. 1 2 | |
31 | 2 | 7 | –1 | –2 | –3 | max | 2 | –4 | 3 | 2 | 10 | 20 | £ | £ |
Определить экстремум целевой функции вида
F = c11x12+c22x22+c12x1x2+b1x1+b2x2
при условиях
a11x1+a12x2<=>p1
a21x1+a22x2<=>p2 .
Решение
ѓ(x1,x2)=1. Нужно определить относительный максимум функции для этого нужно определить стационарную точку
стационарная точка (-0,25;1.25)
2. Исследовать найденную стационарную точку на максимум для чего определить вогнутость функции f.
-2<0
Условия выполняются, следовательно, целевая функция является строго вогнутой в окрестности стационарной точки.
3. Составление функции Лагранжа.
A
Перепишем систему А.
4. Вводим дополнительные переменные v1,v2,w1,w2 ,превращающие неравенства системы А1 в равенства.
A2
Б2
5. Решить систему А2 с помощью метода искусственных переменных.
Вводим псевдоцелевую функцию
базисные переменные: y1,y2,w1,w2
свободные переменные:x1,x2,v1,v2,u1,u2
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| | | | | | | |
| 80M | M | 4M | 0 | M | 4M | 0 |
| 10 | 0 | 1.5 | 0 | 0 | 0.5 | 0 |
| 13.5 | 0 | -1.5 | -2 | 0.5 | 0.5 | -0.5 |
| 50 | 0 | 8 | 0 | 0 | 2 | 0 |
| 58.5 | -1 | 5.5 | 4 | 1.5 | -0.5 | 1.5 |
y1=x1=u1=y2=w1=v2=0
x2=10
w1=50 оптимальное решение
u2=13.5
v1=58.5
6. проверим условие дополняющей нежесткости
xi*vi=0
ui*wi=0 условия выполняются
x1=0
x2=10- решение исходной задачи квадратичного программирования
Ответ
x1=0x2=10