Реферат: Задачи по теории принятия решений
УНИВЕРСИТЕТ РОССИЙСКОЙ АКАДЕМИИ ОБРАЗОВАНИЯ
Факультет: Бизнес, Маркетинг,Коммерция
Дисциплина: Теория принятиярешений
Тема контрольной работы: [Задачипо четвёртому варианту]
Ф.И.О. студента: Спрыжков Игорь Максимович
Курс: 4. Семестр: 7. Номерзачетной книжки: 1818.
Дата сдачи: _____________________
Ф.И.О. преподавателя: АсташкинС.В.
Оценка: _________________________ Подпись:_________________________
Дата проверки: __________________
<span Times New Roman",«serif»;mso-fareast-font-family:«Times New Roman»; mso-font-kerning:8.0pt;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">Задача 1Условие
Решить симплекс-методом задачу, предварительно приведя её кканоническому виду:
x1 – x2 – x3 +7x4 → max
-x1+ 2x2 – x3 + x4 ≤ 2
2x1+ x2 + x3 – 2x4 ≤ 12
2x1+ 3x2 + 4x3 + 2x4 ≤ 6
xj≥ 0, j = 1, 2, 3,4
РешениеОбщий вид задачи линейного программирования в каноническойформе:
∑aij= bi, i = 1, 2, …, n
xj≥ 0, j = 1, 2, …, n, n+1, n + m
∑pjxj→ max
Экономико-математическая модель рассматриваемойзадачи в канонической форме будет иметь вид:
-1x1+ 2x2 – 1x3 + 1x4 + 1x5 + 0x6 + 0x7 = 2
2x1 + 1x2 + 1x3 — 2x4 + 0x5 + 1x6 + 0x7 = 12
2x1 + 3x2 + 4x3 + 2x4 + 0x5 + 0x6 + 1x7 = 6
xj ≥ 0, j = 1, 2, …, 7
x1– x2 – x3 + 7x4 + 0x5 + 0x6 + 0x7 → max
Т.е. в ней линейная форма максимизируется, все ограниченияявляются равенствами, все переменные удовлетворяют условию неотрицательности.
Система уравнений имеет предпочитаемый вид: базиснымипеременными являются переменные Х5, Х6, Х7,правые части неотрицательны. Исходноеопорное решение, дающее координаты исходной угловой точки, имеет вид Х = (0, 0,0, 0, 2, 12, 6)т.
Все остальные вычисления и действия удобно производит втабличной форме (табл. 1 – 3).
Решение задачи потребовало три итерации, каждой из которыхсоответствует симплекс-таблица.
В первую строку первой симплекс-таблицы занесены все данныепервого уравнения, во вторую – второго и т.д.
В каждой из таблиц во втором столбце (Бx) указаны базисныенеизвестные. Неизвестные, не входящие в базис, равны нулю. Значения базисныхнеизвестных записаны в третьем столбце (X0). Нижний элемент этого столбца является значениемкритерия оптимальности на данном шаге. В первом столбце (Pj) представлены коэффициентыпри базисных неизвестных, взятые из критерия оптимальности. Каждый из столбцов X1 – X4 соответствуетосновным переменным задачи, а столбцов X5 – X7– дополнительным переменным задачи. Последние элементы этих столбцов образуютнижнюю строку, содержащую элементы ∆J. С их помощью определяется,достигнут ли оптимум, а если не достигнут, то какое небазисное неизвестноеследует ввести в базис, чтобы улучшить план. Элементы последнего столбца(θ) позволяют найти то из прежних базисных неизвестных, которое следуетвывести из базиса, чтобы улучшить план. Разрешающий элемент, расположенный напересечении столбца, вводимого в базис неизвестного, и строки неизвестного, выводимогоиз базиса, выделен в каждой таблице.
Рассмотрим первую симплексную таблицу решения задачи.
План задачи находится в столбцах Бх и Х0.
Элементы столбцов Х1 – Х7 являютсякоэффициентами замещения неизвестных. Они показывают, в каком соотношении любыеиз неизвестных могут заменить базисные переменные в плане данного шага.
Элементы нижней строки столбцов Х1 – Х7показывают размер уменьшения значения критерия оптимальности от замены базисныхнеизвестных Хj.
Показатель Δj рассчитывается перемножением элемента первого столбцатаблицы (Pj)на элемент столбца Хjс последующим вычитанием соответствующего элемента Pj.
После нахождения L0 и Δj, проверяется условий оптимальности (все Δj > 0) и неразрешимости(если найдется хотя бы один Δj < 0 такой, что все элементы соответствующего столбцаотрицательны).
Наличие отрицательных Δjсвидетельствуето том, что найденный план производства не является оптимальным, так как имеютсявозможности увеличения прибыли.
В качестве разрешающего столбца (неизвестной) может бытьвзят любой столбец, для которого оценочный коэффициент отрицательный. Однако заразрешающий столбец обычно принимают столбец, для которого отрицательныйоценочный коэффициент принимает наименьшее значение.
Для определения неизвестного, которое необходимо вывести избазиса, используют показатели последнего столбца θ. Он получен путемделения элемента третьего столбца Х0на элемент столбцанеизвестного, вводимого в базис следующего шага. Параметр θ показывает,какой ресурс нас лимитирует, поэтому из базиса выводится переменная,соответствующая наименьшему положительному значению θ.
Строка в новой таблице, соответствующая разрешающей,получается из разрешающей строки делением всех элементов на разрешающийэлемент.
Столбцы, соответствующие базисным неизвестным, являютсяединичными, причем единица стоит на пересечении строки и столбца с одинаковымипеременными.
После заполнения новой таблицы (всякая новая таблицаявляется новой по отношению к рассматриваемой) снова проверяется выполнениеусловий оптимальности и разрешимости задачи.
В третьей симплекс-таблице выполняется условиеоптимальности. Решение задачи прекращается. Максимальное значение линейнойформы: LОПТ= 18.
Ответ: оптимальное решение х* = (0.5; 0;0; 2.5), т.е. х1* = 0.5, х2* = 0, х3*= 0, х4* = 2.5.
Таблица SEQ Таблица * ARABIC 1
Симплексная таблица первого плана задачи
Pi
Бx
X0
X1
X2
X3
X4
X5
X6
X7
θ
X5
2
-1
2
-1
1
1
2
X6
12
2
1
1
-2
1
-
X7
6
2
3
4
2
1
3
∆j
-1
1
1
-7
<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;font-variant:small-caps;mso-font-kerning:8.0pt;mso-ansi-language: RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">Таблица SEQ Таблица * ARABIC 2
Симплексная таблица второго плана задачи
Pi
Бx
X0
X1
X2
X3
X4
X5
X6
X7
θ
7
X4
2
-1
2
-1
1
1
-
X6
18
4
4
5
1
1
4.5
X7
2
4
-1
6
-2
1
0.5
∆j
14
-8
15
-6
7
Таблица SEQ Таблица * ARABIC 3
Симплексная таблица третьего плана задачи
Pi
Бx
X0
X1
X2
X3
X4
X5
X6
X7
7
X4
2.5
1.75
0.5
1
0.5
0.25
X6
4
1.25
-0.25
0.5
0.25
1
X1
0.5
1
-0.25
1.5
-0.5
0.25
∆j
18
13
6
3
2
Задача 2УсловиеРешить задачу применив симплекс-метод к соответствующейдвойственной задаче.
х1– х2 – 6х3 + 2х4+ 12х5 → min
2х1– х2 + х3 + х4 + 2х5 ≥ 3
-x1 + 2x2 – 2х3 + 3х4+ х5 ≥ 2
х1– х2 + 3х3 + х4 + 3х5 ≥ 1
РешениеЗапишем двойственную задачу:
2y1 – y2 + y3 ≤ 1
-y1 + 2y2 - y3 ≤ -1
y1 – 2y2 + 3y3 ≤-6
y1 + 3y2 + y3 ≤ 2
2y1 + y2 + 3y3 ≤ 12
max(3y1+ 2y2 + y3) — ?
Сведём задачу к каноническому виду:
2y1– y2 + y3 + y4 = 1
-y1 + 2y2 - y3 + y5 = -1
y1 – 2y2 + 3y3+ y6 = -6
y1 + 3y2 + y3 + y7 = 2
2y1 + y2 + 3y3 + y8= 12
max(3y1+ 2y2 + y3) — ?
Все остальные вычисления и действия удобно производит втабличной форме (табл. 4– 6).
Таблица SEQ Таблица * ARABIC 4
Симплексная таблица первого плана задачи
Pi
Бy
y0
3
2
1
θ
y1
y2
y3
y4
y5
y6
y7
y8
y4
1
2
-1
1
1
0.5
y5
-1
-1
2
-1
1
1
y6
-6
1
-2
3
1
-
y7
2
1
3
1
1
2
y8
12
2
1
3
1
6
∆j
-3
-2
-1
Таблица SEQ Таблица * ARABIC 5
Симплексная таблица второго плана задачи
Pi
Бy
y0
3
2
1
θ
y1
y2
y3
y4
y5
y6
y7
y8
3
y1
0.5
1
-0.5
0.5
0.5
-
y5
-7
2
1
1
∞
y6
-8
-5
2
1
-1
1.6
y7
1
5
1
1
0.2
y8
11
2
2
-1
1
5.5
∆j
1.5
-3.5
0.5
1.5
Таблица SEQ Таблица * ARABIC 6
Симплексная таблица третьего плана задачи
Pi
Бy
y0
3
2
1
y1
y2
y3
y4
y5
y6
y7
y8
3
y1
0.6
1
0.5
0.5
0.1
0.1
y5
-7
2
1
1
y6
-7
2
1
1
2
y2
0.2
1
0.2
0.2
y8
10.6
2
-1
-0.4
-0.4
1
∆j
2.2
0.5
1.5
0.3
0.3
y4 ↔x1 x1= 1
y5 ↔x2 x2= 0
y6 ↔x3 x3 =0
y7 ↔x4 x4= 1
y8 ↔x5 x5= 0
Ответ: оптимальное решение х* = (1; 0; 0;10), т.е. х1* = 1, х2* = 0, х3*= 0, х4* = 1, х5* = 0.
Задача 3Для рытья котлована объёмом 1440 м3 строителиполучили три экскаватора. Мощный экскаватор производительностью 22.5 м3/часрасходует в час 10 литров бензина. Аналогичные характеристики среднего экскаватора– 10 м3/час и 10/3 л/час, малого – 5 м3и 2 л/час. Экскаваторы могут работать одновременно, не мешая друг другу. Запасбензина у строителей ограничен и равен 580 литров. Если рыть котлован толькомалым экскаватором, то бензина заведомо хватит, но это будет очень долго. Какимобразом следует использовать имеющуюся технику, чтобы выполнить работу какможно скорее?
РешениеПусть экскаваторы работали x1, x2, x3 (час) соответственно,тогда
22.5x1+ 10x2 + 5x3 = 1440 – объемработ
10x1+ 10/3 x2+ 2x3≤ 580 – ограничения по расходу бензина
x1,x2, x3 ≥ 0
α =max(x1, x2, x3) → min
Значение αравно наибольшему из значений x1,x2, x3 и это значениенужно взять наименьшим.
Решим задачу графически.
<img src="/cache/referats/6118/image004.gif" align=«left» hspace=«12» v:shapes="_x0000_s1029">
Множество допустимых значений – фигура ABCD.
Определим координаты точки A:
22.5x1+ 10x2 + 5·0= 1440
10x1 + 10/3x2 + 2·0 =580
30x1+ 10x2 =1740
7.5x1= 300
x1= 40 (час)
x2= (1440 – 22.5·40)/10 = 54 (час)
Определим координаты точки B:
22.5x1+ 10·0 + 5x3= 1440
10x1+ 10/3 ·0 + 2x3 = 580
45x1+ 10x3 =2880
50x1+ 10x3 =2900
5x1= 20
x1= 4
x3= (1440 – 22.5·4)/5 = 270
Итак, определены координаты всех точек:
A(40;54;0)
B(4;0;270)
C(64;0;0)
D(58;0;0)
Искомое решение задачи – точка A.
Ответ: оптимальный режим работы экскаваторов:Мощный экскаватор – 40часов, Средний экскаватор – 54 часа, Малый экскаватор –не используется.
Задача 4В пекарне для выпечки четырех видов хлеба используется мукадвух сортов, маргарин и яйца. Имеющееся оборудование, производственные площадии поставки продуктов таковы, что в сутки можно переработать не более 290 кгмуки первого сорта, 150 кг муки второго сорта, 50 кг маргарина, 1280 шт. яиц. Втаблице приведены нормы расхода продуктов, а также прибыль от продажи 1 кгхлеба каждого вида:
Таблица SEQ Таблица * ARABIC 7
Наименование продукта
Нормы расхода на 1 кг хлеба (по видам)
1
2
3
4
мука 1 сорта, кг
0.5
0.5
мука 2 сорта, кг
0.5
0.5
маргарин, кг
0.125
0.125
яйцо, шт.
2
1
1
1
прибыль, за 1 кг
14
12
5
6
Требуется определить суточный план выпечки хлеба,максимизирующий прибыль.
Решение0.5x1 + 0.5x2 + 0·x3 + 0·x4 ≤ 290
0·x1 + 0·x2 + 0.5x3 + 0.5x4 ≤ 150
0.125x1+ 0·x2 + 0·x3 + 0.125x4 ≤ 50
2x1 + 1x1 + 1x3 + 1x4 ≤ 1280
14x1 + 12x2 + 5x3 + 6x4 → max
Все остальные вычисления и действия удобно производит втабличной форме (табл. 8 – 11).
<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;font-variant:small-caps;mso-font-kerning:8.0pt;mso-ansi-language: RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">Таблица SEQ Таблица * ARABIC 8
Симплексная таблица первого плана задачи
Pi
Бx
X0
14
12
5
6
θ
x1
x2
x3
x4
x5
x6
x7
x8
x5
290
0.5
0.5
1
580
x6
150
0.5
0.5
1
∞
x7
50
0.125
0.125
1
400
x8
1280
2
1
1
1
1
640
∆j
-14
-12
-5
-6
Таблица SEQ Таблица * ARABIC 9
Симплексная таблица второго плана задачи
Pi
Бx
X0
14
12
5
6
θ
x1
x2
x3
x4
x5
x6
x7
x8
x5
90
0.5
-0.5
1
-4
180
x6
150
0.5
0.5
1
∞
14
x1
400
1
1
8
∞
x8
120
-1
1
1
-4
1
-
∆j
5600
-12
-5
-8
112
Таблица SEQ Таблица * ARABIC 10
Симплексная таблица третьего плана задачи
Pi
Бx
X0
14
12
5
6
θ
x1
x2
x3
x4
x5
x6
x7
x8
12
x2
180
1
-1
2
-8
∞
x6
150
0.5
0.5
1
300
14
x1
400
1
1
8
∞
x8
300