Тема 2.1 Линейное программирование

Линейное программирование. Основная задача линейного программирования и сведение к ней произвольной задачи линейного программирования. Алгоритм оптимизации целевой функции графическим способом. Алгоритм симплекс-метода. Понятие двойственности. Транспортная задача: постановка задачи и ее математическая модель. Построение первоначального опорного плана. Матрица затрат. Метод наименьшей стоимости. Метод северо-западного угла. Метод потенциалов. Приложение транспортной задачи к решению некоторых задач экономики и управления. Задача о назначениях.

Студент должен:

Знать:

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

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

алгоритм оптимизации целевой функции графическим способом;

алгоритм оптимизации целевой функции симплекс-методом;

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

основную теорему симплекс-метода;

способ устранения зацикливания;

принципы формулирования двойственной задачи;

общую формулировку транспортной задачи;

метод наименьшей стоимости;

метод северо-западного угла;

метод потенциалов;

области применения транспортной задачи;

Уметь:

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

осуществлять постановку основной задачи линейного программирования;

оптимизировать целевую функцию графическим способом;

оптимизировать целевую функцию симплекс-методом;

выделять базисные и свободные переменные;

составлять двойственные задачи;

решать взаимно двойственные задачи;

решать транспортные задачи методом наименьшей стоимости;

решать транспортные задачи методом северо-западного угла;

уточнять решение методом потенциалов;

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

Лабораторная работа № 1 «Оптимизация целевой функции графическим и симплексным методом» (1 ч)

Вопросы для самопроверки по теме 2.1:

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

Сформулируйте общую задачу линейного программирования.

Дайте определение плана, невырожденного и вырожденного опорного плана, оптимального плана.

Какое множество называется выпуклым? Приведите примеры выпуклых множеств.

Что называется многогранником решений?

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

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

Какие задачи линейного программирования можно решать графическим методом?

Какой метод решения систем линейных уравнений лежит в основе симплекс-метода?

Зачем в системе ограничений необходим единичный базис?

Когда оптимальный план расширенной задачи является оптимальным планом исходной задачи?

Что такое зацикливание и в какой задаче линейного программирования оно может произойти?

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

Как по решению исходной задачи найти решение двойственной?

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

Сколько положительных перевозок должен содержать невырожденный опорный план и почему?

Дайте определение системе потенциалов, расскажите, как она строится?

Для решения каких экономических задач применяется транспортная задача?