Ответы: Ответы на Теорию к РК-1

Теоретические вопросы к РК№1

Задача Линейного Программирования:

Определение задачи линейного программирования (ЗЛП). Допустимые и оптимальные решения (точки). Стандартная и каноническая форма ЗЛП. Переход из одного вида в другой. Базисные и свободные переменные в канонической ЗЛП. Связь между понятиями: 1) допустимое решение; 2) базисное решение; 3) допустимое базисное решение, 4) угловая (крайняя точка); 5) оптимальное решение. Способы перехода от ограничений – равенств к ограничениям – неравенствам.

Симплекс-метод:

Алгоритм симплекс-метода (перечислить основные шаги). Симплекс-таблицы. Ограничения на знаки коэффициентов в симплекс-таблице и их устранение. Опишите правила выбора генерального элемента в задаче на минимум. Укажите причины, по которым такой выбор может не произойти. Правила преобразования симплекс-таблицы, в которой уже выбран генеральный элемент. Метод искусственного базиса. Запись решения методом искусственного базиса симплекс-таблиц Исследование методом искусственного базиса задача с пустым допустимым множеством.

Двойственная Задача:

Запись двойственной ЗЛП для стандартного вида. Основные утверждения (без доказательства) для пары двойственных задач: 1)одновременная разрешимость или неразрешимость, равенство оптимальных значений; 2) Частные производные оптимума: целевой функции по правым частям ограничений, приращение целевой функции. Условия дополняющей нежесткости (УДН). Их векторно-матричная запись, скалярная запись, интерпретация в терминах «если-то». Нахождение решения двойственной задачи с помощью УДН. Основное неравенство теории двойственности (с выводом). Необходимые достаточные условия, при которых это неравенство становится равенством. Экономический смысл двойственных переменных.

Транспортная Задача:

Формальная постановка транспортной задачи (ТЗ). Число базисных и свободных переменных. Отыскание допустимого базисного решения в ТЗ. Вырожденные базисные перевозки в ТЗ и особенности работы с ними. Определение цикла пересчета. Улучшение неоптимальной перевозки с помощью перекачки по циклу. Двойственная задача к ТЗ. Проверка оптимальности решения ТЗ. Открытая модель ТЗ и ее сведение к закрытой.

Задача о Назначениях:

Формальная постановка задачи о назначениях. Связь с транспортной задачей. Алгоритм решения задачи о назначениях (на минимум). Сведение задачи о максимальном назначении к задаче на минимум.