|
|
|
 |
Исследование операций и принятие решения |
|
 |
БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Исследование операций и принятие решения
Исследование операций и принятие решения
20 Министерство общего и профессионального образования РФ Южно-Уральский государственный университет Кафедра «Системы управления» Курсовая работа по дисциплине исследование операций Вариант 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. Составление системы ограничений 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 ЛитератураКурс лекций Плотникова Н.В.
|
|
 |
НОВОСТИ |
 |
|
| Изменения |
|
| Прошла модернизация движка, изменение дизайна и переезд на новый более качественный сервер |
|
