Прикладная математика. 3

Федеральное агентство по образованию 

Государственное образовательное учреждение

высшего профессионального образования

«Государственный  Университет Управления» 
 
 

Институт  информационных систем управления

Кафедра прикладной математики 
 
 
 
 

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

по учебной  дисциплине «Прикладная математика» 
 
 
 
 
 
 

Вариант №11

Исполнитель:

студентка Ибрагимова А.В.   группы Антикризисное управление 2-1 подпись  _________ 

Руководитель  курсовой работы: к.т.н., доцент Бодров А.П. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Москва 2011 
Содержание

     1. Линейная производственная задача . . . . . . . . . . . . . . . . . . . . . . . . . . 3

     2. Двойственная задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

     3. Задача «о расшивке узких мест производства» . . . . . . . . . . . . . . . . . 9

     4. Транспортная задача линейного  программирования . . . . . . . . . . . . .12

     5. Динамическое программирование. Задача оптимальных значений инвестиций. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

     6. Динамическая задача управления  производством и запасами . . . . .18

     7. Матричная модель производственной  программы предприятия . . . 21

     8. Матричная игра как модель  конкуренции и сотрудничества . . . . . . 22 
 
 

     1. Линейная производственная  задача

     Технологическая матрица А затрат ресурсов на единицу продукции каждого вида:

     Вектор  В объемов ресурсов:

     Вектор  С удельной прибыли:

     Задача  состоит в том, чтобы найти  производственную программу, максимизирующую  прибыль:

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

     Заменяем  неравенства уравнениями при  помощи дополнительных неотрицательных  переменных x₅, x₆, x₇ (балансовые переменные, которые показывают остатки ресурсов). Получаем линейную производственную задачу в каноническом виде:

     Для решения задачи воспользуемся симплексным  методом. Решение приведено в  таблицах:

      , следовательно, 6 – разрешающий элемент.

     х₁ - в базис, х₆ – исключаем из базиса.

      , следовательно, 5 – разрешающий  элемент. 

     x₂ - в базис, х₅ – исключаем из базиса.

     Оптимальное решение получено, так как все оценочные коэффициенты (0, 0, 4, 8, 6, 2, 0) неотрицательны.

     Оптимальное решение: x₁ = 25, х₂ = 16, х₇ = 28, наибольшая прибыль P_max = 1380. Первый и второй ресурс использованы полностью, так как их остатки равны нулю (x₅ = x₆ = 0 – узкие места производства), а остаток у третьего ресурса равен 28 (x₇ = 28).  

     2. Двойственная задача

     Технологическая матрица А затрат ресурсов на единицу  продукции, вектор В объемов ресурсов, вектор С удельной прибыли:

     y₁, y₂, y₃ – двойственные (расчетные) переменные.

     Для производства единицы продукции  первого вида нужно затратить 4 единицы  ресурса первого вида и 6 – второго. В ценах y₁, y₂, y₃ затраты составят 4y₁ + 6y₂. За единицу первой продукции прибыль составляет 36:

     Для производства единицы продукции  второго вида нужно затратить 5 единиц ресурса первого вида и 7 – третьего. В ценах y₁, y₂, y₃ затраты составят 5y₁ + 7y₃. За единицу второй продукции прибыль составляет 30:

     Для производства единицы продукции  третьего вида нужно затратить 2 единицы  ресурса первого вида, 4 – второго, 6 – третьего. В ценах y₁, y₂, y₃ затраты составят 2y₁ + 4y₂ + 6y₃. За единицу третьей продукции прибыль составляет 16:

     Для производства единицы продукции  четвертого вида нужно затратить 3 единицы  ресурса первого вида, 1 – второго, 5 – третьего. В ценах y₁, y₂, y₃ затраты составят 3y₁ + 1y₂ + 5y₃. За единицу четвертой продукции прибыль составляет 12:

     Таким образом, нужно найти вектор двойственных оценок Y = (y₁, y₂, y₃) минимизирующий общую оценку всех ресурсов:

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

     Оценки  ресурсов не могут быть отрицательны:

     Решение задачи можно найти с помощью  второй основной теоремы двойственности: для оптимальности допустимых решений  X = (x₁, x₂, x₃, x₄) и Y = (y₁, y₂, y₃) пары двойственных задач необходимо и достаточно выполнение условий:

     Ранее было найдено, что в решении этой задачи x₁>0, x₂>0, поэтому:

     Если  учесть, что третий ресурс был избыточным (так как x₇ = 28), то y₃ = 0, то получаем систему уравнений:

     Получаем, что y₁ = 6, y₂ = 2.

     Двойственные  оценки ресурсов:

     Y_опт = (6, 2, 0).

     Общая (минимальная) оценка всех ресурсов равна:

     F_min = 180*6 + 150*2 + 140*0 = 1380.

     Y_опт = (6, 2, 0) – это три последних компоненты последней строки симплексной таблицы решения исходной задачи. 

     3. Расшивка узких  мест производства

     Первый  и второй ресурсы использованы полностью, следовательно, они образуют «узкие места производства».

     Пусть вектор T=(t₁, t₂, t₃) – вектор дополнительных объемов ресурсов. Должно выполняться условие:

     H + Q^-1T ≥0

     Задача  состоит в том, чтобы найти  вектор

     T = (t₁, t₂, 0),

     максимизирующий суммарный прирост прибыли 

     W = 6t₁ + 2t₂ —> max

     при условии сохранения двойственных оценок ресурсов

      ,

     Предполагая, что можно надеяться получить дополнительно не более 1/3 первоначального объема ресурса каждого вида:

      , причем t₁≥0, t₂≥0.

     Переписав неравенства в виде:

     приходим  к задаче ЛП. Задача решается графически:

      Решению соответствует точка А (160/3, 50). 

     Программа «расшивки» имеет вид:

     T_опт = (160/3; 50; 0), W_max = 6*160/3 + 2*50= 420.

     и прирост прибыли – 420.

     Сводка  результатов приведена в следующей  таблице:

     4. Транспортная задача  линейного программирования

     Исходные  данные задачи имеют вид:

     A = (a₁, a₂, a₃) = (58, 40, 45). B = (b₁, b₂, b₃, b₄) = (42, 35, 27, 28).

     Общий объем производства больше, чем требуется всем производителям , т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 143 – 132 = 11 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

     Первое  базисное допустимое решение строим по правилу «северо-западного угла», которое состоит в том, чтобы  на каждом этапе мы максимально загружаем  «северо-западную клеточку»:

     Обозначим через

     вектор  симплексных множителей или потенциалов. Тогда

     откуда  следует

     Один  из потенциалов можно выбрать  произвольно, так как в системе  одно уравнение линейно зависит  от остальных. Положим, что p₁=0. Остальные потенциалы в силу основной теоремы двойственности находим из условия, что для базисных клеток ∆_ij=0. Получаем:

     Вычисляем оценки всех свободных клеток:

     Находим наибольшую положительную оценку:

     Для найденной свободной клетки 14 строим цикл пересчета – замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные – в занятых. Это будет 14-12-22-23-33-34. Производим перераспределение поставок вдоль цикла пересчета, максимально загружая 14 клетку.

     P_max=16 
 
 
 
 
 
 
 
 

     Получаем  второе базисное решение

     Находим новые потенциалы, новые оценки.

     В силу второй основной теоремы двойственности все ∆_ij≤0, . Это допустимое решение и будет являться базисным.

     5. Динамическое программирование. Задача оптимальных значений инвестиций

     Есть  четыре банка (n=4). Общая сумма инвестиций равна 700 тыс руб (b=700), выделяемые банкам суммы кратны 100 тыс руб. Значения функций f_j(x_j) приведены в таблице:

     Заполняя  таблицу, f₂(x₂) складываем со значениями F₁(ξ-x₂)=f₁(ξ-x₂) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение .

     Продолжая процесс, табулируем функции F₃(ξ), .