Лекция № 5. Линейное программирование

Контрольные вопросы

Классы задач математического программирования

Вычислительные методы разработаны лишь для немногих типов задач нелинейного программирования, а именно для задач так называемого выпуклого программирования. Это задачи, в результате решения которых определяется минимум выпуклой (или максимум вогнутой) функции, заданной на выпуклом замкнутом множестве. В свою очередь, среди задач выпуклого программирования более подробно исследованы задачи квадратичного программирования. В результате решения таких задач требуется в общем случае найти максимум (или минимум) квадратичной функции = с ₁ x ₁ + с ₂ x ₂ + … + с_nx_n + +d ₁₁ x ₁²+…+ d ₁₂ x ₁ x ₂+… + d _{1 n} x ₁ x_n +…+ d_nnx_n ² при условии, что её переменные удовлетворяют либо некоторой системе линейных неравенств или линейных уравнений, либо некоторой системе, содержащей как линейные неравенства, так и линейные уравнения.

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

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

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

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

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

1. Вид оптимизационной задачи.

2. Математическая постановка задач оптимизации и ее интерпретация к проблемам выбора наилучших вариантов экономического поведения.

3. Условия сведения экономической задачи к задаче оптимизации.

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

5.1 Задача линейного программирования в общем виде

5.2 Варианты решения задачи линейного программирования

5.3 Области применения линейного программирования

5.4 Пример решения станковой задачи

5.5 Математическая модель задачи использования сырья

5.6 Основные понятия и теоремы линейного программирования

5.7 Нахождение решения задачи линейного программирования на основе её геометрической интерпретации