Определение первоначального допустимого базисного решения

В рассмотренных выше примерах оптимальное решение получено путем последовательного перехода от первоначального допустимого базисного решения к следующему, "лучшему", и так – до достижения критерия оптимальности. Однако не всегда на первом же шаге получается допустимое базисное решение. В следующем примере рассмотрим один из возможных алгоритмов получения допустимого базисного решения. Другой, так называемый М-метод, будет изложен в параграфе 5.7.

5.3. Решить симплексным методом задачу:

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

Решение. Вводим дополнительные неотрицательные переменные с соответствующими знаками

В соответствии с правилом, сформулированным в параграфе 5.2, на I шаге в качестве основных возьмем дополнительные переменные.

I шаг. Основные переменные:

Неосновные переменные:

Выражаем основные переменные через неосновные:

(5.6)

– первое базисное решение недопустимое (отрицательная компонента выделена), поэтому оно не может быть оптимальным. Линейную функцию на недопустимом решении не рассматриваем! В системе (5.6) выберем то уравнение, которое содержит отрицательный свободный член, т.е. первое уравнение (если таких уравнений несколько, выбираем любое из них).

Поскольку переменная х3 принимает отрицательное значение при первом базисном решении, то ее необходимо увеличить. Это можно сделать за счет увеличения любой из неосновных переменных, входящих в первое уравнение с положительным коэффициентом, в данном случае – переменной хТ Если перевести эту переменную в основные, то она, став положительной, увеличит переменную х3. Как только х2 достигнет уровня 1, то ,г3 обратится в нуль, т.е. исчезнет отрицательная компонента в решении. Можно считать, что переменная Xj етанет неосновной. Однако рост переменной х2 ограничен условиями неотрицательности остальных переменных, которые определяют х2 = min {1; 3; ∞} = 1, т.е. первое уравнение разрешающее. При х2 = 1 переменная .г3 = 0 и переходит в неосновные переменные.

II шаг. Основные переменные:

Неосновные переменные:

Выражая новые основные переменные через новые неосновные, начиная с разрешающего уравнения, получаем

и базисное решение Х2 = (0; 1; 0; 2; 3), которое является допустимым. Поэтому выражаем через неосновные переменные линейную функциюи продолжаем решение в соответствии с алгоритмом, изложенным в параграфе 5.2 (читателю рекомендуется провести его самостоятельно). ►

Однако нс всегда первый же шаг избавляет от недопустимого решения.

5.4. Решить симплексным методом задачу:

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

Решение. После введения дополнительных неотрицательных переменных с соответствующими знаками получим систему уравнений:

На I шаге дополнительные переменные возьмем в качестве основных, так как они удовлетворяют правилу, изложенному в параграфе 5.2: входят во все уравнения и только но одному разу.

I шаг. Основные переменные:

Неосновные переменные:

Выразим основные переменные через неосновные:

X1 = (0; 0; -12; 7; 10; -2) – первое базисное решение недопустимое, с двумя отрицательными компонентами (выделены).

Для получения допустимого базисного решения поступаем так, как в задаче 5.3: выбираем любое уравнение, содержащее отрицательный свободный член (первое или четвертое), например первое, и в нем – любую неосновную переменную с положительным коэффициентом: х1 или х2, например х,. Наибольшее возможное значение х1 = min {12/2; ∞; 10/2; ∞} = = 5 достигается в третьем уравнении; оно разрешающее, и переменная х5 переходит в неосновные переменные. Однако при этом ни одна из отрицательных компонент базисного решения не пропадает! Поэтому невыгодно переводить переменную х1 в основные переменные. Переведем в основные х2, тогда наибольшее возможное значение х2 = min {12/3; 7; 10; 2} = = 2 достигается в четвертом уравнении; при этом переменная х6 переходит в неосновные и исчезает одна отрицательная компонента в базисном решении.

II шаг. Основные переменные: х2, ж3, х4, жг

Неосновные переменные: х4, х6.

Выразим новые основные переменные через новые неосновные, начиная с четвертого уравнения:

Х2 = (0; 2; -6; 5; 8; 0) – недопустимое базисное решение с одной отрицательной компонентой. Рассмотрим второе уравнение (с отрицательным свободным членом) и переведем в основные одну из неосновных переменных ж, или х6, входящих в уравнение с положительными коэффициентами.

Получим из уравнений их наибольшие возможные значения: xl = min {оо; 3; 8/2} = 3 достигается во втором уравнении; xG = min {∞; 2; 5; 8} = 2 тоже определяет второе уравнение как разрешающее. Любой выбор устранит недопустимость решения, поэтому безразлично, какую переменную – ж, или х6 – выбрать. Переведем ж6 в основные.

III шаг. Основные переменные: х2, ж4, х5, х6.

Неосновные переменные: ж,, х3.

Выразим новые основные переменные через новые неосновные, начиная со второго уравнения:

