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

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

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

Первый случай.

Определение 4.1. Систему ограничений канонической ЗЛП называют имеющей единичный неотрицательный базис, если правые части системы неотрицательны ( , ), каждое выражение в левой части содержит одну (свою) переменную с коэффициентом, равным единице, а все остальные – с коэффициентом, равным нулю:

, . (4.1)

В векторной форме система ограничений может быть записана так:

.

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

Выразив из системы (4.1) переменные через переменные , получим систему ограничений в допустимом виде

, . (4.2)

Начальный опорный план (базисное решение) ЗЛП в этом случае строится достаточно просто. Предпочтительные переменные выбираются в качестве базисных, а все остальные – свободными переменными. Свободным переменным придаются нулевые значения, а базисным переменным – свободные члены. Начальный опорный план имеет вид

.

Пример 4.1. Привести систему ограничений канонической ЗЛП к допустимому виду, найти базис переменных и начальный опорный план:

Решение. Система ограничений представлена в форме (4.1) с неотрицательным базисом переменных , так как в правой части каждого уравнения находятся неотрицательные числа. Выразив переменные через , получим систему ограничений в допустимом виде

Начальный опорный план (базисное решение) имеет вид

.

Второй случай. Пусть система ограничений имеет вид

, . (4.3)

Введя в систему ограничений (4.3) балансовые переменные (по одной в каждое неравенство), получим систему ограничений канонического вида

, , (4.4)

в которой базисными будут являться балансовые переменные , а свободными – переменные .

В векторной форме система ограничений (4.4) принимает вид

Тогда начальный опорный план (базисное решение) примет вид

.

Третий случай. Пусть система ограничений имеет вид

, . (4.5)

В этом случае для нахождения базисных переменных сначала систему ограничений приводят к каноническому виду путем введения балансовых переменных (по одной в каждое неравенство):

, ,

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

, ,

которые и объявляются базисными переменными.

Процесс решения задачи в этом случае называется решением ЗЛП М-методом (методом искусственного базиса). Более подробно об этом методе идет речь в §7.

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

Пример 4.2. Привести систему ограничений канонической ЗЛП к допустимому виду, найти базис переменных и начальный опорный план:

.

Решение. Составим расширенную матрицу системы ограничений:

.

Прибавим ко второй строке первую строку, после чего умножим вторую строку на :

.

Из последней матрицы видно, что можно взять в качестве базисной переменной, так как коэффициенты при ней образуют первый столбец единичной матрицы, причем свободный коэффициент положительный. Далее элементарные преобразования совершаем так, чтобы второй столбец расширенной матрицы не изменился. Умножим третью строку матрицы на и сложим с первой строкой, после чего третью строку умножим на :

.

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

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

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

.

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Популярное:

1. I. Предмет и задачи дидактики
2. II. Предполагаемые союзники и их задачи
3. III. Целевые установки, задачи и направления обеспечения транспортной безопасности
4. Алгоритм решения задач линейного программирования с помощью Excel
5. Алгоритм решения транспортной задачи
6. Анализ подходов и методов решения задачи
7. Анализ современного состояния АПК в России: задачи и экономическая стратегия развития
8. БИЛЕТ 1. Цели, задачи и основные принципы православной педагогики. Сотериологический характер педагогических воззрений Святых Отцов Церкви
9. БИЛЕТ 9. Вопрос 2. Психолого-педагогические задачи процесса духовно-нравственного становления личности на этапе вхождения в мир (наследство, зачатие, внутриутробное развитие, роды, новорожденность).
10. Бухгалтерский учет: его задачи, функции и
11. ВВЕДЕНИЕ. ЗАДАЧИ И ПРОБЛЕМЫ ГИСТОЛОГИИ.
12. Введение. Сущность , основные задачи, субъекты и объекты менеджмента.