5. Геометрический смысл симплекс-метода решения задач линейного программирования. Построение начального опорного плана.

Симплекс-метод включает два этапа:

1) определение начального решения, удовлетворяющего ограничениям задачи;

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

6. Симплекс-метод. Критерий оптимальности опорного плана.

Для проверки решения на оптимальность просматривается последняя f- строка.

1) Если коэффициенты, стоящие при свободных переменных, неотрицательны, то полученное решение оптимально. Полученное решение единственно, если все эти коэффициенты положительны.

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

3) Если в последней строке есть хотя бы один отрицательный коэффициент, а в соответствующем этому коэффициенту столбце нет ни одного положительного элемента, то целевая функция f не ограничена на области допустимых решений.

4) Если хотя бы один из коэффициентов, стоящих при свободных переменных, отрицательный и в соответствующем ему столбце есть хотя бы один положительный элемент, то полученное решение может быть улучшено.

7. Симплекс-метод. Правило перехода к новому опорному плану.

8. Симплекс-таблица. Пересчет симплекс-таблиц. Алгоритм симплекс-метода решения задач линейного программирования.

Шаг 1. Получение начального решения.

Шаг 2. Выражение функции f только через свободные переменные.

Шаг 3. Проверка решения на оптимальность.

Шаг 4. Получение нового решения.

4.1. Выбор переменной, вводимой в список базисных переменных.

4.2. Выбор переменной, выводимой из списка базисных переменных.

4.3. Выполнение симплекс-преобразования и переход к новой симплекс-таблице.

9. Метод искусственного базиса.

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

На I этапе вводятся искусственные переменные, необходимые для получения начального базиса. Записывается новая целевая функция, предусматривающая минимизацию суммы искусственных переменных при исходных ограничениях. Если минимальное значение новой целевой функции равно 0 (т.е. искусственные переменные исключены из базиса), то задача имеет допустимое решение: оптимальное решение, полученное на этапе I, используется в качестве начального решения исходной задачи (этап II). В противном случае (если не удалось вывести из базиса искусственные переменные), задача не имеет допустимого решения.

10. Экономическая интерпретация двойственных задач планирования производства.

Поясним экономический смысл двойственной модели.

Пусть в качестве управляющих переменных , , исходной модели рассматривается число изделий, производимых некоторым предприятием, а параметров - количество ресурсов, используемых для изготовления изделий. Через обозначено количество ресурсов i-того типа, идущее на изготовление одного изделия j- того вида, _j - прибыль от реализации одного изделия j- того вида. Тогда исходная модель соответствует задаче определения оптимального плана производства продукции, обеспечивающего максимальную прибыль.

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

j =1,…,m. Цены на ресурсы должны удовлетворять следующим двум условиям: во-первых, они не должны быть слишком высокими, иначе ресурсы невозможно будет продать; а во-вторых, цены на ресурсы должны быть такими, чтобы прибыль от их реализации была больше прибыли от реализации готовой продукции. Первое условие выражается формулой , второе условие – ограничениями

В левой части каждого из неравенств стоит прибыль от продажи ресурсов всех типов, идущих на изготовление j- того изделия, в правой части – прибыль от продажи j- того изделия ( ).

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

Значения переменных часто называют теневыми ценами.