Х3 = (0; 4; 0; 3; 4; 2) – допустимое базисное решение. Выражаем функцию цели через неосновные переменные F = -2х, +3х2 = 12-4х, +х3. Дальнейшее решение предоставляем выполнить самостоятельно в соответствии с алгоритмом, изложенным в параграфе 5.2. ►

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

Замечание 2. Из задачи 5.4 не следует делать вывод о том, что чем больше отрицательных компонент в первоначальном базисном решении, тем больше потребуется шагов, чтобы получить допустимое базисное решение. Оказывается, что в некоторых случаях невозможно получить допустимое базисное решение даже при одной отрицательной компоненте, а иногда его можно получить за один шаг, хотя все компоненты первоначального базисного решения отрицательны. Дальнейшие примеры пояснят это замечание.

Рассмотрим задачу о составлении рациона, приведенную в параграфе 1.2 и решенную геометрически в задаче 4.2.

5.5. Решить симплексным методом задачу:

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

Решение. Введем дополнительные переменные х3, х4, х5, х6 (каждую со знаком "минус"). Их экономический смысл – это разность между содержанием и необходимым минимумом каждого из питательных веществ.

На I шаге берем дополнительные переменные в качестве основных.

I шаг. Основные переменные: х3, х4, ху

Неосновные переменные: χν х.г

После преобразований получим

Xi = (0; 0; -9; -8; -12) – первое базисное решение недопустимое, содержащее три отрицательные компоненты. Неосновная переменная х2 входит в каждое уравнение с положительным коэффициентом, поэтому имеет смысл перевести ее в основные. В случае, когда все основные переменные принимают отрицательные значения, для ускорения решения можно в качестве значения для переменной х2 взять максимальное оценочное отношение из полученных во всех уравнениях: х.2 = шах {9/3; 8; 12} = 12. Третье уравнение является разрешающим, при этом х2 = 0 и переходит в основные, а остальные основные переменные принимают положительные значения.

II шаг. Основные переменные: х2, х4, х5.

Неосновные переменные: х(, х3.

После преобразований получим

Х2 = (0; 9; 0; 10; 42) – допустимое базисное решение. Если действовать, как в предыдущих примерах, то для получения допустимого решения потребуется три шага!

Заканчивая решение задачи 5.5 симплексным методом (рекомендуем это сделать самостоятельно), на следующем шаге получаем оптимальное базисное решение Х2 = (2; 3; 0; 0; 5), при котором минимальные затраты на рацион составляют F j = 26. Учитывая экономический смысл исходных и дополнительных переменных, получаем, что в оптимальном рационе используются 2 единицы корма I и 3 единицы корма II, при этом вещества 5, и S2 потребляются в необходимых минимальных количествах (х3 = х4 = 0), а питательное вещество 53 оказывается в избытке на 5 единиц (х. = 5). ►

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

5.6. Решить симплексным методом задачу:

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

Решение. Введем дополнительные переменные:

I шаг. Основные переменные: х3, хг

Неосновные переменные: xv х2.

Хх = (0; 0; 2; -1) – недопустимое базисное решение. Во втором уравнении выбираем любую переменную – х. или х2, так как обе имеют знак "плюс", и переводим в основные. Для X,: min {2; 6/2} = 2, разрешающее первое уравнение; для х2: min {2; 6} = 2, разрешающее тоже первое уравнение, поэтому в любом случае не удается сразу избавиться от отрицательной компоненты базисного решения (см. замечание 1 на с. 81).

II шаг. Основные переменные: х,, х4.

Неосновные переменные: х2, х3.

Получим после преобразований

Рис. 5.3

Х2 = (2; 0; 0; -2) – недопустимое базисное решение. Однако второе уравнение нс содержит неосновной переменной с положительным коэффициентом, поэтому невозможно увеличить переменную хА и получить допустимое базисное решение. Задача противоречива (рис. 5.3). ►

После анализа результатов, полученных при решении задач 5.1–5.6, сформулируем алгоритм получения первоначального допустимого базисного решения.

  • 1. Если каждая дополнительная переменная входит в уравнение с тем же знаком, что и свободный член, стоящий в правой части уравнения, то дополнительные переменные можно брать в качестве основных на I шаге. При этом получится допустимое базисное решение.
  • 2. Если первое базисное решение получилось недопустимым (например, в качестве основных взяты дополнительные переменные, но хотя бы одна из них входила в уравнение со знаком, противоположным знаку свободного члена), то рассматриваем уравнение, содержащее отрицательный свободный член (любое, если их несколько), и переводим в основные ту неосновную переменную, которая в это уравнение входит с положительным коэффициентом (любую, если их несколько). Такие шаги повторяем, до тех пор пока не достигается допустимое базисное решение.
  • 3. Если базисное решение недопустимое, а в уравнении, содержащем отрицательный свободный член, отсутствует неосновная переменная с положительным коэффициентом, то в этом случае допустимое базисное решение получить невозможно, т.е. условия задачи противоречивы.
 
< Пред   СОДЕРЖАНИЕ     След >