2. Задачи линейного программирования

Задачи линейного программирования (ЛП). Относятся к типу специальных неклассических задач МП (такие задачи, для которых в силу каких-то специфических особенностей их критериальных функций и функциональных ограничений разработаны специальные методы решения). Они характеризуются тем, что функции F (X) и g_i (X) являются линейными по X.

Общая постановка задачи ЛП может быть представлена в следующем виде:

(3.13)

где b_i, c_j, a_ij – заданные постоянные величины.

Все остальные задачи МП, не сводимые к постановке являются нелинейными задачами МП.

Для решения задач ЛП используется симплекс-метод, позволяющий получить точное решение задачи за конечное количество шагов.

Однако следует иметь в виду, что линейное, а тем более детерминированное, описание ЗПР обычно представляет собой довольно грубое приближение реальной задачи; более детальный анализ задачи часто позволяет обнаружить нелинейные и стохастические явления.

Билет №3

1. Типы модельных связей. Классификация задач принятия решений в зависимости от типа модельной связи.

Механизм ситуации – совокупность условий, которая влияет на проблему. В теории принятия решений в механизме ситуации бывает 2 типа:

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

2. Многозначные – такие связи между способом и исходом операции, в рамках которых при многократном воспроизведении одной и той же альтернативы возможно появления разных исходов (рисковые ситуации или условия неопределенности).

При этом степени возможности появления тех или иных исходов и результатов вполне соизмеримы (т. е нельзя считать один исход менее вероятным по сравнению с другим).

2. Симплекс-метод: суть метода, табличный алгоритм.

Суть – базисную и свободную переменную. Алгоритм:

1) приводим задачу к каноническому виду (т.е. избавляемся от неравенств, добавляя базовые переменные y1 y2) 2)выражаем базисные переменные через свободные переменные и свободные члены 3) строим симплекс-таблицу: в левый верхний угол каждой ячейки записывается коэффициент, который стоит в соответствующей строке системы при соответствующей переменной. 4) пересчет коэффициентов. Для начала выбираем разрешающий столбец- по строке выбирается наибольшее по модулю число Разрешающая строка – свободный член разделить на элемент этой же строки в разрешающем столбце, взятый с обратным знаком. Из полученных отношений выбираем минимальное. На пересечении разрешающего столбца и разрешающей строки – разрешающий элемент. Правила расчета коэффициентов: 1. В правый нижний угол ячейки с разрешающим элементом записываем число, обратное разрешающему элементу. 2. В правые нижние углы разрешающего столбца записывается результат от деления элементов ячейки на разрешающий элемент. 3. В правые нижние углы остальных ячеек разрешающей строки записывается результат от деления элементов на разрешающий элемент, взятый с обратным знаком. 4. В правые нижние углы остальных ячеек записываются результаты от вычисления: элемент ячейки – (соответствующий элемент разрешающего столбца*на соответствующий элемент разрешающей строки /на разрешающий элемент). Трактовка результатов: показатели правых нижних углов в строке функции в столбцах переменных должны быть неположительными – задача решена. Если нет, то еще раз итерация. Правый нижний угол в строке функции в столбце свободных членов – максимум прибыли. Количество продукции – в правом нижнем углу разрешающей строки.

Билет №4