Теория Принятия Решения

ГОСУДАРСТВЕННОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ  ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО

ОБРАЗОВАНИЯ

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ГОРНЫЙ

УНИВЕРСИТЕТ»

КАФЕДРА АСУ 
 
 
 
 
 
 
 
 

КУРСОВАЯ  РАБОТА

По дисциплине

«Теория принятия решений» 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Выполнил: ст. гр. АС-В-08

                                                                                       Мамаков С.Р.

                                                                                                 Принял: доц., к.т.н.

                                                                                     Быков А.Ю. 
 
 
 
 
 
 
 
 

Москва 2011 год 
 
 
 

ОГЛАВЛЕНИЕ:

1.      Задание на курсовую работу…………………………………………………….-3-
2.       Задача линейного программирования…………………………………………-4-
1.       Физическая интерпретация задачи……………………………………………..-4-
2.       Краткое описание метода решения……………………………………………..-4-
1.     Понятие математического программирования…………………………………-4-
2.      Понятие линейного программирования. Виды задач ЗЛП………………….....-5-
3.      Постановка ЗЛП и исследования их структуры………………………………...-6-
1. Оптимальное распределение взаимозаменяемых ресурсов……………………-7-
2. Задача о смесях……………………………………………………………………-8-
3. Задача о раскрое материала………………………………………………………-9-
4.      Форма записи ЗЛП……………………………………………………………….-10-
5.      Решение записи ЗЛП симплекс методом……………………………………….-11-
3.       Блок схема алгоритма решения задачи…………………………………………-14-
4.       Решение задачи…………………………………………………………………..-15-
3.       Задача динамического программирования…………………………………….-17-
1.      Физическая интерпретация задачи……………………………………………...-17-
2.      Понятие динамического программирования…………………………………..-17-
3.      Решение…………………………………………………………………………...-19-

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ 

5.37.  Задача  линейного программирования 

min Z=3x₁+x₂

-4x₁+x₂ ≤ 29

3x₁-x₂ ≤ 15

5x₁+x₂ ≥ 38

x_1,x₂ ≥ 0, целые. 
 
 

3.7.   Задача  динамического программирования 
 

  0          0         0        0

100       30       50      40

200       50       80      50

300       90       90     110

400      110     150    120

500      170     190    180

600      180     210    220 
 

1.17.    Решение задачи методом Гомари 

Z=4x₁+2x₂+5x₃+8x₄

x₁+2x₂+4x₃+8x₄ ≤ 24

3x₁+5x₂+x₃+      ≤ 12

6x₁+      +3x₃+x₄ ≤ 35

x_j ≥0 
 
 
 

                                                                                                         Выдал: доц., к.т.н.

                                                                                            Быков А.Ю. 

Получил: ст.гр. АС-В-08

                                                                                              Мамаков С.Р. 
 
 
 
 
 
 
 
 

ЗАДАЧА  ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. 

1.Физическая  интерпретация задачи. 
 

При производстве двух видов изделий (x₁, x₂), указаны планы производства изделий (А₁, А₂, А₃), норма затраченного и общее количество сырья. Нужно определить оптимальный план производства изделий.

Таблица 1.1

   

2.   КРАТКОЕ ОПИСАНИЕ МЕТОДА РЕШЕНИЯ 

2.1    Понятие математического программирования 
 

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

       Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.

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

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

   

     В  зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:

• Задачи линейного программирования;
• Задачи нелинейного программирования.

 

        Если целевая функция и функции ограничений – линейные функции, то

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

1.2   Понятие линейного  программирования.  Виды задач линейного  программирования 
 

     Линейное программирование (ЛП) –  один из первых и наиболее  подробно изученных разделов  математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программы) для ЭВМ» не имеет, т.к. дисциплина «линейное программирование» возникло еще до того  времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и других задач.

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

       И так, линейное программирование возникло после второй мировой войны и стало быстро развиваться, привлекая внимание математиков, экономистов, инженеров благодаря возможности широкого практического применения, а так же математической стройности.

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

       Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д..

      Задача линейного  программирования  (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.

    

  Общая форма  задачи имеет вид: найти min cx при условиях

a_λx – b_i  ≥ 0,  i ϵ I₁

     a_λx – b_i  = 0,  i ϵ I₂

     x_λ  ≥ 0,           j ϵ J₁,

где

     I₁ U I₂ = {1,…..,m}, I₁ U I₂ = Ø, J₁ ᴄ {1,……,n}, x= (x₁,….., x_n)^T,

          C= (c₁,……,c_n), a_i = (a_i1,……, a_in),  i=1,……m.

       Здесь и далее нам удобнее считать с и a_i вектор – строками, а х и

b = (b_i ,…..,b_m)^T – вектор столбцами.

       Наряду с общей формой широко  используются также каноническая  и стандартная формы. Как в  канонической так и в стандартной  форме 

                 J₁ ={1,……,n}, т.е. все переменные в любом допустимом решение задачи должны принимать неотрицательные значения (такие переменные принято называть неотрицательные в отличии от так называемых свободных переменных, на область значений которых подобные ограничение не накладывается). Отличие же между этими формами состоит в том, что в одном случае I₂ = 0, а в другом I₁ = 0.

         Задача ЛП в канонической форме:

w = cx – min                                     (2.1)

Ax = b                                               (2.2)

x ≥ 0                                                  (2.3)

     Задача ЛП в стандартной форме

w = cx – min                                    

Ax = b                                              

x ≥ 0                                             

         В обоих случаях А есть матрица размерности m х n, i-я строка которой совпадает с вектором а_i.

         Задача ЛП в общей форме  сводится (в определенном смысле) к задаче ЛП в канонической (стандартной) форме. Под этим  понимается существование общего  способа построения по исходной задаче новой задачи ЛП, любое оптимальное решение которой «легко» преобразуется в оптимальное решение исходной задачи и наоборот. (Фактически, связь между этими задачами оказывается еще более тесной). Тем самым мы получаем возможность, не теряя общности, заниматься задачами ЛП, представленных либо в канонической, либо в стандартной форме. Ввиду этого наши дальнейшие рассмотрения задач ЛП будут посвящены, главным образом, задачам в канонической форме. 
 
 
 
 
 
 
 
 
 
 
 

2.3    Постановка задач  линейного программирования  и исследование  их структуры. 

          Большинство задач, решаемых методами  исследования операций, может быть  сформулировано так:

          Максимизировать F(x₁, x₂,…. x_n) при ограничениях

          g₁(x₁, x₂,…. x_n) ≤ b₁;