Исследование операций и принятие решения
20
Министерство общего и профессионального образования РФ
Южно-Уральский государственный университет
Кафедра «Системы управления»
Курсовая работа по дисциплине исследование операций
Вариант 4
Группа ПС-
3
17
Выполнил: Гречишникова Л.А.Проверил: Плотникова Н.В.Челябинск 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. Составление системы ограничений bj ,j = имеем 3 ограничения3. Запишем целевую функцию.L= max4. Опираясь на условие задания и на перечисленные выше пункты, запишем математическую модель задачи.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+180x7=-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*x5maxL = 1620+6*x2-14*x3-2*x4-9*x5maxТак как в L коэффициент при x2 больше 0, то переменную x2 будем увеличивать. Определим границу увеличения x2 по уже описанной выше схеме.x6 = 210-x2-3x3-2x4x7 = 80-2x2+8x3+4x5x6 =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*x7L = 1860+10* x3-2*x4+3* x5-3*x7Так как в L коэффициент при x3 больше 0, то переменную x3 будем увеличивать. Определим границу увеличения x3 по уже описанной выше схеме.x6=170-2x4-7x3-2x5+0.5x7x2=40-0.5x7+4x3+2x5x6 =0 x2=0 необходимо поменять местами переменные x3 и x2.Новое решение будет следующим:Свободные: x7, x2, x4, x5 =0Базисные: x1, x6, x3 Видно, что получается отрицательная базисная переменная х3, поэтому очевидно, что x3 увеличивать нельзя. Поработаем с х5.x1=180-2x3-x4-x5x6=170-7x3-2x4-2x5+0.5x7x2=40+4x3+2x5-0.5x7x1 =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.25x75. Симплекс-таблицы. L = 9*x1+6*x2+4*x3+7*x4 L = 0 - (-9*x1-6*x2-4*x3-7*x4)
|
| b | | | | | |
L | 1620 | 9 | -6 | 14 | 2 | |
| 180 | 1 | 0 | 2 | 1 | |
| 210 | 0 | 1 | 3 | 2 | |
| 80 | -4 | 2 | -8 | 0 | |
|
L = 0- (-1620+9x5-6x2+14x3+2x4)
|
| b | | | | | |
L | 1860 | -3 | 3 | -10 | 2 | |
| 180 | 1 | 0 | 2 | 1 | |
| 170 | 2 | | 7 | 2 | |
| 40 | -2 | | -4 | 0 | |
|
|
| 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, где = 1 2 . . . 6 , В = b1 b2 . . . b6 , = 1 2 . . . 6 , А= (=1,6; =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.
|
| 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
|
| 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 | |
|
Итак, улучшаем план перевозок с помощью Цикла1. Для этого перенесем по циклу мнимальное количество груза, стоящее в отрицательной вершине.
|
| 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 для таблицы с изменениями.
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 | |
|
Из таблицы видно, что найденное оптимальное решение верно, так как Дij ?0.
Ответ
|
| 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 | |
| 2 | 7 | -1 | -2 | -3 | max | 2 | -4 | 3 | 2 | 10 | 20 | | | |
|
Решение задачи нелинейного программированияОпределить экстремум целевой функции вида = 1112+2222+1212+11+22при условиях111+122<=>1211+222<=>2 .Решениеѓ(x1,x2)= 1. Нужно определить относительный максимум функции для этого нужно определить стационарную точку . стационарная точка (-0,25;1.25)2. Исследовать найденную стационарную точку на максимум для чего определить вогнутость функции f. -2<0Условия выполняются, следовательно, целевая функция является строго вогнутой в окрестности стационарной точки.3. Составление функции Лагранжа. A БПерепишем систему А.А14. Вводим дополнительные переменные v1,v2,w1,w2 ,превращающие неравенства системы А1 в равенства. A2перепишем систему ББ2 - условия дополняющей нежесткости5. Решить систему А2 с помощью метода искусственных переменных. в 1 и 2-ое уравнение системы А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=0x2=10w1=50 оптимальное решениеu2=13.5v1=58.56. проверим условие дополняющей нежесткостиxi*vi=0ui*wi=0 условия выполняютсяx1=0x2=10- решение исходной задачи квадратичного программированияОтветx1=0x2=10ЛитератураКурс лекций Плотникова Н.В.