Полный текст:
Содержание
Задание 1. 3
Задание 2. 5
Задание 3. 9
Задание 4. 12
Задание 5. 15
Задание 6. 17
Задание 7. 19
Литература. 21
Задание 1
НАХОЖДЕНИЕ РЕШЕНИЯ ЗАДАЧИ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ГРАФИЧЕСКИМ МЕТОДОМ
Найти максимум и минимум функции цели F при
условиях:
F =3x1 + 2x2
Решение
Решим эту задачу
графическим методом. Изобразим на координатной плоскости область допустимых
решений, ограниченную заданными неравенствами (номер в скобках возле линий
соответствует номеру неравенства в системе ограничений).
Учитывая направления этих
ограничений относительно прямых, строим область допустимых решений (обведенный
жирными линиями треугольник АВС).
Построим вектор F, соответствующий функции
цели F = 3х1
+ 2х2.
Крайние точки области в
направлении возрастания и убывания функции цели – А (минимум) и С (максимум).
Найдем их координаты и экстремальные значения целевой функции:
.
.
Ответ: ; .
Задание 2
Нахождение оптимального плана симплексным методом
Для изготовления
различных изделий А, В, С предприятие использует три различных типа сырья.
Нормы расхода сырья на производство одного изделия каждого типа, цена одного
изделия А, В, С, а также общее количество сырья каждого типа, которая может
быть использована предприятием, приведены в таблице.
Изделия А, В, С могут
производиться в любых отношениях, но производство ограничено выделенным
предприятию сырьем каждого типа. Составить план производства А, В, С, при
котором общая стоимость всей произведенной предприятием продукции будет
максимальной.
Вид сырья
Нормы
расхода сырья (кг) на одно изделие
Общее
количество сырья (кг)
А
В
С
І
15
10
7
380
ІІ
5
4
10
350
ІІІ
6
3
9
320
Цена
одного изделия (грн.)
10
8
11
Решение
Обозначим через х1,
х2 и х3 количество единиц продукции А, В, С. Тогда задача
описывается математической моделью – задачей линейного программирования:
Для решения задачи
симплекс-методом сведем ее к каноническому виду:
Базис – х4, х5, х6:
і
Сб
Б
А0
10
8
11
0
0
0
?і
А1
А2
А3
А4
А5
А6
1
0
Х4
380
15
10
7
1
0
0
380/7
2
0
Х5
350
5
4
10
0
1
0
350/10
3
0
X6
320
6
3
9
0
0
1
320/9
m+1
0
-10
-8
-11
0
0
0
Сначала выбираем столбик
для выбора ведущего элемента. Это столбик с минимальным значением в последней строке:
.
Соответственно, ведущий
столбик – 3-й.
Теперь выбираем ведущую
строку. Это строка с минимальным значением отношения ? (определяется делением
столбика А0 на А3):
.
Соответственно, ведущая
строка – 1-я (х5), а ведущий элемент лежит на пересечении строки х5
и столбика А3.
Осуществим Жордановы
преобразования таблицы относительно этого элемента:
і
Сб
Б
А0
10
8
11
0
0
0
?і
А1
А2
А3
А4
А5
А6
1
0
Х4
135
32/2
36/5
0
1
-7/10
0
270/32
2
11
Х3
35
1/2
2/5
1
0
1/10
0
70
3
0
X6
5
3/2
-3/5
0
0
-9/10
1
10/3
m+1
385
-9/2
-18/5
0
0
11/10
0
і
Сб
Б
А0
10
8
11
0
0
0
?і
А1
А2
А3
А4
А5
А6
1
0
Х4
290/3
0
59/5
0
1
31/5
-23/3
1450/177
2
11
Х3
100/3
0
3/5
1
0
2/5
-1/3
500/9
3
10
X1
10/3
1
-2/5
0
0
-3/5
2/3
–
m+1
400
0
-27/5
0
0
-8/5
3
і
Сб
Б
А0
10
8
11
0
0
0
?і
А1
А2
А3
А4
А5
А6
1
8
Х2
1450/177
0
1
0
5/59
31/59
-115/177
–
2
11
Х3
5030/177
0
0
1
-3/59
5/59
10/177
5030/10
3
10
X1
390/59
1
0
0
2/59
-23/59
24/59
390/24
m+1
26210/59
0
0
0
27/59
73/59
-30/59
і
Сб
Б
А0
10
8
11
0
0
0
?і
А1
А2
А3
А4
А5
А6
1
8
Х2
75/4
115/72
1
0
5/36
-7/72
0
2
11
Х3
55/2
-5/36
0
1
-1/18
5/36
0
3
0
X6
65/4
59/24
0
0
1/12
-23/24
1
m+1
905/2
5/4
0
0
1/2
3/4
0
(m+1)-я строка последней
таблицы не содержит отрицательных чисел, следовательно, этот план является
оптимальным:
х1 = 0;
х2 = 75/4;
х3 = 55/2;
Zmax
= Z (0; 75/4; 55/2) = 905/4.
Ответ:
Для получения
максимального дохода в размере 905/4 грн. предприятию следует выпускать 75/4 и 55/2 ед. продукции
В и С соответственно.
Задание 3
Двойственные задачи
Для данной задачи
составить двойственную и найти решение обеих задач.
F = 10x1 + 5x2
® max
x1 ? 0, х2
? 0
Решение
Для решения исходной
задачи симплекс-методом приведем ее к каноническому виду:
Базис – х3, х4:
і
Сб
Б
А0
10
5
0
0
?і
А1
А2
А3
А4
1
0
X3
60
3/10
3/20
1
0
200
2
0
X4
70
1/2
7/10
0
1
140
m+1
0
-10
-5
0
0
Сначала выбираем столбик
для выбора ведущего элемента. Это столбик с минимальным значением в (m+1)-й
строке:
.
Соответственно, ведущий столбик
– 1-й.
Теперь выбираем ведущую
строку. Это строка с минимальным значением отношения ? (определяется делением
столбика А0 на А1):
.
Соответственно, ведущая
строчка – 2-я (х4), а ведущий элемент лежит на пересечении строки х4
и столбика А1.
Осуществим Жордановы
преобразования таблицы относительно этого элемента:
і
Сб
Б
А0
10
5
0
0
?і
А1
А2
А3
А4
1
0
X3
1800
0
-27
1
-60
2
10
X1
140
1
7/5
0
1/5
m+1
1400
0
9
0
20
(m+1)-я строка последней
таблицы не содержит положительных чисел, следовательно, этот план является
оптимальным:
х1 = 140;
х2 = 0;
Fmax
= F(140;0) = 1400.
По теории двойственности,
запишем задачу, двойственную к исходной.
Чтобы из задачи построить
двойственную, можно воспользоваться следующими соотношениями между ними.
1) прямая задача –
максимизации, двойственная – минимизации;
2) поскольку все
переменные прямой задачи неотрицательны, то все ограничения двойственной задачи
типа "?";
3) поскольку в системе
неравенств прямой задачи первые ограничения типа "?", то две
переменные двойственной задачи являются неотрицательными;
4) коэффициенты целевой функции
прямой задачи соответствуют ограничениям по ресурсам двойственной и наоборот,
ограничение по ресурсам прямой задачи – это коэффициенты целевой функции в
двойственной задаче.
Матрица норм ресурсов
двойственной задачи получается путем транспонирования матрицы норм ресурсов
прямой задачи.
Найдем решение
двойственной задачи, воспользовавшись связью переменных: основные переменные
прямой задачи соответствуют дополнительным переменным двойственной и наоборот. Из
(m+1)-й строки последней симплексной таблицы решения исходной задачи выпишем
оптимальный план двойственной задачи (А3 – А4).
у1 = 0;
у2 = 20;
Zmin
= Z (0;20) = 60*0 + 70*20 = 1400.
Ответ:
Fmax
= F(140;0) = 1400; Zmin = Z(0;20) = 1400.
Задание 4
Транспортная задача линейного программирования
Дано:
m – количество пунктов производства некоторого
однородного груза;
п – количество пунктов потребления;
Qі – объем производства в i-м пункте;
Vj – объем потребления в j-м пункте;
(сіj) – матрица затрат на перевозку единицы груза из i-го
пункта производства в j-й пункт потребления.
Составить такой план
перевозок, при котором общая стоимость перевозок будет минимальной.
m = 3; n = 5;
Q1 = 200, Q2
= 300, Q3 = 250,
V1 = 120, V2
= 80, V3 =170, V4 = 220, V5 = 180.
Решение
Суммарный спрос равен 770,
предложение – 750. Введем условного поставщика Q4 = 20. Теперь задача является закрытой.
По методу минимальных
элементов строим опорный план перевозок (суть метода заключается в
первоочередном заполнении ячеек с минимальной стоимостью):
50 3
80 2
70 4
7
3
500
2
4
100 1
200 2
6
300
70 4
5
9
7
180 3
400
0
0
0
20 0
0
200
380
170
220
230
Проверим его
оптимальность по методу потенциалов (для заполненных ячеек: cij = ui
+ vj; для пустых ячеек условие оптимальности: cij ? ui
+ vj).
50 3
80 2
70 4
7
3
u1 = 0
2
4
100 1
200 2
6
u2 = -3
70 4
5
9
7
180 3
u3 = 1
0
0
0
20 0
0
u4 =
-5
v1 = 3
v2 = 2
v3 = 4
v4 =5
v5 = 2
u1 + v1 = 3;
u1 + v2 = 2;
u1 + v3 = 4;
u2 + v3 = 1;
u2 + v4 = 2;
u3 + v1 = 4;
u3 + v5 = 3;
u4 + v4 = 0.
Положим u1
= 0. Тогда:
u2 =
-3; u3 = 1; u4 = -5;
v1 = 3;
v2 = 2; v3 = 4; v4 = 5; v5 = 2.
Критерий оптимальности (cij
? ui + vj) выполняется
во всех пустых клетках, потому этот план является оптимальным.
х11
= 50; х12 = 80; х13 = 70;
х23
= 100; х24 = 200;
х31
= 70; х35 = 180;
х44
= 20.
Экономический
смысл этого плана состоит в следующем:
– 1-й пункт производства
отправит х11 = 50 ед. груза на 1-й пункт потребления; х12
= 80 ед. груза на 2-й пункт потребления; х13 = 70 ед. груза на 3-й
пункт потребления;
– 2-й пункт производства
отправит х23 = 100 ед. на 3-й пункт потребления; х24 =
200 ед. на 4-й пункт потребления;
– 3-й пункт производства
отправит х31 = 70 ед. продукции на 1-й пункт потребления; х35
= 180 ед. продукции на 5-й пункт потребления.
Кроме того, 5-тый пункт
потребления недополучит х35 = 20 ед. груза (дефицит).
При условии выполнения оптимального
плана производства минимальная стоимость перевозок составит:
.
Ответ:
х11
= 50; х12 = 80; х13 = 70; х23 = 100; х24
= 200; х31 = 70; х35 = 180; х44 = 20.
.
Задание 5
Матричная игра
Найти решение игры,
заданной такой матрицей:
Решение
Проверим существование
седловой точки у платежной матрицы:
;
.
? ? ?, т.е. матрица не
имеет седловой точки. Это означает, что игра не может быть решена в чистых
стратегиях. Итак, первый игрок будет применять смешанную стратегию х = (p1,
p2), где p1, p2 – вероятности, с которыми
игрок А применять соответствующие чистые стратегии А1, А2.
Игрок B будет применять смешанную стратегию у = (q1, q2),
где q1, q2 – вероятности, с которыми игрок B применять
соответствующие чистые стратегии В1, В2.
Итак, если игрок В
применяет чистую стратегию В1 или В2, то выигрыш игрока А
соответственно равен:
Тогда:
Решив систему, получим х
= (2/5,3/5), ? = 49/5.
Если игрок А применяет
чистую стратегию А1 или А2, то выигрыш игрока В
соответственно равен:
Тогда:
Решение системы у = (1/5,4/5),
? = 49/5.
Ответ
х = (2/5,3/5), у = (1/5,4/5),
? = 49/5.
Задание 6
Метод множителей Лагранжа
За сутки два
шарикоподшипниковых завода выпускают n шарикоподшипников. Затраты
на их производство первым заводом равны f1(x), вторым заводом – f2(x).
Определить, сколько шарикоподшипников должен изготовить каждый завод, чтобы
общие затраты на их производство были минимальными.
n = 10 000;
f1(x) = 3x12 + 2x1;
f2(x) = x22 + 4x2.
Решение
Ограничение имеет вид:
х1 + х2 = 10 000,
функция общих расходов:
f(x1,x2) = 3x12
+ 2x1 + x22 + 4x2.
Исследуем функцию на
экстремум (минимум) методом Лагранжа:
F(x1,x2,?) = 3x12
+ 2x1 + x22 + 4x2 – ?(х1
+ х2 – 10 000).
Вычислим ее
частные производные и приравняем их к нулю:
;
;
.
Решим систему и получим:
x1 = 4000,6; x2 = 5999,4.
Учтем дискретность (целочисленность)
переменной (речь идет о выпуске шарикоподшипников), поэтому следует рассмотреть
два варианта:
– выпуск 4000 и 6000
подшипников соответственно 1-м и 2-м заводами;
– выпуск 4001 и 5999
подшипников соответственно 1-м и 2-м заводами.
fmin(4000,6000) = 3*40002 +
2*4000 + 60002 + 4*6000 = 84 032 000 (у.е.);
fmin(4001,5999) = 3*40012 +
2*4001 + 59992 + 4*5999 = 84 044 002 (у.е.);
Расходы второго варианта
меньше.
Ответ:
Оптимальным является
выпуск первым и вторым заводом 4000 и 6000 подшипников соответственно. В таком
случае затраты на производство будут минимальными и составят 84 032 000
условных денежных единиц.
Задание 7
Основы ТЕОРИИ РИСКА
Предприятие должно
заключить договор на поставку сырья для производства одной из трех фирм А, В и
С. Статистическая информация по задержкам сроков поставок по месяцам за
прошедший год приведена в таблице. Необходимо оценить риск того, что каждая из
фирм оплатит товар в срок по договору поставки.
1.8.2.
Месяцы года
1
2
3
4
5
6
7
8
9
10
Задержка поставок, дни
А
1
4
0
3
1
5
2
4
2
1
В
4
4
1
5
1
1
1
3
5
2
С
1
2
3
4
2
4
0
4
3
1
Решение
Математическое ожидание
задержки определяется по формуле:
,
где
ti – задержка по месяцам; n – количество месяцев, i = 1,2,3 ,..., 10 – текущий
номер месяца.
Математическое ожидание:
;
;
.
Определим рискованность
операции с помощью стандартного (среднего квадратичного) отклонения ? как в
лучшую, так и в худшую сторону. Чем больше величина стандартного отклонения,
тем больше разброс возможного результата (тем больше экономический риск данной
операции).
Стандартное отклонение
определим по формуле:
,
где
D – дисперсия процесса, которая рассчитывается по формуле:
.
Коэффициент вариации
рассчитаем по формуле:
.
;
;
.
Выводы
Меньше показатель
задержки для фирмы А (в среднем 2,3 дней), меньшие колебания (меньший риск) у
фирмы С, потому делаем вывод о целесообразности взаимодействия именно с ней.
Литература
1.
Гетманцев
В.Д. Математика для економістів: Дослідж. операцій. Математ. програмування. /
Редкол.: В.Я. Кардаш (голова) та ін.; Київ. нац. екон. ун-т ім. В.Гетьмана. –
К., 2006. – 304 с.
2.
Дякон В.М.
Математичне програмування: Навч. посіб. для студ. вищ. навч. закл. / В.М.
Дякон, Л.Є. Ковальов; За заг. ред. В.М. Міхайленка; Європ. ун-т. – К., 2004. –
497 с.
3.
Егоршин А.А.
Математическое программирование: Учеб. пособие. / А.А.Егоршин, Л.М.Малярец;
Харьк. гос. экон. ун-т. – Х.: ИД «ИНЖЭК», 2003. – 239 с.
4.
Жильцов О.Б.
Математичне програмування (з елементами інформаційних технологій) : Навч.
посіб. для студ. вищ. навч. закл. / О.Б.Жильцов, В.Р.Кулян, О.О.Юнькова; За
ред. О.О.Юнькової; Межрегіон. акад. упр. персоналом (МАУП) – К., 2006. – 182 с.
5.
Математичне
програмування: Навч. посіб. для студ. вищ. техн. навч. закл. / Максимов О.В.,
Афанасьєва М.Г., Липовик В.В., Щербак А.Ф.; Криворіз. техн. ун-т. – Кривий Ріг:
Вид. дім, 2006. – 315 с.
6.
Математичне
програмування: Навч. посіб. / Глушик М.М., Копич І.М., Пенцак О.С.,
Сороківський В.М.; Укоопспілка, Львів. комерц. акад. – Львів, 2004. – 237 с.