УПРАЖНЕНИЯ 7.2.2

1. В примере 7.2.1 представьте результаты вычислений, выполненных на первой и второй итерациях, в виде симплекс-таблиц.

2. Решите модифицированным симплекс-методом следующие задачи ЛП.

a) Максимизировать z = 6л:, - 2хг + Зх3 при ограничениях

2 л:, - х2 + 2х3 < 2, х1+4х3<4,

b) Максимизировать г = 2л:, + л:2 4- 2л:3 при ограничениях

4 л:, + Зл:2-1-8д:3< 12, 4 л:, + л:2 +12лг3<8, 4л:,-л:2 + 3л:3<8, л: л:2, х3>0.

c) Минимизировать z = 2jc, + л:2 при ограничениях

Зл:, 4- л:2 = 3, 4л:, 4-Зл:2 > 6, л:, 4-2л:2<3, л: jc2>0.

d) Минимизировать z = 5jc, - 4л:2 4- 6л:3 4- 8л:4 при ограничениях

л:, + 7л:2 4- Зл:3 4- 7л:4 < 46, Зл:, - л:24-л:34-2л:4<20, 2xl + 3x2-x3 + xi>18,

2 3* 4 ~ *

3. Решите следующую задачу ЛП с помощью модифицированного симплекс-метода, используя в качестве начального базиса вектор = (л:2, л:4, л:5)г.

Минимизировать z = 7х2 + 11л:3 - 10л:4 4- 26л:6 при ограничениях

хг-х3 + х, + хв = 6,

л:2 - л:3 л:4 4- Зл:6 - 8,

л:, 4- л:2 - Зл:3 4- л:4 4- л:5 = 12,

Х\> %2> 3> Ч 5 6 -

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

a) Задача из упражнения 2,с.

b) Задача из упражнения 2,d.

с) Задача из упражнения 3 (отказавшись от предложенного начального решения Хдо).

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

Шаг 0. Пусть В0 = I - начальный базис, причем хотя бы один из элементов вектора отрицателен (т.е. решение недопустимо).

Шаг 1. Вычисляем текущие значения базисных переменных: Хв = B b. Выбираем в качестве исключаемой из базиса переменную, имеющую наибольшее отрицательное значение (обозначим исключаемую переменную хг). Если все элементы в Хв неотрицательны, то вычисления заканчиваются, так как достигнуто допустимое решение.

Шаг 2.

a) Для всех небазисных переменных ху вычисляем разности zj-cj = СВВ 1Р. - е..

b) Для всех небазисных переменных ху вычисляем коэффициенты ограничений (В Р )г, ассоциированные со строкой, соответствующей исключаемой переменной хг.

c) Определяем вводимую в базис переменную как переменную, на которой достигается следующий минимум.

, (В-рд<о.

Если все (ВРД > 0, допустимого решения не существует.

Шаг 3. Формируем новый базис путем замены в базисе вектора Р на Рг. Вычисляем новую обратную матрицу В 1 и переходим к шагу 1.

Примените описанный метод для решения следующей задачи.

Минимизировать z = 2х, + х2

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

Зх, + х2 > 3, 4х, + Зх2 > 6, х, + 2х2 < 3, х х2> 0.

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

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

= min

(В-РД

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

X = L + X, Х>0

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

Теперь рассмотрим ситуацию с верхними границами X<U. В данном случае прямая замена X = U - X , X > 0 невозможна, поскольку обратная подстановка не гарантирует неотрицательности X. Здесь необходимо применение других процедур.

Запишем задачу ЛП с верхними границами на значения переменных как

максимизировать г = {СХ (A, I)X = Ь, 0 < X < U}.

При выполнении алгоритма решения задач с ограниченными переменными явно используются только ограничения (A, I)X = b, X > 0; ограничения вида X < U учитываются лишь в измененном симплексном условии допустимости.

Пусть Хв = B~b - текущее базисное допустимое решение задачи ЛП с ограничениями (A, I)X = b, X > 0. Обозначим через Р; вводимый в базис вектор, определенный на основе обычного симплексного условия оптимальности. Если предположить, что все небазисные переменные равны нулю, уравнение ограничения относительно базисной переменной xt будет записано следующим образом.

(ХД=(В,Ь),-(В-,Р.),х/

Поскольку вводимая переменная х примет положительное значение, величина базисной переменной (Хв), возрастет или уменьшится, в зависимости от того, будет значение (ВРД отрицательным или положительным. Таким образом, при определении значения вводимой переменной xj необходимо удовлетворить следующие три условия.

1. Базисная переменная (Хв), должна остаться неотрицательной, т.е. (Хв), > 0.

2. Базисная переменная (Хв), не должна превышать своей верхней границы, т.е. должно выполняться неравенство (Хв), < (UB) где UB - вектор, содержащий упорядоченные элементы вектора U, соответствующие вектору Хв.

3. Вводимая переменная xt не может принять значения, превышающего верхнюю границу, т.е. должно выполняться неравенство x.<ut, где и.- у-й элемент вектора U.

Первое условие (Хв), > 0 требует выполнения неравенства

(В-Ц-СВ-РДя.гО, которое заведомо будет выполняться, если

х,*е.=тЫ(В Н-

(в-рд

(В-РДэ-О .

Это условие полностью соответствует условию допустимости обычного симплекс-метода.