Курсовая работа по "Теории принятия решений"

Автор работы: Пользователь скрыл имя, 20 Января 2014 в 23:42, курсовая работа

Описание работы

Для изготовления бетона трех марок, предприятие использует четыре вида сырья. Запасы сырья известны и равны 6, 8, 1, 2 тонн. Количество сырья каждого вида, необходимое для производства единицы бетона первой марки соответственно равны: 1, 2, -1, 0. Для бетона второго вида: 2, 1, 1, 1. Для бетона третьего вида: 1,3/4, -1, 0. Отрицательные значения сырья свидетельствуют об отрицательном его воздействии на марку бетона. Прибыль от реализации бетона первого вида составляет 3 у.е., от бетона второго вида 2 у.е., третьего 2 у.е. Составить план, обеспечивающий наибольшую прибыль производству.

Содержание работы

Задание на курсовую работу 2
Решение задачи линейного программирования симплекс методом 4
Физическая интерпретация задачи 4
Краткое описание метода решения задачи 4
Блок-схема решения ЗЛП симплекс-методом 6
Аналитическое решение задачи 7
Транспортная задача 9
Физическая интерпретация задачи 9
Краткое описание метода решения задачи 9
Блок-схема решения транспортной задачи 11
Аналитическое решение задачи 12
Статистические игры (игры с природой) 18
Физическая интерпретация задачи 18
Краткие теоретические сведения 18
Блок-схема алгоритма решения задачи 19
Аналитическое решение задачи 20
Список использованной литературы 24

Файлы: 1 файл

курсачТПР - копия.docx

— 275.21 Кб (Скачать файл)
  1. - для всех базисных клеток
  2. - для всех свободных клеток

План  обладает свойством, называющимся потенциальным, а соответствующие ему платежи  - потенциалами пунктов Ai и Bj соответственно. Тогда всякий потенциальный план является оптимальным. Для решения транспортной задачи необходимо построить потенциальный план. При улучшении плана необходимо основываться на следующем свойстве платежей и псевдостоимостей: какова бы ни была система платежей , удовлетворяющая условию , для каждой свободной клетки цена цикла пересчета в данной клетке.

 

 

Блок-схема решения транспортной задачи

 

Рис. 2. Блок-схема алгоритма решения задачи

Аналитическое решение задачи

Для разрешимости транспортной задачи необходимо, чтобы суммарные запасы продукции у поставщиков равнялись  суммарной потребности потребителей. Проверим это условие. В нашем случае, потребность всех потребителей - 280 единиц продукции равна запасам всех поставщиков.

Математическая модель транспортной задачи:

F = ∑∑cijxij,

при условиях:

∑xij = ai, i = 1,2,…, m,

∑xij = bj, j = 1,2,…, n,

Стоимость доставки единицы груза  из каждого пункта отправления в  соответствующие пункты назначения задана матрицей тарифов, данные которой занесем в таблицу 1.

Таблица 1

Поставщик

Потребитель

Запас

B1

B2

B3

А1

1

2

2

50

А2

4

5

7

100

А3

6

2

4

130

Потребность

70

100

110

-


 

  1. Поиск первого опорного плана.

Используя метод минимального элемента, построим первый опорный план транспортной задачи, для этого составим таблицу (тарифы cij располагаются в нижнем правом углу ячейки).

Минимальный элемент матрицы тарифов  находится в ячейке A1B1 и равен 1, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A1 к потребителю B1 наиболее рентабельный. Запасы поставщика A1 составляют 50 единиц продукции. Потребность потребителя B1 составляет 70 единиц продукции. От поставщика A1 к потребителю B1 будем доставлять min = { 50 , 70 } = 50 единиц продукции. Разместим в ячейку A1B1 значение равное 50. Мы полностью израсходoвали запасы поставщика A1. Вычеркиваем строку 1 таблицы, т.е исключаем ее из дальнейшего рассмотрения (Таблица 2).

Минимальный элемент матрицы тарифов находится  в ячейке A3B2 и равен 2, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A3 к потребителю B2 наиболее рентабельный. Запасы поставщика A3 составляют 130 единиц продукции. Потребность потребителя B2 составляет 100 единиц продукции. От поставщика A3 к потребителю B2 будем доставлять min = { 130 , 100 } = 100 единиц продукции. Разместим в ячейку A3B2 значение равное 100. Мы полностью удовлетворили потребность потребителя B2. Вычеркиваем столбец 2 таблицы, т.е исключаем его из дальнейшего рассмотрения (Таблица 2).

Продолжая вычисления, получаем первый опорный план (Таблица 3).

Таблица 2

Поставщик

Потребитель

Запас

B1

B2

B3

А1

50 1

- 3

- 2

50

А2

- 4

- 5

- 7

100

А3

- 6

100 2

- 4

130

Потребность

70

100

110

-


 

Таблица 3

Поставщик

Потребитель

Запас

B1

B2

B3

А1

 50 1

   -   3

  -   2

50

А2

 20 4

   -   5

80 7

100

