1. Что такое математическое программирование (мп)?

Математическое программирование, математическая дисциплина, посвященная теории и методам решения задач о нахождении

экстремумов функций на множествах, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами).

М. П. :Основные разделы содержания: Линейное программирование (постановка и решение задачи линейного программирования, анализ чувствительности, симплекс-метод, двойственная модель линейного программирования). Транспортная задача. Задача о назначениях.

2. Чем отличаются задачи линейного программирования от (злп) от общих задач мп?

Линейное программирование,математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах, задаваемых системами линейных неравенств и равенств; Л. п. является одним из разделов математического программирования. Для решения ЗЛП разработано много методов, как графических, так и численных. В MS Excel для решения линейных и целочисленных задач с ограничениями используется метод branch-and-bound (ветви и границы).

3. Приведите примеры злп.

4.Что такое каноническая форма злп?

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

5. Любую ли злп можно привести к канонической формуле?

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

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

• если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

• если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;

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

• если некоторая переменная x_j не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными: x₃ = x₃⁺ - x₃^-, где x₃⁺, x₃^- ≥ 0.

6. Какие способы решения злп Вы знаете?

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

Рассмотрим алгоритм перехода к следующим симплекс-таблицам:

1. Выбираем ключевой столбец. Это столбец соответствующий минимально отрицательному (максимально положительному) элементу последней (индексной) строке:

Если отрицательных элементов в индексной строке нет, то план оптимальный.

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

3. Выбираем ключевую строку:

Среди выбранных коэффициентов столбца, для которых абсолютная величина отношения соответствующего свободного члена к этому элементу минимальна.

Ключевой элемент - это элемент, стоящий на пересечении ключевого столбца и ключевой строки;

4. Базисная переменная из ключевой строки переводится в разряд свободных, а свободная переменная в ключевом столбце переводится в разряд базисных. Строится новая таблица;

5. В новой таблице:

5.1 Все элементы ключевой строки делятся на ключевой элемент.

5.2 Все элементы ключевого столба равны нулю, за исключением ключевого элемента.

5.3 Столбец, у которого в ключевой строке имеется ноль, в новой таблице будет таким же.

5.4 Строка, у которой в ключевом столбце имеется ноль, в новой таблице будет такой же.

5.5 В остальные клетки записывается результат преобразования элементов старой таблицы.

6. Переход к шагу 1.

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