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

Заказать работу

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

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

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

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

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

Курс: 4. Семестр: 7. Номер зачетной книжки: 1818.

Дата сдачи: _____________________

Ф.И.О. преподавателя: Асташкин С.В.

Оценка: _________________________ Подпись: _________________________

Дата проверки: __________________


Задача 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.

Таблица 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

Таблица 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

Таблица 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).

Таблица 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

Таблица 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

Таблица 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 и это значение нужно взять наименьшим.

Решим задачу графически.

Множество допустимых значений – фигура ABCD.

Определим координаты точки A:

22.5x1 + 10x2 + 5·0 = 1440

10x1 + 10/3 x2 + 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 кг хлеба каждого вида:

Таблица 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 + 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).


Таблица 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

Таблица 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

Таблица 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

Таблица 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 кг.

Список использованных источников

·      Зубков М.Я. Математические структуры и математическое моделирование экономики: Учебное пособие. Вып. 3в. Математическое программирование. – М.: Изд-во УРАО, 1996. – 68 с.

·      Алешина И.Ф. Анализ и оценка хозяйственных решений: Методические указания к изучению курса. – М.: Изд-во РОУ, 1996. – 28 с.

Другие материалы

  • Когерентная теория истины
  • ... , должны быть определены в терминах пребывания фактическими или гипотетическими объектами полагания. Перечисленные выше различные версии когерентной теории истины можно получить в зависимости от того, каким образом понятие полагания используется для того, чтобы ограничить уместный класс утверждений, ...

  • Основы теории непустого эфира (вакуума)
  • ... экспериментальное доказательство существования как вещества, так и антивещества. Предсказаны и зарегистрированы нейтрино и антинейтрино [44]. Изложенные основы теории непустого эфира, отчетливо демонстрируют этот первый шаг самоорганизации вещества. Следующие шаги ведут к образованию более сложных ...

  • Теория предпринимательства и эволюционная экономика
  • ... равно важны как селективные преимущества, так и начальные условия развития инноваций. Теория предпринимательства и инноваций в ее современном виде является неотъемлемой составной частью эволюционной экономики. Не претендуя на полноту изложения вопроса, мы в общих чертах попытались показать, как эта ...

  • Теория Дарвина
  • ... что концепция исторического развития живой природы лучше, чем представление о неизменности видов, объясняло наблюдаемые факты. Для обоснования своей теории Дарвин в отличие от своих предшественников, привлек огромное количество доступных ему фактов из самых разных областей. Выдвижение на первый план ...

  • Психологические теории эмоций
  • ... что электрическими воздействиями на эти структуры можно управлять эмоциональными состояниями, такими, как гнев, страх. Активационная теория Линдсея - Хебба Психологическая теория эмоций (так условно можно назвать концепции Джемса - Ланге и Кеннона - Барда) получила дальнейшее развитие под влиянием ...

  • Возможность интеграции теорий на примере РЭПТ
  • ... вышесказанное не принуждает к поголовному синтетическому эклектизму, при доказанной ограниченности ортодоксальных подходов, он лишь показывает возможность на примере конкретной теории и практики возможность интеграции. Ещё одним из аспектов, который, на мой взгляд, нужно затронуть - это трудности ...

  • Теория государственного регулирования экономики Дж.М. Кейнса
  • ... рыночников стали последователями теории Кейнса. В ней была подвержена обоснованной критике идеализация классиками механизма рыночного саморегулирования, доказана необходимость активного государственного вмешательства в экономику и предложены инструменты регулирования. По Кейнсу, достижение полной ...

  • Теории международной торговли
  • ... товарами и услугами, с помощью которого страны удовлетворяют свои безграничные потребности на основе развития общественного разделения труда. Основные теории международной торговли были заложены в конце XVIII начале XIX в. выдающимися экономистами Адамом Смитом и Давидом Рикардо. А. Смит в своей ...

  • Теория относительности
  • ... СССР (1926). Родился в Германии, с 1893 жил в Швейцарии, с 1914 в Германии, в 1933 эмигрировал в США. Создал частную (1905) и общую (1907–16) теории относительности. В 1905 г. Эйнштейну было 26 лет, но его имя уже приобрело широкую известность. В 1909 г. он избран профессором Цюрихского ...

  • Теория личности
  • ... рефлексов, с одной стороны, и система внутренних факторов: самоэффективности, субъективной значимости и доступности, - с другой. Согласно поведенческой теории личности, структура личности – это сложно организованная иерархия рефлексов или социальных навыков, в которой ведущую роль играют внутренние ...

  • Теории преступности
  • ... ибо большую часть своего времени человек проводит в этих группах и в них соиализируется. Центральным понятием социально-психологических теорий преступности является социализация, целью которой служит адаптация и вживание индивида в принятые в обществе нормы поведения. Обратимся теперь к некоторым ...

  • Прагматическая теория истины
  • ... если каждый, кто имеет достаточный релевантный опыт, будет вынужден согласиться с (пропозицией) "Снег бел". Следовательно, поскольку в прагматической теории истина приравнивается к тому, по поводу чего достигнуто всеобщее согласие, это требование редуцируется к "Снег бел" ...

  • Теория истинности А.Тарского
  • ... концепция нейтральна по отношению к этим различиям[94] . Таковы наиболее важные для нас здесь аргументы теории истины Тарского. Огромно воздействие Тарского (как и других представителей Львовско-Варшавской школы) на АФ — например, на Карнапа, по его собственому признанию. В частности, Тарский ...

  • Возможна ли интегральная теория права?
  • ... , представляется, что, синтезировав ряд идей, сформулированных в русской дореволюционной философии права, можно сделать еще один шаг на пути к интегральной теории права. Примечания 1. Алексеев Н.Н. Основы философии права. СПб., 1998. С.63. 2. "Эйдетическим" ценностным значением обладает ...

  • Введение в экономическую теорию
  • ... Графическое изображение. Многие из представленных в этой книге моделей или принципов будут выражены в виде рисунков, схем,таблиц. Экономическая теория: а) дает ценные знания о социальной среде и поведении людей в этой среде; б) способствует разумному принятию фундаментальных решений; в) являясь ...

Каталог учебных материалов

Свежие работы в разделе

Наша кнопка

Разместить ссылку на наш сайт можно воспользовавшись следующим кодом:

Контакты

Если у вас возникли какие либо вопросы, обращайтесь на email администратора: admin@kazreferat.info