Задачи по теории принятия решений
УНИВЕРСИТЕТ РОССИЙСКОЙ АКАДЕМИИ ОБРАЗОВАНИЯ
Факультет: Бизнес, Маркетинг, Коммерция
Дисциплина: Теория принятия решений
Тема контрольной работы: [Задачи по четвёртому варианту]
Ф.И.О. студента:
Задача 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 |
θ |
|
0 |
X5 |
2 |
-1 |
2 |
-1 |
1 |
1 |
0 |
0 |
2 |
|
0 |
X6 |
12 |
2 |
1 |
1 |
-2 |
0 |
1 |
0 |
- |
|
0 |
X7 |
6 |
2 |
3 |
4 |
2 |
0 |
0 |
1 |
3 |
|
∆j |
0 |
-1 |
1 |
1 |
-7 |
0 |
0 |
0 |
|
Таблица SEQ Таблица * ARABIC 2
Симплексная таблица второго плана задачи
|
Pi |
Бx |
X0 |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
θ |
|
7 |
X4 |
2 |
-1 |
2 |
-1 |
1 |
1 |
0 |
0 |
- |
|
0 |
X6 |
18 |
4 |
4 |
5 |
0 |
0 |
1 |
1 |
4.5 |
|
0 |
X7 |
2 |
4 |
-1 |
6 |
0 |
-2 |
0 |
1 |
0.5 |
|
∆j |
14 |
-8 |
15 |
-6 |
0 |
7 |
0 |
0 |
|
Таблица SEQ Таблица * ARABIC 3
Симплексная таблица третьего плана задачи
|
Pi |
Бx |
X0 |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
|
|
7 |
X4 |
2.5 |
0 |
1.75 |
0.5 |
1 |
0.5 |
0 |
0.25 |
|
|
0 |
X6 |
4 |
0 |
1.25 |
-0.25 |
0 |
0.5 |
0.25 |
0 |
|
|
1 |
X1 |
0.5 |
1 |
-0.25 |
1.5 |
0 |
-0.5 |
0 |
0.25 |
|
|
|
∆j |
18 |
0 |
13 |
6 |
0 |
3 |
0 |
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 |
0 |
0 |
0 |
0 |
0 |
θ |
|
y1 |
y2 |
y3 |
y4 |
y5 |
y6 |
y7 |
y8 |
||||
|
0 |
y4 |
1 |
2 |
-1 |
1 |
1 |
0 |
0 |
0 |
0 |
0.5 |
|
0 |
y5 |
-1 |
-1 |
2 |
-1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
0 |
y6 |
-6 |
1 |
-2 |
3 |
0 |
0 |
1 |
0 |
0 |
- |
|
0 |
y7 |
2 |
1 |
3 |
1 |
0 |
0 |
0 |
1 |
0 |
2 |
|
0 |
y8 |
12 |
2 |
1 |
3 |
0 |
0 |
0 |
0 |
1 |
6 |
|
∆j |
0 |
-3 |
-2 |
-1 |
0 |
0 |
0 |
0 |
0 |
|
Таблица SEQ Таблица * ARABIC 5
Симплексная таблица второго плана задачи
| Pi | Бy | y0 |
3 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
θ |
|
y1 |
y2 |
y3 |
y4 |
y5 |
y6 |
y7 |
y8 |
||||
|
3 |
y1 |
0.5 |
1 |
-0.5 |
0.5 |
0.5 |
0 |
0 |
0 |
0 |
- |
|
0 |
y5 |
-7 |
0 |
0 |
2 |
0 |
1 |
1 |
0 |
0 |
∞ |
|
0 |
y6 |
-8 |
0 |
-5 |
2 |
0 |
0 |
1 |
-1 |
0 |
1.6 |
|
0 |
y7 |
1 |
0 |
5 |
0 |
0 |
1 |
0 |
1 |
0 |
0.2 |
|
0 |
y8 |
11 |
0 |
2 |
2 |
-1 |
0 |
0 |
0 |
1 |
5.5 |
|
∆j |
1.5 |
0 |
-3.5 |
0.5 |
1.5 |
0 |
0 |
0 |
0 |
|
Таблица SEQ Таблица * ARABIC 6
Симплексная таблица третьего плана задачи
| Pi | Бy | y0 |
3 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
y1 |
y2 |
y3 |
y4 |
y5 |
y6 |
y7 |
y8 |
||||
|
3 |
y1 |
0.6 |
1 |
0 |
0.5 |
0.5 |
0.1 |
0 |
0.1 |
0 |
|
|
0 |
y5 |
-7 |
0 |
0 |
2 |
0 |
1 |
1 |
0 |
0 |
|
|
0 |
y6 |
-7 |
0 |
0 |
2 |
0 |
1 |
1 |
0 |
0 |
|
|
2 |
y2 |
0.2 |
0 |
1 |
0 |
0 |
0.2 |
0 |
0.2 |
0 |
|
|
0 |
y8 |
10.6 |
0 |
0 |
2 |
-1 |
-0.4 |
0 |
-0.4 |
1 |
|
|
∆j |
2.2 |
0 |
0 |
0.5 |
1.5 |
0.3 |
0 |
0.3 |
0 |
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 и это значение нужно взять наименьшим.
Решим задачу графически.
Задача 4
В пекарне для выпечки четырех видов хлеба используется мука двух сортов, маргарин и яйца. Имеющееся оборудование, производственные площади и поставки продуктов таковы, что в сутки можно переработать не более 290 кг муки первого сорта, 150 кг муки второго сорта, 50 кг маргарина, 1280 шт. яиц. В таблице приведены нормы расхода продуктов, также прибыль от продажи 1 кг хлеба каждого вида:
Таблица SEQ Таблица * ARABIC 7
| Наименование продукта | Нормы расхода на 1 кг хлеба (по видам) | |||
|
1 |
2 |
3 |
4 |
|
|
мука 1 сорта, кг |
0.5 |
0.5 |
0 |
0 |
|
мука 2 сорта, кг |
0 |
0 |
0.5 |
0.5 |
|
маргарин, кг |
0.125 |
0 |
0 |
0.125 |
|
яйцо, шт. |
2 |
1 |
1 |
1 |
|
прибыль, за 1 кг |
14 |
12 |
5 |
6 |
Требуется определить суточный план выпечки хлеба, максимизирующий прибыль.
Решение
0.5x1 + 0.5x2 +а 0x3 + 0x4 ≤а 290
0x1 +а 0x2 + 0.5x3 + 0.5x4 ≤а 150
0.125x1 +а 0x2 +а 0x3 + 0.125x4 ≤ 50
2x1 + 1x1 + 1x3 + 1x4 ≤ 1280
14x1 +а 12x2 + 5x3 + 6x4 →а max
Все остальные вычисления и действия добно производит в табличной форме (табл. 8 - 11).
Таблица SEQ Таблица * ARABIC 8
Симплексная таблица первого плана задачи
| Pi | Бx | X0 |
14 |
12 |
5 |
6 |
0 |
0 |
0 |
0 |
θ |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
||||
|
0 |
x5 |
290 |
0.5 |
0.5 |
0 |
0 |
1 |
0 |
0 |
0 |
580 |
|
0 |
x6 |
150 |
0 |
0 |
0.5 |
0.5 |
0 |
1 |
0 |
0 |
∞ |
|
0 |
x7 |
50 |
0.125 |
0 |
0 |
0.125 |
0 |
0 |
1 |
0 |
400 |
|
0 |
x8 |
1280 |
2 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
640 |
|
|
∆j |
0 |
-14 |
-12 |
-5 |
-6 |
0 |
0 |
0 |
0 |
|
Таблица SEQ Таблица * ARABIC 9
Симплексная таблица второго плана задачи
| Pi | Бx | X0 |
14 |
12 |
5 |
6 |
0 |
0 |
0 |
0 |
θ |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
||||
|
0 |
x5 |
90 |
0 |
0.5 |
0 |
-0.5 |
1 |
0 |
-4 |
0 |
180 |
|
0 |
x6 |
150 |
0 |
0 |
0.5 |
0.5 |
0 |
1 |
0 |
0 |
∞ |
|
14 |
x1 |
400 |
1 |
0 |
0 |
1 |
0 |
0 |
8 |
0 |
∞ |
|
0 |
x8 |
120 |
0 |
-1 |
1 |
1 |
-4 |
0 |
0 |
1 |
- |
|
|
∆j |
5600 |
0 |
-12 |
-5 |
-8 |
0 |
0 |
112 |
0 |
|
Таблица SEQ Таблица * ARABIC 10
Симплексная таблица третьего плана задачи
| Pi | Бx | X0 |
14 |
12 |
5 |
6 |
0 |
0 |
0 |
0 |
θ |
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
||||
|
12 |
x2 |
180 |
0 |
1 |
0 |
-1 |
2 |
0 |
-8 |
0 |
∞ |
|
0 |
x6 |
150 |
0 |
0 |
0.5 |
0.5 |
0 |
1 |
0 |
0 |
300 |
|
14 |
x1 |
400 |
1 |
0 |
0 |
1 |
0 |
0 |
8 |
0 |
∞ |
|
0 |
x8 |
300 |
0 |
0 |
1 |
0 |
-2 |
0 |
-8 |
1 |
300 |
|
|
∆j |
7760 |
0 |
0 |
-5 |
-4 |
24 |
0 |
16 |
0 |
|
Таблица SEQ Таблица * ARABIC 11
Симплексная таблица четвертого плана задачи
| Pi | Бx | X0 |
14 |
12 |
5 |
6 |
0 |
0 |
0 |
0 |
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
||||
|
12 |
x2 |
180 |
0 |
1 |
0 |
-1 |
2 |
0 |
-8 |
0 |
|
|
5 |
x3 |
300 |
0 |
0 |
1 |
1 |
0 |
2 |
0 |
0 |
|
|
14 |
x1 |
400 |
1 |
0 |
0 |
1 |
0 |
0 |
8 |
0 |
|
|
0 |
x8 |
300 |
0 |
0 |
0 |
-1 |
-2 |
-2 |
-8 |
1 |
|
|
|
∆j |
9260 |
0 |
0 |
0 |
1 |
12 |
10 |
16 |
0 |
|
Ответ: суточный план выпуска продукции: хлеб 1-го вида - 400 кг, 2-го вида - 180 кг 3-го вида - 300 кг, 4-го вида - 0 кг.
Список использованных источников