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

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

Предположим, что в трех цехах (Ц1, Ц2, ЦЗ) изготавливается два вида изделий И1 и И2. Известна загрузка каждого цеха а_i (оцениваемая в данном случае в процентах) при изготовлении каждого из изделий и прибыль (или цена, объем реализуемой продукции в рублях) с_i от реализации изделий. Требуется определить, сколько изделий каждого вида следует производить при возможно более полной загрузке цехов, чтобы получить за рассматриваемый плановый период максимальную прибыль или максимальный объем реализуемой продукции.

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

(1)

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

5 х₁ + 4х₂≤ 100;

1.6 х₁+ 6.4 х₂ ≤ 100; (2)

2.9 х₁ + 5.8 х₂ ≤ 100.

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

Графическое решение задачи приведено на рисунке 11.1.

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

Существует два крайних положения линии уровня, когда она «касается» допустимого множества. Этим двум положениям в данном случае соответствуют две точки «касания» -начало координат (0, 0) и точка (9, 13). Первая из этих точек - точка минимума, а вторая - максимума данной функции F вида (1) на допустимом множестве (2).

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

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

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

Целевая функция вида:

и ограничения

,

Переобозначим свободные коэффициенты ограничений a_j0=b_j. Приведем матрицу ограничений к каноническому виду:

Используя метод Жордана-Гаусса, приведем записанную систему к виду, где выделены базисные переменные. Введем условные обозначения:

x₁, x₂ , ... , x_r - базисные переменные;

x_r+1, x_r+2 , ... , x_n - свободные переменные.

; . (2.41)

По последней системе ограничений и целевой функции построим симплекс-таблицу. 

Таблица 2.3

Симплекс-таблица

Все дальнейшие преобразования связаны с изменением содержания этой таблицы.

Нижняя строка элементов а_ок, называется индексной. Элементы индексной строки вычисляются следующим образом:

означает номер соответствующей строки.

Поскольку на первом шаге заполнения таблицы все элементы с_n+I равны нулю, то элементам индексной строки присваиваются значения со­ответствующих элементов целевой функции данного столбца, взятые с обратным знаком, т.е. а_0k= -С_к. Последняя строка таблицы служит для определения направляющего столбца.

Элемент а₀₀ равен значению целевой функции, которое вычисляется по формуле , к - номер базисной переменной (индексация идет по строкам таблицы).

В столбце В_х записываются базисные переменные, на первом шаге в качестве базисных выбирают фиктивные переменные {х_п+к }, . В дальнейшем фиктивные переменные необходимо вывести из базиса.

В столбец С записываются коэффициенты при х_п+к, на первом шаге значения этих коэффициентов равны нулю.

Для перехода от базиса фиктивных переменных к базису реальных переменных применяют следующие правила:

* в качестве направляющего столбца выбирают столбец А_j , для которого выполняется условие a_0j = min{a_ol), при а_0l < 0, т.е. выбирается минимальный элемент, при условии, что этот элемент отрицательный;

* выбирают направляющую строку, для чего каждый элемент столбца свободных членов делится на соответствующий элемент направляющего столбца, элемент столбца свободных членов находится в одной строке с элементом направляющего столбца -. Из всех возможных соотношений выбирается минимальное при условии, что a_rj > 0, 1 ≤ r ≤ т.

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

Переменная, которая соответствует направляющему столбцу, вводится в базис, а переменная, соответствующая направляющей строке, выводится из базиса. При этом для переменной, вводимой в базис, изменяется соответствующее значение коэффициента целевой функции. Вместо коэффициента с_n+i соответствующего старой базисной переменной, в таблице записывается значение коэффициента целевой функции при переменной, вводимой в базис.

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

1. Для всех элементов направляющей строки

где к - номер шага (к = 1, 2,...); i - номер направляющей строки; j - номер направляющего столбца; , т.е. все элементы направляющей строки делим на направляющий элемент, в итоге направляющий элемент стал равным единице; .

2. В направляющем столбце необходимо получить , для всех , r≠i, при , т.е. в направляющем столбце должны быть все нули кроме направляющего элемента, который равен единице.

Для всех остальных элементов, включая индексную строку, производим вычисления

Симплексные преобразования повторяют до тех пор, пока не реализуется один из двух возможных исходов:

а) все a_0l ≥0 - это условие оптимальности базиса последней таблицы;

б) найдется такой элемент a_0l< 0, при котором все элементы столбца а_rj ≤ 0, - это признак неограниченности целевой функции на множестве допустимых решений.