Математическое програмирование

 

Получили  новую таблицу, для которой повторяем  расчет потенциалов:

         Полагаем U₁ =0, а далее U_i + V_i = d_ij для занятых клеток таблицы.

         Проверим критерий оптимальности  : для свободных клеток.

 

         Из тех условий, где критерий  не выполняется, выбираем то  условие, где разница максимальна.  Это – ячейка (2 , 2). Перебросим в ячейку (2 ,2) 10 единиц груза из ячейки (1 , 2). 

Получили  новую таблицу, для которой повторяем  расчет потенциалов:

         Полагаем U₁ =0, а далее U_i + V_i = d_ij для занятых клеток таблицы.

 

         Проверим критерий оптимальности  : для свободных клеток.

 

         Критерий выполнен, значит, полученное  решение оптимально.

         Найдем минимальную стоимость перевозок.

Ответ:  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Задача 3

         Дана задача выпуклого программирования. Требуется:

1)     найти решение графическим методом

2)     написать функцию Лагранжа данной  задачи и найти ее седловую точку, используя решение задачи, полученное графически.

 

      Решение.

          Графическое решение задачи следующее: 

 

          Система неравенств определяет  область, ограниченную двумя прямыми  и координатными осями. График целевой функции представляет собой окружность переменного радиуса с центром в точке (5, 10). Значение целевой функции графически представляет собой квадрат радиуса этой окружности. Минимальным радиусом, удовлетворяющим системе ограничений, будет  такой радиус, который обеспечивает касание окружности с границей области так, как это показано на рисунке.

         Искомая точка определяется как  решение системы уравнений 

     

          Получили точку (3 , 8), значение целевой функции в этой точке равно

Запишем задачу в традиционном виде:

 

         Функция   называется функцией Лагранжа, а переменные  - коэффициентами Лагранжа.

         Точка  называется седловой точкой функции Лагранжа, если для любых  выполняются неравенства:

          Если функции  f, g дифференцируемы, то условия определяющие седловую точку (условия Куна-Таккера):

  

 

 

  В  данном случае получаем:

 

 

         Подставим в эти выражения  значения:

         Получаем 

        Седловая точка функции Лагранжа:

Проверим  условие cедловой точки:

          Условия выполнены, седловая точка .

Ответ:

  

  
 
 

 

Задача 4

      Для двух предприятий выделено 900 единиц денежных средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от х единиц, вложенных в первое предприятие равен , а доход от у единиц, вложенных во второе предприятие равен . Остаток средств к концу года составляет  - для первого предприятия, - для второго предприятия. Решить задачу методом динамического программирования.

      Решение.

         Процесс распределения средств разобьем на 4 этапа – по соответствующим годам.

         Обозначим - средства, которые распределяются на k–ом шаге как сумма средств по предприятиям.

         Суммарный доход от обоих предприятий  на k–ом шаге:

          Остаток средств от обоих предприятий  на k–ом шаге:

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

         Рекуррентные соотношения Беллмана  для этих функций