Определение ведущих столбца и строки

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

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

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

Если в столбце симплексной таблицы содержаться два или несколько одинаковых наименьших значения, то новый опорный план будет вырожденным (одна или несколько базисных переменных станут равными нулю). Вырожденные планы могут привести к зацикливанию, т.е. многократному повторению процесса вычислений, не позволяющему завершить задачу. С целью исключения этого для выбора направляющей строки используют способ Креко, который заключается в следующем. Делим элементы строк, имеющие одинаковые наименьшее значение , на предполагаемые разрешающие элементы, а результаты заносим в дополнительные строки. За ведущую строку выбирается та, в которой раньше встречается меньшее число при чтении таблицы слева направо по столбцам.

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

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

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧИ СИМЛЕКСНЫМ МЕТОДОМ.

Торговое предприятие, располагающее материально-денежными ресурсами, реализует три группы товаров А, В, и С. Плановые нормативы затрат ресурсов на тыс. руб. товарооборота, прибыль от продажи товаров на тыс.руб. товарооборота, а ток же объем ресурсов заданы в таблице 2.

Определить плановый объем продажи и структуру товарооборота так, что бы прибыль торгового предприятия была максимальной.

Таблица 2.

Виды материально-денежных ресурсов	Норма затрат материально-денежных ресурсов на ед. товарооборота, тыс.руб.	Обьем ресурсов
А группа	В группа	С группа
Рабочее время продавцов, чел./ч	0,1	0,2	0,4
Плоцадь торговых залов, м2	0,05	0,02	0,02
Площадь складских помещений, м2
Прибыль, т.руб.				мах

1. запишем математическую модель задачи.

Определить , который удовлетворяет условиям

И обеспечивают максимальное значение целевой функции

Для построения первого опорного плана систему неравенств привидем к системе уравнений.

В матрице этой системы уравнений имеет:

Векторы А₄,А₅,А₆ – линейно независимы, так как определитель, составленный из компонент этих векторов, отличен от нуля:

Соответствующие с этим векторам переменные х₄,х₅,х₆ будут базисными.

Решим систему уравнений относительно базисных переменных.

Функционально запишем в виде:

1. полагая. Что свободные переменные х₁=0, х₂=0, х₃=0, получим опорный план в котором базисные переменные х₄=1100, х₅=120, х₆=8000, следовательно товары не продаются и прибыль равна нулю, а ресурсы не используются.

Запишем первый опорный план в симплексную таблицу 3.

Симплексная таблица 3.

план	Базисные переменные	Ресурсы плана	Значения коэффициентов при переменных
X1	X2	X3	X4	X5	X6
I план	X4 x5 x6		0.1 0.05	0.2 0.02	0.4 0.02
Инд. Строка			-3	-5	-4
II план	X4 x5 x6		0.5 0.04 2.5		-0.02	-0.1 -5
Инд. Строка			-0.5
III план	X4 x5 x6				2.25 -0.5 1.25	6.25 -2.5 0.25	12.5 -62.5
Инд. строка					5.75	23.75	12.5

3. первый опорный план 1 не оптимальный, так как в индексной строке находятся отрицательные коэффициенты -3,-4,-5.

4. за ведущий столбец выберем столбец, соответствующий переменной х₂, так как сравнивая по модулю имеем:

Рассчитываем значения по строкам, как частное от деления

И выбираем наименьшее:

Следовательно, первая строка является ведущей. Элемент 0,2 находиться на пересечении ведущего столбца и ведущей строки и выделен.

1. Формируем следующую симплексную таблицу. Вместо переменной х₄ в план II войдет переменная х₂. Строка, соответствующая переменной х₂ в плане II, получена в результате деления всех элементов строки х₄ плана I на разрешающий элемент РЭ=0,2. На месте разрешающего элемента в плане II получаем 1. В остальных клетках столбца х₂ плана II записываем нули.

Таким образом в новом плане II заполнены строки х₂ и столбец х₂. Все остальные элементы нового плана II, включая элементы индексной строки определяется по правилу прямоугольника. Для этого выбираем из старого плана 4 числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ=0,2. Во второй вершине по диагонали находится старое значение элемента, например, значение целевой функции F(K₁)=0=СЭ, которое указывает па место расположение нового НЭ в новом плане II. 'Третий элемент А=1100 и четвертый элемент В=-5 завершают построение прямоугольника в недостающих двух вершинах и расположены по другой диагонали. Значение нового элемента в плане II находится из выражения:

НЭ=СЭ-(А*В)/РЭ=0

Элементы строки определяются аналогично:

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

Выполняя последовательно все этапы алгоритма, формируем план II.

6 На третьей итерации таблицы 3 получаем план III, который является оптимальным так как все коэффициенты в индексной строке 0. Оптимальный план можно записать так:

тыс. руб.

Следовательно, необходимо продавать товаров первой группы А 250 ед., а второй группы В – 5375 ед. При этом торговое предприятие получает максимальную прибыль в размере 27625 тыс. руб. Товары группы С не реализуются.

В оптимальном плане среди базисных переменных находится дополнительная переменная х₆.Это указывает, что ресурсы третьего вида (площадь складских помещений) недоиспользована на 1875 м², так как переменная х₆ была введена в первое ограничение задачи, характеризующее собой использование этого ресурса.

В индексной строке III плана в столбцах переменных х₃,х₄,х₃, не вошедших в состав базисных, получены ненулевые элементы, поэтому оптимальный план задачи линейного программирования является единственным.

1. ?