Выпуск продукта

Y в неделю

Выпуск деталей типа X в неделю

Рис. 12.23. Задача линейного программирования для объемов выпуска продуктов X и У в неделю

Точка с координатами х = 0, у = 15 также принадлежит этой прямой. Линия уровня изображена на приведенном выше графике пунктиром. Если осуществлять перемещение линии у ровня'параллельно ее начальному положению (отмеченному пунктиром), то легко можно убедиться, что оптимум находится в крайней точке А. Эта точка лежит на пересечении линий ограничений RM1 и RM3. Решение системы этих уравнений дает следующие результаты:

3 х = 27, следовательно, х = 9.

Подставив это значение во второе уравнение системы, получим:

х + у = 20, следовательно, у = 11.

Оптимальным ассортиментным набором является производство 9 единиц про­дукта X и 11 единиц продукта Y в неделю. Таким образом, максимальная прибыль, получаемая за неделю, составит:

Р _тах = 2 х 9 + 11 = 29 ф. ст. в неделю.

Сырье типа 1 и 3 используется полностью, однако существует свободный запас сырья типа 2, т.е.

2 х 11 + s₂ = 30,

следовательно, s₂= 8 кг в неделю.

Гл. 12. Линейное программирование

Решение Симплекс-метод. Представим коэффициенты, стоящие в левой части системы ограничений, в матричной форме. За обозначения столбцов примем переменные которым они соответствуют. Значения правой части ограничений запишем в отдельном столбце матрицы справа. За обозначения строк примем обозначения соответствующих переменных, которые являются базисными (имеющими ненулевые значения) переменными в начальной крайней точке (начале координат). Наконец введем в таблицу дополнительную строку, соответствующую коэффициентам целевой функции у. Существует несколько немного отличных друг от друга вариантов решения задачи симплекс-методом. В том из них, который излагается ниже требуется вводить коэффициенты целевой функции с отрицательным знаком. Полученная в результате применения данной процедуры матрица называется симплекс-таблицей, а сама эта процедура представляет собой Шаг 1 в алгоритме симплекс-метода.

Таблица 12.2. Первая симплекс-таблица

Базисные переменные	Переменные х У S, S2 S3	Правая часть
Si s2 S3	3 0 10 0 0 2 0 10 110 0 1	27 30 20
Целевая функция, Р	-2 -10 0 0	•

Шаг 2. В строке коэффициентов целевой функции найдем наибольшее отрица­тельное значение (- 2). Столбец, соответствующий этому значению, называется ведущим. Разделим значения правой части на соответствующие значения ведущего столбца. В результате получим ряд отношений.

Таблица 12.3. Первая симплекс-таблица с учетом отношения

Базисные переменные	Переменные х у s, s2 s3	Правая часть Ь	Отношения Ь/элемент ведущего столбца
S2 S.1	3» 0 1 0 0 0 2 0 10 110 0 1	27 30 20	27/3=9 «- ведущая строка 30/0 = оо 20/1 = 20 ______________________.
Целевая функция Р	-2-10 0 0

т

Ведущий столбец х

Шаг 3. Выберем среди полученных отношений наименьшее положительное отношение. В нашем случае.оно равно 9. Соответствующая ему строка s, является

д 34 Ч. 4. Моделирование в бизнесе

ведущей. Пересечение ведущего столбца и ведущей строки дает ведущий элемент 3 в приведенной выше табл. 12.3 он отмечен знаком "*".

Шаг 4. Разделим все элементы ведущей строки на ведущий элемент 3. Заменим все элементы ведущей строки на полученные новые значения (табл. 12.4). Обозначение ведущей строки s, заменим на обозначение ведущего столбца х. Новые переменные, соответствующие обозначениям строк, — это базисные пере­менные второго базисного решения.

Таблица 12.4. Вторая симплекс-таблица

Базисные переменные	Переменные х У s, s2 s3	Правая часть Ь
X S2 S3	1 0 1/3 0 0 0 2 0 10 0 1 -1/3 0 1	9 30 11	Новая R(- Прошлая R(+ + ведущий элемент (3) Новая Rj = Прошлая R2 - - 0 х Новая Ri Новая Щ = Прошлая Щ - - 1 х Новая R)
Целевая функция Р	0 -1 2/3 0 0		Новая Р = Прошлая Р -- (-2) х Новая Ri

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

Обозначим через R_s i-ю строку. Соотношение "Новая R3 = Прошлая R3 ^-- Новая R(" означает, что новые элементы строки 3 были получены вычитанием элементов новой ведущей строки (строка 1) из соответствующих элементов веду­щей строки 3 предьщущего шага. Вьшолненные операции перечислены в крайнем правом столбце табл. 12.4.

Шаг 6. Шаги 2-5 повторяются до тех пор, пока не будет достигнута неотрица­тельность всех элементов в строке целевой функции.

Таблица 12.5. Вторая симплекс-таблица с отношениями

Базисные переменные	Переменные * У s, s2 s3	Правая часть Ь	Отношения Ь/элемент ведущего столбца
X s2 S3	1 0 1/3 0 0 0 2 0 1 0 0 1» -1/3 0 1	9 30 11	9/0 =» 30/2 = 15 11/1=11 «- ведущая строка
Целевая функция Р	0 -1 2/3 0 0

т