Реферат: Задачи по теории принятия решений

УНИВЕРСИТЕТ РОССИЙСКОЙ АКАДЕМИИ ОБРАЗОВАНИЯ

Факультет: Бизнес, Маркетинг,Коммерция

Дисциплина: Теория принятиярешений

Тема контрольной работы: [Задачипо четвёртому варианту]

Ф.И.О. студента: Спрыжков Игорь Максимович

Курс: 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

еще рефераты
Еще работы по экономико-математическому моделированию