Приемы сведения ЗЛП к стандартным формам

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

1. Для сведения задачи минимизации к задаче максимизации (и наоборот) достаточно изменить знаки коэффициентов целевой функции.

2. Изменение направления знака неравенства достигается путем изменения знаков коэффициентов ограничения и соответствующей компоненты вектора ограничений.

3. Превращение равенств в неравенства. Пусть имеется ограничение вида

Легко заметить, что это равенство равносильно следующим двум неравенствам:

или следующим неравенствам:

4. Превращение неравенств в равенства.

а) Пусть имеется неравенство

Вводя вспомогательную переменную это неравенство можно записать в виде

б) Аналогично неравенство

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

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

5. Преобразование условий вида Пусть на переменную не наложено условие неотрицательности. Введем две вспомогательные переменные неотрицательные переменные и . Используя эти переменные, условие можно записать в виде

или в виде

Теперь в математической записи задачи вместо нужно подставить одну из приведенных выше разностей, а вместо условия нужно использовать два неравенства и .

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

,

Из этих равенств имеем:

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

Дата добавления: 2014-01-11