Теоретический материал к заданию 1

Управление и планирование являются наиболее сложными функциями в работе предприятий, фирм, служб администраций всех уровней. Долгое время они являлись монополией человека с соответствующей подготовкой и опытом работы. Совершенствование науки, техники, разделение труда усложнили принятие решений в управлении и планировании. Для принятия обоснованного решения необходимо иметь и обработать большое количество информации, определяемое иногда астрономическими цифрами. Принятие ответственных решений, как правило, связано с большими материальными ценностями. В настоящее время недостаточно знать путь, ведущий к достижению цели. Необходимо из всех возможных путей выбрать наиболее экономичный, который наилучшим образом соответствует поставленной задаче. Появление цифровых вычислительных машин создало огромные возможности для развития науки, совершенствования методов планирования и управления производством. Однако без строгих формулировок задач, без математического описания процессов современный уровень управления и планирования не может быть достигнут.

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

Требуется найти максимум функции

f (x_1, x_2, …, x_n) (a)

при условиях

g_i (x_1, x_2, …, x_n) ≤ 0, (b)

x_j ≥ 0, i = j= (c)

где f, g_i – функции, x_1, x_2, …, x_n – параметры управления. Выражение (a) называется функцией цели. Условия (b) и (c) представляют собой ограничения поставленной задачи. Условия (c) справедливы для многих задач, особенно экономических, когда параметры управления (x_j) по своему физическому смыслу не могут быть отрицательными. Математическая дисциплина, занимающаяся изучением экстремальных (максимальных или минимальных) задач управления, планирования и разработкой методов их решения, получила название математического программирования. В зависимости от вида функции цели и ограничений математическое программирование делится на линейное и нелинейное. Наиболее разработанным разделом математического программирования является линейное программирование. Произвольную задачу линейного программирования можно определенным образом сопоставить с другой задачей линейного программирования, называемой двойственной. Первоначальная задача является исходной. Эти две задачи тесно связаны между собой и образуют единую двойственную пару.

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

1. Каждому неравенству системы ограничений исходной задачи приводим в соответствие переменную y_i;

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

3. Составляем систему ограничений. Коэффициенты системы ограничений образуют транспонированную матрицу коэффициентов системы ограничений исходной задачи. Знаки неравенств меняются еа противоположные;

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

Для решения задания 1 необходимо применить теоремы двойственности.

Первая теорем двойственности:

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

L( )_max = S( )_min

Если одна из двойственных задач неразрешима ввиду того, что L( )_max → ∞ (или S( )_min → - ∞), то другая задача не имеет допустимых решений.

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

x_{опт j} y_{опт i} - c_j = 0,

y_{опт i} x_{опт j} - b_i = 0.

Теоремы позволяют определить оптимальное решение одной из пары задач по решению другой.