(5 оценок, среднее: 4,80 из 5)
Загрузка...
Учебная работа. Контрольная работа: Исследование операций
Нормоконтроллёр:
Плотникова Н. В. _______
«____» ___________ 2005 г.
Управляющий:
Плотникова Н. В. _______
«____» ___________ 2005 г.
Создатель:
Студент группы ПС-346
Нечаев Л. В. ___________
«____» ___________ 2005 г.
Работа защищена
с оценкой______________
«____» ___________ 2005 г.
Оглавление
задачка 1…………………………………………………………………………………………………………………………… 3
Условие……………………………………………………………………………………………………………………….. 3
Решение……………………………………………………………………………………………………………………… 3
Ответ: ………………………………………………………………………………………………………………………….. 5
Задачка 2…………………………………………………………………………………………………………………………… 6
Условие……………………………………………………………………………………………………………………….. 6
Решение……………………………………………………………………………………………………………………… 6
Ответ:…………………………………………………………………………………………………………………………… 8
Примечание:……………………………………………………………………………………………………………….. 8
задачка 3…………………………………………………………………………………………………………………………. 10
Условие……………………………………………………………………………………………………………………… 10
Решение……………………………………………………………………………………………………………………. 10
Ответ:…………………………………………………………………………………………………………………………. 14
Задачка 4…………………………………………………………………………………………………………………………. 15
Условие……………………………………………………………………………………………………………………… 15
Решение……………………………………………………………………………………………………………………. 15
Ответ:…………………………………………………………………………………………………………………………. 19
приложение 1……………………………………………………………………………………………………………….. 20
Перечень использованной литературы………………………………………………………………………….. 22
Задачка 1
Условие
Оператор связи оказывает 2 вида услуг:
1. Предоставление одной полосы телефонной сети общего использования (ТСОП) и трёх линий цифровой связи (ЦС);
2. Предоставление одной полосы ЦС и 2-ух линий ТСОП.
Стоимость услуг указана в табл. 1:
Таблица 1
ТСОП
ЦС
Стоимость
услуга 1
1
3
750
Услуга 2
2
1
600
Сети связи и эксплуатируемое оборудование накладывает последующие ограничения на количество применяемых линий связи:
ТСОП ≤ 300
ЦС ≤ 120
ТСОП+2*ЦС ≤ 380
Найти среднее соотношение услуг 1 и 2, которые оператор должен предоставлять для получения наибольшей выручки.
Решение
1. Обозначим за x1 количество оказанных услуг с номером `1′, а x2 – количество оказанных услуг с номером `2′.
2. Учтём ограничения задачки: 
.
3. Составим мотивированную функцию, которую необходимо максимизировать: 
4. задачка сведена к последующей задачке линейного программирования: «Отыскать значения аргументов x1 и x2, при которых функция 
воспринимает наибольшее . Очевидно, x1≥0, x2≥0.
5. Решим выше представленную задачку графическим способом, потому что в задачке находятся лишь 2 переменные x1 и x2. Для этого:
Изобразим многоугольник решений в плоскости x2Ox1:
График представлен на рис. 1.
Сначала максимизации наибольшее задаёт направление возрастания мотивированной функции.
Среднее решение находится в точке (0; 95), находящейся на
пересечении прямых 
. Как следует, наибольшее , достигается при x1 = 0, x2 = 95.
Итак, для получения большей прибыли (57000 ед.) оператор связи должен не предоставлять услуг 1, а услуг 2 предоставить в количестве 95 штук.
Ответ:
– Не предоставлять yслуг #1
– Yслуг #2 предоставить в количестве 95 штук.
задачка 2
Условие
Решение задачки линейного программирования.
При помощи симплекс–таблиц отыскать решение задачки линейного программирования: найти экстремальное
где CT = [ c1 c2 . . . c6 ]T , ВT = [ b1 b2 . . . b6 ]T , XT = [ x1 x2 . . . x6]T , А= [aij] (i=1,6; j=1,3).
Таблица 2
c1
c2
c3
c4
c5
c6
b1
b2
b3
Знаки ограничений
1
2
3
4
-1
12
2
-1
0
2
13
16
=
=
=
a11
a12
a13
a14
a15
a16
a21
a22
a23
a24
a25
a26
a31
a32
a33
a34
a35
a36
Ext
-1
1
1
0
0
0
4
3
2
1
1
0
3
2
0
0
1
0
max
Решение
Составляем систему:
Мотивированная функция имеет вид 
Приведем систему ограничений к виду главный задачки линейного программирования:
Пусть х1, х2 – вольные переменные, х3, х4, х5 – базовые.
Приведем систему и мотивированную функцию к обычному виду, для построения симплекс-таблицы:
Составляем симплекс-таблицу.
Это решение является допустимым, но не опорным, т.к. находится отрицательный вольный член во 2-ой строке. Ликвидируем его путём подмены базовых переменных на главные. В строке x4 находится отрицательный элемент a42=-2, как следует, столбец x2 – разрешающий. Меньшее отношение меж вольным членом и эл-том разрешающего столбца (см. поле «оценка») будет в первой строке и элемент a32 – разрешающий. Вышла таблица 3 (верхние числа).
Таблица 3
Базис
Вольный член
Переменные
Оценка
x1
x2
x3
2
2
-1
-1
1
1
2
x4
-7
4
3
-2
-2
2
—
x5
16
-4
3
2
2
-2
8
F
6
18
13
-9
-9
9
—
сейчас преобразуем таблицу по последующему методу:
1. Выделим разрешающий элемент aij;
2. Найдём оборотную ему величину λ=1/aij и запишем её в правом нижнем углу данной нам же ячейки;
3. Все элементы разрешающей строчки, не считая разрешающего элемента, умножим на λ и запишем понизу соответственной ячейки;
4. Все элементы разрешающего столбца , не считая разрешающего элемента, умножим на -λ и запишем понизу соответственной ячейки;
5. Выделим все верхние числа в разрешающей строке, и все нижние — в разрешающем столбце;
6. Для всякого из других частей запишем в нижнюю часть ячейки произведение выделенных чисел, стоящих в той же строке и в том же столбце, что и данный элемент;
7. Перепишем таблицу, заменив переменные: элементы разрешающих строчки и столбца – значениями, стоящими в нижних частях этих ячеек; оставшиеся элементы – суммой чисел, стоящих в верхних и нижних частях ячеек.
Применительно к текущему шагу, разрешающий элемент a32, λ = 1 / a32 = 1. Опосля обозначенных выше преобразований, получим новейшую таблицу (табл. 4):
Таблица 4
Базис
Вольный член
Переменные
x1
x3
x2
2
-1
1
x4
-3
1
2
x5
12
5
-2
F
24
4
9
Решение опять не быть может опорным, т.к. находится отрицательный вольный член во 2-ой строке. Попытаемся устранить его путём подмены базовых переменных на главные. Но в строке x4 больше нет отрицательных частей, как следует, нереально избрать разрешающий столбец. Заметим, что в строке мотивированной функции нет отрицательных частей, означает среднее решение, в случае отмены ограничений на переменные, достигнуто. Ограничивающая система уравнений не имеет решений при неотрицательных значениях всех переменных.
Ответ:
Система уравнений несовместима в области положительных значений переменных.
Примечание:
Тот же итог получен и при решении данной задачки в пакете Mathematica:
Задачка 3
Условие
Решение транспортной задачки:
1. Записать условия задачки в матричной форме.
2. Найти опорный план задачки.
3. Найти лучший план задачки.
4. Проверить решение задачки способом потенциалов.
Таблица 5
B1
B2
B3
ai
A1
10
20
32
700
A2
12
50
25
600
A3
21
18
50
200
A4
25
15
23
200
A5
21
30
40
100
bj
300
700
1000
Решение
Заметим, что общее количество припасов (700+600+200+200+100=1800) меньше количества заявок (300+700+1000=2000), как следует имеем открытую транспортную задачку с излишком заявок. Добавим строчку с фиктивными припасами для дополнения задачки до задачки закрытого типа. Опосля корректировки получаем транспортную задачку с правильным балансом (табл. 6):
Таблица 6
B1
B2
B3
ai
A1
10
20
32
700
A2
12
50
25
600
A3
21
18
50
200
A4
25
15
23
200
A5
21
30
40
100
A6
0
0
0
200
bj
300
700
1000
2000
Найдём опорное решение способом меньших издержек (табл. 7):
Таблица 7
B1
B2
B3
ai
A1
10
300
20
400
32
—
700
-10 (2)
A2
12
—
50
—
25
600
600
-7 (7)
A3
21
—
18
200
50
—
200
-8 (4)
A4
25
—
15
100
23
100
200
-5 (5)
A5
21
—
30
—
40
100
100
-22 (8)
A6
0
—
0
—
0
200
200
18 (9)
Bj
300
700
1000
2000
0 (1)
-10 (3)
-18 (6)
Избранный план перевозок является допустимым, т.к. при нём все заявки удовлетворены и все припасы израсходованы, сумма перевозок по строке равна припасу соответственного пт отправления, а сумма перевозок по столбцу – заявке соответственного пт предназначения. Сумма припасов равна сумме заявок, и выражается числом 2000, стоящим в правом нижнем углу таблицы. Данное распределение является базовым (заполнено m+n-1=8 ячеек таблицы), как следует, задачка готова к решению.
Сначало Издержки на перевозку составят:
Составим матрицу оценок способом потенциалов:
Начнём с первого столбца. Пусть потенциал этого столбца равен нулю. с потенциалом в скобках записываем номер шага. Опосля добавления потенциала к коэффициентам издержек первого столбца коэффициент издержек заполненной клеточки (1;1) не поменяется; чтоб приобретенный опосля сложения коэффициент стал равен 0, потенциал первой строчки таблицы должен быть равен -10; для обнуления коэффициента издержек клеточки (1;2) потенциал второго столбца должен быть -10 и т.д.
Изменённые коэффициенты выписываются в виде матрицы оценок:
Аспект оптимальности (базовое распределение поставок правильно и тогда лишь тогда, когда оценки всех вольных клеток неотрицательны) на данном шаге не выполнен – находятся 2 вольные клеточки с отрицательными оценками.
Продолжим оптимизацию (табл. 8). Составим цикл пересчёта для клеточки (5;2) и дадим поставку неё:
Таблица 8
B1
B2
B3
ai
A1
10
300
20
400
32
—
700
A2
12
—
50
—
25
600
600
A3
21
—
18
200
50
—
200
A4
25
—
15 —
100
23 +
100
200
A5
21
—
30 +
—
40 —
100
100
A6
0
—
0
—
0
200
200
Bj
300
700
1000
2000
В верхнем правом углу знаком «+» отмечаются те клеточки, поставки в которые увеличатся, а знаком «-» — те, в которые уменьшатся. Большая вероятная поставка, исходя из текущего цикла пересчёта равна min {100, 100, 100} = 100. Передвигаем её по циклу (табл. 9):
Таблица 9
B1
B2
B3
ai
A1
10
300
20
400
32
—
700
-10 (2)
A2
12
—
50
—
25
600
600
-7 (8)
A3
21
—
18
200
50
—
200
-8 (4)
A4
25
—
15
0
23
200
200
-5 (5)
A5
21
—
30
100
40
—
100
-20 (6)
A6
0
—
0
—
0
200
200
18 (9)
Bj
300
700
1000
2000
0 (1)
-10 (3)
-18 (7)
Опосля передвижения освободились сходу 2 клеточки, решение закончило быть базовым. Для того, чтоб оно осталось базовым, дадим фиктивную поставку в клеточку (4;2).
опять составляем матрицу оценок по вышеприведённому методу:
На текущем шаге клеток с отрицательной оценкой нет, как следует, аспект оптимальности выполнен.
Проверим решение при помощи способа потенциалов (табл. 10). Примем a1 = 0, тогда bj = cij – ai (для заполненных клеток). Если отысканное решение справедливо, то во всех пустых клеточках таблицы Δij = cij – (ai + bj ) ≥ 0, и Δij = 0 в заполненных клеточках. Получим последующую таблицу (в скобках показаны оценки клеток):
Таблица 9
B1
B2
B3
ai
A1
10 (0)
300
20 (0)
400
32 (4)
—
700
-10 (2)
A2
12 (5)
—
50 (33)
—
25 (0)
600
600
-7 (8)
A3
21 (13)
—
18 (0)
200
50 (24)
—
200
-8 (4)
A4
25 (20)
—
15 (0)
0
23 (0)
200
200
-5 (5)
A5
21 (1)
—
30 (0)
100
40 (2)
—
100
-20 (6)
Bj
300
700
1000
0 (1)
-10 (3)
-18 (7)
Условие Δij ≥ 0 производится, как следует, решение верное.
Ответ:
Таблица 10
B1
B2
B3
ai
A1
10
300
20
400
32
—
700
A2
12
—
50
—
25
600
600
A3
21
—
18
200
50
—
200
A4
25
—
15
—
23
200
200
A5
21
—
30
100
40
—
100
Bj
300
700
1000
1800/2000
Суммарные Издержки на перевозку составляют:
задачка 4
Условие
Решение задачки нелинейного программирования
Найти экстремум мотивированной функции вида
F = c11x12+c22x22+c12x1x2+b1x1+b2x2
при критериях
a11x1+a12x2<=>p1
a21x1+a22x2<=>p2 .
Данные размещаются в табл. 11.
1. Отыскать стационарную точку мотивированной функции и изучить ее (функцию) на неровность (вогнутость) в округах стационарной точки.
2. Составить функцию Лагранжа.
3. Получить систему неравенств в согласовании с аксиомой Куна-Таккера.
4. Используя способ искусственных переменных составить симплекс-таблицу и отыскать решение приобретенной задачки линейного программирования.
5. Отдать ответ с учетом критерий дополняющей нежёсткости.
Таблица 11
b1
b2
c11
c12
c22
extr
a11
a12
a21
a22
p1
p2
Знаки огр.
1
2
1
8
-1
0.5
-1
max
1
1
0
1
7
5
≤
≤
Решение
Мотивированная функция имеет вид:
Ограничения:
,
1. Определим относительный максимум функции. Для этого нужны координаты стационарной точки 
.
, 
Получили стационарную точку (1.6;4.4).
2. Исследуем стационарную точку на максимум, для чего же и определим вогнутость функции f.
,
Условия производятся, как следует мотивированная функция является строго вогнутой в округи стационарной точки.
3. Составим функцию Лагранжа:
Составим систему неравенств в согласовании с аксиомой Куна-Таккера.
А)
Б)
Перепишем систему А:
A1)
.Вводим доп переменные v1, v2, w1, w2, превращающие неравенства системы А1 в равенства: 
A2) 
перепишем систему Б:
Б2)
— условия дополняющей нежёсткости
Решим систему А2 при помощи способа искусственных переменных. 
в 1-ое и 2-ое уравнение системы А2.
Вводим псевдоцелевую функцию
базовые переменные: y1, y2, w1, w2
вольные переменные: x1, x2, v1, v2, u1, u2
Решаем эту задачку симплекс-методом при помощи таблиц и маленький программки на языке Си, текст которой приведён в Приложении 1.
Таблица 12
bi
x1
x2
u1
u2
v1
v2
y1
1
0.5
2
0.5
-0.5
-0.25
1
0.5
0
0
-1
-0.5
0
0
y2
8
0.25
-0.5
0.25
2
-0.125
1
0.25
1
0
0
-0.25
-1
0
w1
7
-0.5
1
-0.5
1
0.25
0
-0.5
0
0
0
0.5
0
0
w2
5
0
0
0
1
0
0
0
0
0
0
0
0
0
Y’
9M
0.75M
-1.5M
0.75M
-1.5M
-0.375M
-2M
0.75M
-1M
0M
1M
-0.75M
1M
0M
Таблица 13
bi
y1
x2
u1
u2
v1
v2
x1
0.5
1.1
0.5
0.03333
-0.25
0.1333
0.5
0.1667
0
0.1333
-0.5
-0.03333
0
-0.1333
y2
8.25
4.4
0.25
0.1333
1.875
0.5333
1.25
0.6667
1
0.5333
-0.25
-0.1333
-1
-0.5333
w1
6.5
-5.5
-0.5
-0.1667
1.25
-0.6667
-0.5
-0.8333
0
-0.6667
0.5
0.1667
0
0.6667
w2
5
-4.4
0
-0.1333
1
-0.5333
0
-0.6667
0
-0.5333
0
0.1333
0
0.5333
Y’
9.75M
8.25M
0.75M
0.25M
-1.875M
1M
-1.25M
1.25M
-1M
1M
0.25M
-0.25M
1M
-1M
Таблица 14
bi
y1
y2
u1
u2
v1
v2
x1
1.6
0.5333
0.1333
0.6667
0.1333
-0.5333
-0.1333
x2
4.4
0.1333
0.5333
0.6667
0.5333
-0.1333
-0.5333
w1
1
-0.6667
-0.6667
-1.333
-0.6667
0.6667
0.6667
w2
0.6
-0.1333
-0.5333
-0.6667
-0.5333
0.1333
0.5333
Y’
18M
1M
1M
0M
0M
0M
0M
Среднее решение:
y1=y2=u1=u2=v1=v2=0
x1=1.6
x2=4.4
w1=1
w2=0.6
Проверим условие дополняющей нежёсткости:
xi*vi=0
ui*wi=0
Условия производятся, как следует, x1=1.6, x2=4.4 являются решением начальной задачки kвадратичного программирования. Координаты стационарной точки совпадают с координатами, приобретенных в качестве ответа. Стационарная точка удовлетворяет условиям ограничений.
Ответ:
x1=1.6
x2=4.4
f(x1;x2) = 0
приложение 1
Для решения задачки #4 применена последующая программка на языке Си, скомпилированная gcc (GCC) 4.0.0 20050519 (Red Hat 4.0.0-8). Её текст приведён ниже:
#include <stdio.h>
#define x 7
#define y 5
double mc[x*y] =
{
1, 2, -0.5, 1, 0, -1, 0,
8, -0.5, 2, 1, 1, 0, -1,
7, 1, 1, 0, 0, 0, 0,
5, 0, 1, 0, 0, 0, 0,
9, -1.5, -1.5, -2, -1, 1, 1
};
double mt[x*y];
void mprint (double* m, int xs, int ys)
{
int i, j;
printf («n»);
for (j = 0; j < ys; j++)
{
for (i = 0; i < xs; i++)
{
printf («%10.4lg «, m[j*xs+i]);
}
printf («n»);
}
}
int main (void)
{
int i, j, i1, j1, it, jt;
double msx, msx1;
// Избираем разрешающий эл-т
nextmtx:
printf («nИсходная матрица коэффициентов:»); mprint (mc, x, y);
getch ();
msx = 10000.;
for (i = 0; i < x; i++)
{
if (mc[(y-1)*x+i] < 0)
{
// Может быть, найден разрешающий столбец
for (j = 0; j < y; j++)
{
// Отыскиваем меньшее отношение своб. члена к эл-ту разр. столбца
if (mc[j*x+i] < 1e-32)
continue; // Нулевой либо отрицательный
msx1 = mc[j*x] / mc[j*x+i];
if (msx > msx1) // Личное св.ч / р.эл
{
msx = msx1; // меньшее отыскиваем
it = i; jt = j; // координаты р.эл.
}
}
if (msx > 9999.) continue; // Нет положительных эл-тов
else // найден р.эл., mx != 0
{
i = it; j = jt; // его координаты
}
printf («n Разрешающий элемент: a(%d;%d) = %lg», j+1, i+1, mc[j*x+i]);
if (mc[j*x+i] > 0)
{
// Это и есть разрешающий элемент (s_el), находим оборотную величину
mt[j*x+i] = 1. / mc[j*x+i];
for (i1 = 0; i1 < x; i1++)
{
// Разрешающая строчка ( 1/s_el)
if (i1 == i) continue; // Пропустить сам s_el
mt[j*x+i1] = mt[j*x+i] * mc[j*x+i1];
}
for (j1 = 0; j1 < y; j1++)
{
// Разрешающий столбец (-1/s_el)
if (j1 == j) continue; // Пропустить сам s_el
mt[j1*x+i] = — mt[j*x+i] * mc[j1*x+i];
}
// удачно составлены разр. строчка и столбец.
// сейчас составляем другие коэфф-ты
for (j1 = 0; j1 < y; j1++)
{
if (j1 == j) continue; // Пропустить всю разреш. строчку
for (i1 = 0; i1 < x; i1++)
{
if (i1 == i) continue; // И столбец тоже
// Произведение нижней части столбца
// на высшую часть строчки
mt[j1*x+i1] = mt[j1*x+i] * mc[j*x+i1];
}
}
/*
* Всё. Готова матрица нижних значений, сейчас необходимо
* поместить всё на свои места в mc
*/
printf («nМатрица нижних значений:»); mprint (mt, x, y);
getch ();
for (j1 = 0; j1 < y; j1++)
{
for (i1 = 0; i1 < x; i1++)
{
if ((j1 == j) || (i1 == i))
{
/*
* Разрешающая строчка либо столбец
* просто ложим элементы в mc
*/
mc[j1*x+i1] = mt[j1*x+i1];
}
else
// по другому — сумму
mc[j1*x+i1] += mt[j1*x+i1];
}
}
// Всё готово к следующему шагу.
goto nextmtx; // след. матрица
}
// Этот эл-т не подступает, т.к. он отрицательный
}
// Если так и не было пригодного эл-та, то проверяем след. столбец
}
// отрицательны коэфф-тов при мотивированной ф-ции не найдено, как следует, решение нормально
printf («nОптимизировано. Ответ:»); mprint (mc, x, y);
return 0;
}
программка компилировалась командной строчкой:
gcc simplex.c -o simplex
, запускалась:
./simplex
и выдавала на консоль пошаговое решение задачки, которое было занесено в симплекс-таблицы (см. табл. 12-14) четвёртой задачки данной курсовой работы.
Перечень использованной литературы
1. Кремер Н. Ш., Путко Б. А., Трощин И. М. «Исследование операций в экономике» — М.: ЮНИТИ, 2004. — 407 с.
2. Плотникова Н. В. Курс лекций (ПС)
]]>