А3

   -  6

 100 2

 30 4

130

Потребность

70

100

110

-


Заполненные нами ячейки будем называть базисными, остальные - свободными. Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.  Количество базисных ячеек (задействованных маршрутов) равно 5, что и требовалось.

Мы нашли  начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

Значение  целевой функции для этого  опорного плана равно:

S0 = 1 * 50 + 4 * 20 + 7 * 80 + 2 * 100 + 4 * 30 = 1010 ден. ед.

Общие затраты на доставку всей продукции, для начального решения, составляют 1010 ден. ед.

  1. Оценка полученного решения.

Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика. Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя. Для базисной ячейки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.

ui + vj = cij, где cij - тариф клетки AiBj

Поскольку, число базисных клеток - 5, а общее количество потенциалов  равно 6, то для однозначного определения  потенциалов, значение одного из них  можно выбрать произвольно.

Примем v= 0.

v+ u= c23,     v+ u= 7,    u= 7 - 0 = 7

v+ u= c33,      v+ u= 4,     u= 4 - 0 = 4

v+ u= c21,      v+ u= 4,     v= 4 - 7 = -3

v+ u= c32,      v+ u= 2,     v= 2 - 4 = -2

v+ u= c11 ,         v+ u= 1,       u= 1- (-3) = 4


 

Таблица 4

Поставщик

Потребитель

Uj

B1

B2

B3

А1

        50         1

          -          3

         -         2

u1 = 4

А2

         20         4

          -          5

        80        7

u2 = 7

А3

          -        6

        100       2

        30        4

u3 = 4

Vi

v1 = -3

v2 = -2

v3 = 0

-


 

Найдем  оценки свободных ячеек следующим  образом (в таблице 5 они располагаются  в нижнем левом углу ячейки):

12 = c12 - ( u+ v) = 3 - ( 4 + ( -2 )) = 1,


13 = c13 - ( u+ v) = 2 - ( 4 + 0 ) = -2,


22 = c22 - ( u+ v) = 5 - ( 7 + ( -2 )) = 0,


31 = c31 - ( u+ v) = 6 - ( 4 + ( -3 )) = 5.


 

Таблица 5

Поставщик

Потребитель

Uj

B1

B2

B3

А1

50 1

1     -        3

-2          -        2

u1 = 4

А2

20 4

0           -         5

         80       7

u2 = 7

А3

5          -         6

        100      2

         30       4

u3 = 4

Vi

v1 = -3

v2 = -2

v3 = 0

-


 

Оценка  свободной ячейки A1B3 (незадействованного маршрута) отрицательная ( 13 = -2), следовательно, решение не является оптимальным.

Построим  цикл для выбранной ячейки A1B3. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения.

Ячейки, образующие цикл для свободной ячейки A1B3:

A1B3, A1B1, A2B1, A2B3

Пусть ячейка A1B3, для которой мы строили цикл, имеет порядковый номер один (Таблица 6).

Среди ячеек  цикла A1B1 , A2B3 , номера которых четные, найдем ячейку, обладающую наименьшим значением.

min = {50, 80} = 50

В данном случае, это ячейка A1B1.

Другими словами, из маршрутов доставки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика A1 к потребителю B1, по которому доставляется меньше всего (50) единиц продукции. Данный маршрут мы исключим из схемы доставки продукции.

 

Таблица 6

Поставщик

Потребитель

Запас

B1

B2

B3

А1

         50        1

1       -        3

-2          -         2

50

А2

          20        4

0           -         5

         80       7

100

А3

5          -         6

       100      2

         30       4

130

Потребность

70

100

110

-


 

От ячеек  цикла с четными номерами отнимает 50. К ячейкам с нечетными номерами прибавляем 50.

Мы вводим новый маршрут доставки продукции  от поставщика A1 к потребителю B3. По данному маршруту доставим 50 единиц продукции, по цене доставки 2 за единицу продукции. Общие затраты увеличатся на 2 * 50 ден. ед.

По маршруту от поставщика A1 к потребителю B1 мы полностью перестаем доставлять продукцию. Общие затраты уменьшатся на 1 * 50 ден. ед. От поставщика A2 к потребителю B1 дополнительно поставим 50 единиц продукции, по цене доставки 4 за единицу продукции. Общие затраты увеличатся на 4 * 50 ден. ед. Сократим поставку от поставщика A2 к потребителю B3 на 50 единиц продукции, по цене доставки 7 за единицу продукции. Общие затраты уменьшатся на 7 * 50 ден. ед.

Данные  преобразования не изменят баланс между  поставщиками и потребителями. Все  поставщики израсходуют все свои запасы, а все потребители получат  необходимое им количество продукции.

 

Таблица 7

Поставщик

Потребитель

Запас

B1

B2

B3

А1

        50-50     1

1       -        3

-2          +50        2

50

А2

       20+50    4

0           -         5

       80-50    7

100

А3

5          -         6

       100      2

          30       4

130

Потребность

70

100

110

-

Информация о работе Курсовая работа по "Теории принятия решений"