Линейное программирование. НИЖЕГОРОДСКИЙ ИНСТИТУТ УПРАВЛЕНИЯ

НИЖЕГОРОДСКИЙ ИНСТИТУТ УПРАВЛЕНИЯ

Факультет государственного и муниципального управления

Кафедра математики и системного анализа

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

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

Направление подготовки:Государственное и муниципальное управление

Выполнил: студент Гк-722

Мемакова И. А.

Научный руководитель:

доцент, кандидат технических наук

Кошелев С. В.

Г.Нижний Новгород

Г.

Содержание

1. Теоретическая часть. 3

1.2 Линейное программирование. 3

1.2 Динамическое программирование. 5

1.3 Транспортная задача. 9

2. Практическая часть. 13

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

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

2.3 Транспортная задача. 20

Теоретическая часть

Линейное программирование

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

Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательностипеременных.

В общем виде модель записывается следующим образом:

· целевая функция:

= c1x1 + c2x2 + ... + cnxn → max(min);

(1)

· ограничения:

a11x1 + a12x2 + ... + a1nxn {≤≥}b1, a21x1 + a22x2 + ... + a2nxn {≤ = ≥} b2, ………………. am1x1 + am2x2 + ... + amnxn {≤ = ≥} bm;

(2)

· требование неотрицательности:

xj ≥ 0,

(3)

При этом a_ij, b_i, c_j ( ) - заданные постоянные величины.

Задача состоит в нахождении оптимального значения функции (1) при соблюдении ограничений (2) и (3).

Систему ограничений (2) называют функциональными ограничениями задачи, а ограничения (3) - прямыми.

Вектор , удовлетворяющий ограничениям (2) и (3), называется допустимым решением (планом) задачи линейного программирования. План , при котором функция (1) достигает своего максимального (минимального) значения, называется оптимальным.

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

Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b₁, b₂,..., b_m условных единиц.

Известны также технологические коэффициенты a_ij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида ( ).

Прибыль, получаемая предприятием при реализации изделия j-го вида, равна c_j.

В планируемом периоде значения величин a_ij, b_i и c_j остаются постоянными.

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