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

Основные понятия исследования операций. Основные понятия задач и методов математического программирования. Постановка задачи линейного программирования. Виды задач линейного программирования. Линейное и целочисленное программирование.Графическая интерпретация двумерной задачи линейного программирования. Теория двойственности в анализе оптимальных решений экономических задач. Постановка и различные формы записи задач линейного программирования. Стандартная и каноническая формы представления. Симплекс-метод и симплексные таблицы. Экономическая интерпретация элементов таблицы. Двойственные задачи и методы, их интерпретация. Экономическая и математическая формулировки транспортной задачи. Правила построения цепей. Смысл потенциалов, метод потенциалов. Основные способы построения начального опорного решения. Транспортные задачи с нарушенным балансом производства и потребления.

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

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

1. Приведите примеры задач линейного программирования.

2. Чем выделяется задача целочисленного программирования?

3. Как построить многоугольник решений?

4. Что называется нулевой линией уровня целевой функции?

5. Как получить каноническую форму записи задачи линейного программ-мирования?

6. Как заполняется симплекс-таблица?

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

8. Сформулируйте критерий оптимальности допустимого решения.

9. Как составить двойственную задачу к данной задаче линейного программирования?

10. Как выписать решение основной задачи, опираясь на решение двойственной задачи?

Тема 5. Нелинейное программирование

Выпуклые множества и их свойства. Угловые точки. Выпуклые и вогнутые функции. Основная задача выпуклого программирования. Условия Куна-Таккера в градиентной форме. Необходимый признак локального максимума для задач с выпуклыми ограничениями. Достаточный признак для задач выпуклого программирования. Усиленные условия Куна-Таккера.

Основные термины: множество, выпуклое множество, выпуклая функция, вогнутая функция, угловые точки.

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

1. Дайте понятие выпуклого множества.

2. Приведите примеры выпуклых и невыпуклых множеств.

3. Дайте понятия выпуклой и вогнутой функций.

4. Приведите примеры выпуклых и вогнутых функций.

ПЛАНЫ ПРАКТИЧЕСКИХ ЗАНЯТИЙ