Министерство образования и науки Российской Федерации
Южно-Уральский государственный университет
Кафедра системы управления
Курсовая работа
по дисциплине: исследование операций
Вариант 9
_
Челябинск
2004 г.
Содержание
Задание 1 3
Задание 2 6
Задание 3 9
Задание 4 11
Литература 17
Задание 1
Задача 9
Условие:
Из трех видов сырья необходимо составить смесь, в состав которой должно входить не менее a ед. химического вещества А, b ед. – вещества В и c ед. – вещества С. Количество единиц химического вещества, содержащегося в 1 кг. сырья каждого вида, указано в таблице. Там же приведена цена 1 кг. сырья каждого вида. Составить смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость.
| Вещество |
Количество единиц вещества, содержащегося в 1 кг сырья |
| 1 |
2 |
3 |
| А |
d11
|
d12
|
d13
|
| В |
d21
|
d22
|
d23
|
| С |
d31
|
d32
|
d33
|
| Цена 1 кг сырья |
D1
|
D2
|
D3
|
| № вар. |
d11
|
d12
|
d13
|
d21
|
d22
|
d23
|
d31
|
d32
|
d33
|
| 9 |
1 |
1 |
0 |
2 |
0 |
3 |
1 |
2 |
4 |
| D1
|
D2
|
D3
|
а |
b |
c |
| 5 |
6 |
7 |
26 |
30 |
24 |
Решение:
Составим математическую модель задачи.
Обозначим через n1, n2, n3 количество кг сырья 1, 2, 3 соответственно.
Тогда, целевая функция будет
L=D1n1+ D2n2+D3n3 = 5n1+ 6n2+7n3 →min
Система ограничений:
_ EMBED Equation.3 ___
Приведем систему ограничений к виду основной задачи линейного программирования. Введем целевую функцию с противоположным знаком L', и новые переменные n4, n5, n6, которые входят в целевую функцию с нулевыми коэффициентами.
L’=0-(5n1+ 6n2+7n3) →max
_ EMBED Equation.3 ___
Выберем n1, n2, n3 свободными переменными, а n4, n5, n6 – базисными и приведем к стандартному виду для решения с помощью симплекс-таблицы:
L’=0-(5n1+ 6n2+7n3)
_ EMBED Equation.3 ___
Составим симплекс-таблицу.
Это решение не опорное, т.к. свободные члены не положительны.
Выберем в первой строке отрицательный элемент, например на пересечении n1 и n4, тогда разрешающий столбец n1, а разрешающий элемент – n5 (минимальный по отношению свободного члена к элементам разрешающего столбца).
Таблица 1.1
| b |
n1
|
n2
|
n3
|
| L’ |
0 |
5 |
6 |
7 |
| -75 |
2,5
|
0 |
-8 |
| n4
|
-26 |
-1 |
-1 |
0 |
26/1=26 |
| 15 |
-1
|
0 |
1,5 |
| n5
|
-30
|
-2
|
0
|
-3
|
30/2=15min |
| 15 |
-1 |
0 |
1,5 |
| n6
|
-24 |
-1 |
-2 |
-4 |
24/1=24 |
| 15 |
-1
|
0 |
1,5 |
Меняем n1
и n5.
Таблица 1.2
| b |
n5
|
n2
|
n3
|
| L’ |
-75 |
2,5 |
6 |
-0,5 |
| -45 |
5
|
-10 |
25 |
| n4
|
-11 |
-0,5 |
-1 |
1,5 |
11/0,5=22 |
| 9 |
-1
|
2 |
-5 |
| n1
|
15 |
-0,5 |
0 |
1,5 |
| 9 |
-1
|
2 |
-5 |
| n6
|
-9
|
-0,5
|
-2
|
-2,5
|
9/0,5=18min |
| 18 |
-2 |
4 |
5 |
Меняем n5
и n6.
Таблица 1.3
| b |
n6
|
n2
|
n3
|
| L’ |
-120 |
5 |
-4 |
25 |
| -10 |
5
|
5 |
-18 |
| n4
|
-2
|
-1
|
1
|
-4
|
| 2 |
-1 |
-1 |
2,5 |
| n1
|
24 |
-1 |
2 |
-3 |
| 2 |
-1
|
-1 |
3,5 |
| n5
|
18 |
-2 |
4 |
5 |
| 4 |
-2
|
-2 |
7 |
Меняем n4
и n6
.
Таблица 1.4
| b |
n4
|
n2
|
n3
|
| L’ |
-130 |
5 |
1 |
7 |
| n6
|
2 |
-1 |
-1 |
3,5 |
| n1
|
26 |
-1 |
-1 |
0 |
| n5
|
22 |
-2 |
2 |
12 |
Т.к. коэффициенты при всех ni положительны, то это и есть оптимальное решение.
Тогда n4 = n2 = n3 =0, n6 =2, n1 =26, n5 =22, L’= -130, следовательно, L=130.
Необходимо взять 26 кг первого сырья, и тогда получим смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость 130.
Ответ: для получения смеси с минимальными затратами необходимо взять 26 кг только первого сырья.
Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer
Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM.
SeoHammer делает продвижение сайта прозрачным и простым занятием.
Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.
Что умеет делать SeoHammer
— Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок.
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз,
а первые результаты появляются уже в течение первых 7 дней.
Зарегистрироваться и Начать продвижение
Задание 2
Задача 29
Условие:
Решение задачи линейного программирования.
С помощью симплекс–таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции Q=CTx при условии Ax ( (B,
где (( = ( (1 (2 . . . (6 (( , В( = ( b1 b2 . . . b6 (( ,
(( = ( (1 (2 . . . (6(( , А= ((((( ((=1,6; (=1,3).
| № вар. |
С1
|
с2
|
с3
|
с4
|
с5
|
с6
|
b1
|
b2
|
b3
|
| 29 |
0 |
5 |
1 |
–1 |
1 |
0 |
2 |
2 |
10 |
| Знаки ограничений |
a11
|
a12
|
a13
|
a14
|
| 1 |
2 |
3 |
| £ |
£ |
£ |
–1 |
1 |
1 |
0 |
| a15
|
a16
|
a21
|
a22
|
a23
|
a24
|
a25
|
a26
|
| 0 |
0 |
1 |
–2 |
0 |
1 |
0 |
0 |
| a31
|
a32
|
a33
|
a34
|
a35
|
a36
|
Тип экстрем. |
| 2 |
1 |
1 |
1 |
2 |
0 |
max |
Решение:
Составим систему:
_ EMBED Equation.3 ___
Целевая функция Q= 0x1+5x2+x3 –x4+x5 →max
Приведем систему ограничений к виду основной задачи линейного программирования.
_ EMBED Equation.3 ___
Пусть х1, х2 , х3, х4, х5 – свободные переменные, х6, х7, х8 – базисные.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
Q= 0-(-5x2-x3 +x4- x5)
_ EMBED Equation.3 ___
Составим симплекс-таблицу:
Это опорное решение т.к. коэффициенты bj>0. Будем искать оптимальное решение. Т.к. коэффициенты при свободных членах <0 (кроме при x1), то разрешающим может быть любой столбец. Пусть x2, тогда на пересечении x2 и x6 получим разрешающий элемент.
Таблица 2.1
| b |
x1
|
x2
|
x3
|
x4
|
x5
|
| Q |
0 |
0 |
-5 |
-1 |
1 |
-1 |
| 10 |
-5 |
5
|
5 |
0 |
0 |
| x6
|
2
|
-1
|
1
|
1
|
0
|
0
|
2/1=2min |
| 2 |
-1 |
1 |
1 |
0 |
0 |
| x7
|
2 |
1 |
-2 |
0 |
1 |
0 |
| 4 |
-2 |
2
|
2 |
0 |
0 |
| x8
|
10 |
2 |
1 |
1 |
1 |
2 |
10/2=5 |
| -2 |
1 |
-1
|
-2 |
0 |
0 |
Меняем x2
и x6.
Таблица 2.2
| b |
x1
|
x6
|
x3
|
x4
|
x5
|
| Q |
10 |
-5 |
5 |
4 |
1 |
-1 |
| 4 |
1,5 |
-1 |
-1 |
0,5 |
0,5
|
| x2
|
2 |
-1 |
1 |
1 |
0 |
0 |
| 0 |
0 |
0 |
0 |
0 |
0
|
| x7
|
6 |
-1 |
2 |
2 |
1 |
0 |
| 0 |
0 |
0 |
0 |
0 |
0
|
| x8
|
8
|
3
|
-1
|
-1
|
1
|
2
|
| 4 |
6 |
-2 |
-2 |
2 |
0,5 |
Меняем x5
и x8.
Таблица 2.3
| b |
x1
|
x6
|
x3
|
x4
|
x8
|
| Q |
14 |
-3.5 |
4,5 |
3,5 |
1,5 |
0,5 |
| 21 |
5,25
|
-2,625 |
-2,625 |
2,625 |
2,625 |
| x2
|
2 |
-1 |
1 |
1 |
0 |
0 |
| 8/3 |
2/3
|
-1/3 |
-1/3 |
1/3 |
1/3 |
| x7
|
6 |
-1 |
2 |
2 |
1 |
0 |
| 8/3 |
2/3
|
-1/3 |
-1/3 |
1/3 |
1/3 |
| x
5
|
4
|
1,5
|
-0,5
|
-1
|
0,5
|
0,5
|
| 8/3 |
2/3 |
-1/3 |
-1/3 |
1/3 |
1/3 |
Меняем x5
и x1.
Таблица 2.4
| b |
x5
|
x6
|
x3
|
x4
|
x8
|
| Q |
35 |
5,25 |
1,875 |
0,875 |
4,125 |
3,125 |
| x2
|
14/3 |
2/3 |
2/3 |
2/3 |
1/3 |
1/3 |
| x7
|
26/3 |
2/3 |
5/3 |
5/3 |
4/3 |
1/3 |
| x1
|
8/3 |
2/3 |
-1/3 |
-1/3 |
1/3 |
1/3 |
Получили оптимальное решение, т.к. все коэффициенты положительны.
Следовательно Q=35; x5=x6= x3=x4=x8=0; x1=8/3; x2=14/3; x7=26/3.
Ответ: Q=35; x5=x6= x3=x4=x8=0; x1=8/3; x2=14/3; x7=26/3.
Задание 3
Задача 9
Условие:
Решение транспортной задачи:
1. Записать условия задачи в матричной форме.
2. Определить опорный план задачи.
3. Определить оптимальный план задачи.
4. Проверить решение задачи методом потенциалов.
Таблица 1
| №вар. |
а1
|
а2
|
а3
|
b1
|
b2
|
b3
|
b4
|
b5
|
с11
|
с12
|
с13
|
| 9 |
300 |
700 |
1000 |
200 |
100 |
400 |
600 |
200 |
23 |
40 |
10 |
| с14
|
с15
|
с21
|
с22
|
с23
|
с24
|
с25
|
с31
|
с32
|
с33
|
с34
|
с35
|
| 12 |
21 |
25 |
21 |
20 |
50 |
18 |
15 |
30 |
32 |
25 |
50 |
Решение:
Составим таблицу транспортной задачи.
Таблица 2
| B1 |
B2 |
B3 |
B4 |
B5 |
a |
| A1 |
| 23 |
40 |
10 |
12 |
21 |
300 |
| A2 |
| 25 |
21 |
20 |
50 |
18 |
700 |
| A3 |
| 15 |
30 |
32 |
25 |
50 |
1000 |
| b |
200 |
100 |
200 |
600 |
200 |
Заметим, что сумма запасов превышает заявки. Это транспортная задача с избытком запасов. Для того чтобы привести к транспортной задаче с правильным балансом, введем фиктивный пункт назначения В5 с нулевыми перевозками. Добавим недостающее число заявок b5=700. Теперь количество заявок равно количеству запасов и равно 2000.
Заполним таблицу. Для этого не будем использовать метод северо-западного угла, т.к. он принесет много хлопот, будем заполнять клетки слева направо от заявок к запасам, исходя из наименьшей цены.
Таблица 3
| B1 |
B2 |
B3 |
B4 |
B5 |
В6 |
a |
| A1 |
300
|
| 23 |
40 |
10 |
12 |
21 |
0 |
300 |
| A2 |
100
|
200
|
200
|
200
|
| 25 |
21 |
20 |
50 |
18 |
0 |
700 |
| A3 |
200
|
300
|
500
|
| 15 |
30 |
32 |
25 |
50 |
0 |
1000 |
| b |
200 |
100 |
200 |
600 |
200 |
700 |
2000 |
Это будет опорный план.
Количество заполненных ячеек – 6. r=m+n-1=3+6-1=8>6, значит, план является вырожденным, т.к. не хватает 2 базисных клеток. Добавим их, и сделаем план невырожденным. Для этого изменим в некоторых клетках количество запасов и заявок на малую величину _ EMBED Equation.3 ___
Сервис онлайн-записи на собственном Telegram-боте
Попробуйте сервис онлайн-записи VisitTime на основе вашего собственного Telegram-бота:
— Разгрузит мастера, специалиста или компанию;
— Позволит гибко управлять расписанием и загрузкой;
— Разошлет оповещения о новых услугах или акциях;
— Позволит принять оплату на карту/кошелек/счет;
— Позволит записываться на групповые и персональные посещения;
— Поможет получить от клиента отзывы о визите к вам;
— Включает в себя сервис чаевых.
Для новых пользователей первый месяц бесплатно.
Зарегистрироваться в сервисе
Таблица 4
| B1 |
B2 |
B3 |
B4 |
B5 |
В6 |
a |
| A1 |
300
|
300 |
| 23 |
40 |
10 |
12 |
21 |
0 |
| A2 |
|
100
|
200
|
|
200
|
200
|
700 |
| 25 |
21 |
20 |
50 |
18 |
0 |
| A3 |
200
|
300
|
500
|
1000 |
| 15 |
30 |
32 |
25 |
50 |
0 |
| b |
200 |
100 |
200 |
600 |
200 |
700 |
2000 |
Проверим методом потенциалов:
Примем α1=0, тогда βj = cij – αi (для заполненных клеток).
Если решение верное, то во всех пустых клетках таблицы Δij = cij – (αi+ βj) ≥ 0
Очевидно, что Δij =0 для заполненных клеток.
В результате получим следующую таблицу:
Таблица 5
| β1=2 |
β2=8 |
β3=7 |
β4=12 |
β5=6 |
β6=-13 |
a |
| α1=0 |
300
|
300 |
| 23-2>0 |
40-8>0 |
10-7>0 |
12-12=0 |
21-6>0 |
0-(-13)>0 |
| α2=13 |
100
|
200
|
200
|
200
|
700 |
| 25-13-2>0 |
21-8-13=0 |
20-7-13=0 |
50-12-13>0 |
18-6-13=0 |
0-13+13=0 |
| α2=13 |
200
|
300
|
500
|
1000 |
| 15-13-2=0 |
30-13-8>0 |
32-13-7>0 |
25-13-2=0 |
50-13-6>0 |
0-13+13=0 |
| b |
200 |
100 |
200 |
600 |
200 |
700 |
2000 |
Таким образом, решение верное, т.к. Δij > 0 для всех пустых клеток и Δij =0 для всех заполненных.
Тогда сумма всех перевозок:
L=200*15+10*21+200*20+300*12+300*25+200*18+200*0+500*0=23800
Ответ:
| B1 |
B2 |
B3 |
B4 |
B5 |
В6 |
a |
| A1 |
300
|
| 23 |
40 |
10 |
12 |
21 |
0 |
300 |
| A2 |
100
|
200
|
200
|
200
|
| 25 |
21 |
20 |
50 |
18 |
0 |
700 |
| A3 |
200
|
300
|
500
|
| 15 |
30 |
32 |
25 |
50 |
0 |
1000 |
| b |
200 |
100 |
200 |
600 |
200 |
700 |
2000 |
Задание 4
Задача 54
Условие:
Определить экстремум целевой функции вида
( = (11(12+(22(22+(12(1(2+(1(1+(2(2
при условиях:
(11(1+(12(2<=>(1
(21(1+(22(2<=>(2 .
Найти стационарную точку целевой функции и исследовать ее (функцию) на выпуклость (вогнутость) в окрестностях стационарной точки.
Составить функцию Лагранжа.
Получить систему неравенств в соответствии с теоремой Куна-Таккера.
Используя метод искусственных переменных составить симплекс-таблицу и найти решение полученной задачи линейного программирования.
1. Дать ответ с учетом условий дополняющей нежесткости.
2.
| № |
b1
|
b2
|
c11
|
c12
|
c22
|
extr |
a11
|
a12
|
a21
|
a22
|
p1
|
p2
|
Знаки огр.
1 2
|
| 31 |
–7 |
–2 |
4 |
1.5 |
–2 |
min |
–2 |
1.5 |
4 |
–3 |
18 |
9 |
£ |
³ |
Решение:
1) Целевая функция: F=4x12-2x22 +1,5x1x2-7x1-2x2→min
Рассмотрим F’=-4x12+2x22 -1,5x1x2+7x1+2x2→max
Ограничения g1(x) и g2(x): _ EMBED Equation.3 ___ →_ EMBED Equation.3 ___
Определим относительный максимум функции F’, для этого определим стационарную точку (х10, х20):
_ EMBED Equation.3 ___→ _ EMBED Equation.3 ___→ _ EMBED Equation.3 ___
2) Исследуем стационарную точку на максимум, для чего определяем выпуклость или вогнутость функции:
F’11 (х10, х20) = -8 < 0
F’12 (х10, х20) = -1,5
F’21 (х10, х20) = -1,5
F’22 (х10, х20) = 4
_ EMBED Equation.3 ___
Т.к. условие выполняется, то целевая функция является строго выпуклой в окрестности стационарной точки
3) Составляем функцию Лагранжа:
L(x,u)=F’(x)+u1g1(x)+u2g2(x)=
=-4x12+2x22 -1,5x1x2+7x1+2x2+u1(_ EMBED Equation.3 ___)+u2(_ EMBED Equation.3 ___)
Получим уравнения седловой точки, применяя теорему Куна-Таккера:
_ EMBED Equation.3 ___ i=1;2
Объединим неравенства в систему А, а равенства в систему В:
Система А:
_ EMBED Equation.3 ___
Система В:
_ EMBED Equation.3 ___
Перепишем систему А:
_ EMBED Equation.3 ___
4)Введем новые переменные
V={v1,v2}≥0; W={w1,w2}≥0
в систему А для того, чтобы неравенства превратить в равенства:
_ EMBED Equation.3 ___
Тогда
_ EMBED Equation.3 ___.
Значит , система В примет вид:
_ EMBED Equation.3 ___ - это условия дополняющей нежесткости.
5) Решим систему А с помощью метода искусственных переменных.
Введем переменные Y={y1; y2} в 1 и 2 уравнения системы
_ EMBED Equation.3 ___
Затем создадим псевдоцелевую функцию Y=My1+My2→min
Y’=-Y= -My1-My2→max.
Пусть свободные переменные: х1, х2, v1, v2, u1, u2;
а базисные y1, y2, w1, w2.
Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы:
_ EMBED Equation.3 ___
_ EMBED Equation.3 ___
Решим с помощью симплекс-таблицы. Найдем опорное решение:
| b |
x1 |
x2 |
u1 |
u2 |
v1 |
v2 |
| Y'/M |
-9 |
-9,5 |
2,5 |
0,5 |
1 |
1 |
1 |
| 8,3125 |
1,1875
|
1,7813 |
-2,375 |
-4,75 |
-1,188 |
0 |
| y1 |
7
|
8
|
1,5
|
-2
|
-4
|
-1
|
0
|
| 0,875 |
0,125 |
0,1875 |
-0,25 |
-0,5 |
-0,125 |
0 |
| y2 |
2 |
1,5 |
-4 |
1,5 |
3 |
0 |
-1 |
| -1,313 |
-0,188
|
-0,281 |
0,375 |
0,75 |
0,1875 |
0 |
| w1 |
18 |
-2 |
1,5 |
0 |
0 |
0 |
0 |
| 1,75 |
0,25
|
0,375 |
-0,5 |
-1 |
-0,25 |
0 |
| w2 |
9 |
-4 |
3 |
0 |
0 |
0 |
0 |
| 3,5 |
0,5
|
0,75 |
-1 |
-2 |
-0,5 |
0 |
| b |
y1 |
x2 |
u1
|
u2 |
v1 |
v2 |
| Y'/M |
-0,69 |
1,1875 |
4,2813 |
-1,875 |
-3,75 |
-0,188 |
1 |
| 0,6875 |
-0,188 |
-4,281 |
1
|
3,75 |
0,1875 |
-1 |
| x1 |
0,875 |
0,125 |
0,1875 |
-0,25 |
-0,5 |
-0,125 |
0 |
| 0,0917 |
-0,025 |
-0,571 |
0,1333
|
0,025 |
-0,133 |
| y2
|
0,688
|
-0,188
|
-4,281
|
1,875
|
3,75
|
0,1875
|
-1
|
| 0,3667 |
-0,1 |
-2,283 |
0,5333 |
2 |
0,1 |
-0,533 |
| w1 |
19,75 |
0,25 |
1,875 |
-0,5 |
-1 |
-0,25 |
0 |
| 0,1833 |
-0,05 |
-1,142 |
0,2667
|
1 |
0,05 |
-0,267 |
| w2 |
12,5 |
0,5 |
3,75 |
-1 |
-2 |
-0,5 |
0 |
| 0,3667 |
-0,1 |
-2,283 |
0,5333
|
2 |
0,1 |
-0,533 |
| b |
y1 |
x2 |
y2 |
u2 |
v1 |
v2 |
| Y'/M |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
| x1 |
0,967 |
0,1333 |
| u1 |
0,367 |
-0,1 |
-2,283 |
0,5333 |
2 |
0,1 |
-0,533 |
| w1 |
19,93 |
0,2667 |
| w2 |
12,87 |
0,5333 |
Т. о, u2=x2=y1=y2=v1=v2=0; x1=0,967; u1=0,367; w1=19,93; w2=12,87;
б) Условия дополняющей нежесткости выполняются (u2w2=0), значит решения исходной задачи квадратичного программирования существует.
ОТВЕТ: существует.
Литература
Курс лекций Плотникова Н. В.
|
