Тема 2.3. Решение задач линейного программирования

Содержание вопросов

Постановка задач. Графический метод. Симплекс-таблица. Симплекс – метод. Метод искусственного базиса. Симплекс-метод при отсутствии условий неотрицательности переменных.

Вопросы и задания для самостоятельной работы:

1. Подготовить ответы на контрольные вопросы по теме 2.3.:

1.1.Определение задачи линейного программирования. Общая и каноническая форма задачи линейного программирования?

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

1.3.Первая геометрическая интерпретация задачи линейного программирования и графический метод ее решения?

1.4. Вторая геометрическая интерпретация задачи линейного программирования. Базисные решения задачи лине йного программирования?

1.5.Свойства базисных решений задачи линейного программирования?

1.6.Симплекс-метод, общая характеристика. Основные идеи и их геометрическая иллюстрация?

1.7.Критерий оптимальности допустимого базисного плана в симплекс-методе?

1.8.Правила преобразования текущего базисного плана и перехода к следующему плану в симплекс-методе?

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

1.10. Сходимость симплекс-метода. Вырожденность в задачах линейного программирования?

2. Тестовые задания для самостоятельного контроля уровня подготовки студентами вопросов темы 2.3.

2.1. Общая и каноническая форма задачи линейного программирования:

А. общий вид задачи линейного программирования;

Б. задача нахождения наибольшего значения линейной функции;

В. условия неотрицательности;

Г. каноническая форма задачи линейного программирования.

2.2.Первая геометрическая интерпретация задачи линейного программирования и графический метод ее решения:

А. представление полуплоскостей неравенствами;

Б. область допустимых планов задачи;

В. линия уровня функции;

Г. градиент функции.

2.3.Вторая геометрическая интерпретация задачи линейного программирования:

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

Б. многогранный выпуклый конус, натянутый на систему векторов в пространстве;

В. коэффициенты разложения вектора ограничений задачи по векторам требований;

Г. геометрическая интерпретация канонической задачи линейного программирования.

2.4. Базисные решения задачи линейного программирования:

А. несовместность системы уравнений;

Б. базис в пространстве;

В. базисный допустимый план;

Г. базисный план задачи.

2.5. Свойства базисных решений задачи линейного программирования:

А. каждый допустимый базисный план является угловой точкой множества допустимых планов;

Б. угловая точка множества;

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

Г. процедура перехода от одной угловой точки к другой.

2.6. Симплекс-метод, общая характеристика:

А. поиск решения сводится к последовательному перебору угловых точек множества допустимых планов (или базисных планов);

Б. метод последовательного улучшения плана;

В. улучшение значения целевой функции;

Г. расширенные векторы условий и ограничений.

2.7. Основные идеи симплекс-метода и их геометрическая интерпретация:

А. геометрически определение вектора означает, что он принадлежит конусу, натянутому на расширенные векторы, а расширенный вектор ограничений служит его проекцией;

Б. нулевая координата вектора равна значению целевой функции выбранного базисного плана;

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

Г. геометрическая интерпретация классической задачи линейного программирования иллюстрирует общую идею критерия, используемого в симплекс-методе для определения оптимальности (или неоптимальности) текущего плана.

2.8. Критерий оптимальности допустимого базисного плана в симплекс-методе:

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

Б. в техническом плане симплекс-метод представляет собой некоторый итеративный вычислительный процесс;

В. текущий базисный план;

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

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

А. схема алгоритма симплекс-метода применительно к решению линейной задачи максимизации;

Б. 0-й этап: нахождение допустимого базисного плана;

В. 1-й этап: стандартная итерация алгоритма;

Г. проверка оптимальности текущего базисного плана: осуществляется просмотр строки оценок.

2.10. Сходимость симплекс-метода. Вырожденность в задачах линейного программирования:

А. сходимость-обязательное свойство любого вычислительного алгоритма;

Б. допустимый базисный план канонической задачи линейного программирования, соответствующий базису, называется вырожденным, если;

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

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