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. Выберем элементы решения.

За элементы решения примем 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*x5max

L = 1620+6*x2-14*x3-2*x4-9*x5max

Так как в 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)

Ответ

Если фабрика произведет 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.

Полученное решение удовлетворяет системе ограничений!

Ответ

L* = 8

x*4,x*5=0 - свободные

- базисные

ЗАДАНИЕ N3

Условие

Решение транспортной задачи, все данные приведены ниже в таблице.

Решение

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

k = ai bj . Рассчитаем k.

Тогда получим транспортную задачу с правильным балансом.

Найдем опорное решение с помощью метода северо-западного угла.

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.

Ответ

ЗАДАНИЕ N4

Условие

Решение задачи нелинейного программирования

Определить экстремум целевой функции вида

= 1112+2222+1212+11+22

при условиях

111+122<=>1

211+222<=>2 .

Решение

ѓ(x1,x2)=

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- решение исходной задачи квадратичного программирования

Ответ

x1=0

x2=10

Литература

Курс лекций Плотникова Н.В.