Примерный перечень вопросов к зачету  по математике для студентов 2 курса заочного факультета 1.     Общая задача математического программирования. Основные понятия и определение. ответ:

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

общая задача математического программирования формулируется следующим образом: найти экстремум целевой функции задачи Z(X) = f (x1, x2, x3,…., xn) max(min)             (6.4.13) и соответствующие ему переменные при условии, что эти переменные удовлетворяют системе ограничений (x1, x2, x3,…., xn ) =0, i=1,2,..,l                          (6.4.14) (x1, x2, x3,…., xn ) >(<) 0, i = l +1, l+2,…,m     (6.4.15) Если целевая функция (6.4.13)и система ограничений (6.4.14), (6.4.15) являются линейными, то задача математического программирования называется задачей линейного программирования,

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

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

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

− система ограничений (2.2) имеет вид системы линейных уравнений и/или неравенств.

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

Существует несколько форм записи задач линейного программирования. Рассмотрим их.

1. Общая форма записи задачи линейного программирования: необходимо найти экстремальное значение целевой функции

                                (4.1)

при ограничениях

 

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

 

Здесь (и везде далее)  заданные числа       

2. Каноническая форма записи задачи линейного программирования: необходимо найти экстремальное значение целевой функции (4.1) при ограничениях

На все неизвестные наложены условия неотрицательности:

 

                                            (4.2)

 

3. Симметричная форма записи задачи линейного программирования. Здесь принято выделять две стандартные задачи − задачу максимизации и задачу минимизации.

3.1. Стандартная задача максимизации: необходимо найти максимальное значение целевой функции (4.1) при ограничениях

и условиях неотрицательности (4.2).

3.2. Стандартная задача минимизации: необходимо найти минимальное значение целевой функции (4.1) при ограничениях

и условиях неотрицательности (4.2).

Симплексный метод

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

Основное содержание симплексного метода заключается в следующем:

1. Указать способ нахождения оптимального опорного решения

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

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

Алгоритм симплексного метода решения задач линейного программирования

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

1. Привести задачу к каноническому виду

2. Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)

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

4. Если выполняется признак единственности оптимального решения, то решение задачи заканчивается

5. Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения