Стандартная форма линейных оптимизационных моделей 3 страница

x₁ + 2x₂ + x₄ = 4

минимизировать: Z = 4x₁ + x₂ + MR₁

при ограничениях: 3x₁ + x₂ +R₁ = 3

4x₁ + 3x₂ + x₃ = 6

x₁ + 2x₂ + x₄ = 4

R₁ = 3 – 3x₁ – x₂

Z = 4x₁ + x₂ + M(3 – 3x₁ – x₂) = 4x₁ + x₂ + 3M – 3x₁M – x₂M =

= (4 – 3M)x₁ + (1 – M)x₂ + 3M;

Z – (- 4 +3M)x₁ – (- 1 + M)x₂ = 3M.

№2а. максимизировать: Z = x₁ + x₂

при ограничениях: 2x₁ + 3x₂ = 5

7x₁ + 2x₂ £ 6 x₁; x₂ ³ 0.

С.ф:

Максимизировать: Z = x₁ + x₂

При ограничениях: 2x₁ + 3x₂ = 5

7x₁ + 2x₂ + x₃ = 6 x₁; x₂; x₃ ³ 0.

Максимизировать: Z = x₁ + x₂ – M(5 – 2x₁ – 3x₂) = x₁ + x₂ – 5M + 2x1M +

+3x₂M = (1 + 2M)x₁ + (1 + 3M)x₂ = -5M;

Z – (- 1 – 2M)x₁ + (-1 – 3M)x₂ = -5M.

б) минимизировать: Z = x₁ + x₂ + x₃ + x₄

при ограничениях: 2x₁ + x₂ + x₃ = 7

4x₁ + 8x₂ + x₄ = 8

x₃ = 7 – 2x₁ – x₂

x₄ = 8 – 4x₁ – 8x₂

Z = x₁ + x₂ +(7 – 2x₁ – x₂)+(8 - 4x₁ - 8x₂) = x₁ + x₂ + 7– 2x₁ – x₂ + 8 – 4x₁ –8x₂=

= - 5x₁ – 11x₁ + 15

Z +5x₁ + 11x₂ = 15

Упражнения:

1. Применительно к рассматриваемому примеру запишите Z – уравнения начальной С – Т для каждого из следующих вариантов изменения модели.

а). В третьем ограничении поставлен знак ³.

Ответ: Z + (-4 + 8 M)x₁ + (-1 + 6M)x₂ – Mx₃ – Mx₄ = 13M.

Искусственные переменные вводятся в каждое из трех уравнений.

б). Во втором ограничении поставлен знак £.

Ответ: Z + (-4 + 3M)x₁ + (-1 + M)x₂ = 3M.

Искусственные переменные вводится только в 1-ое уравнение.

в). Целевая функция: Z = 4x₁ + x₂ подлежит максимум.

Ответ: Z + (-4 – 7M)x₁ + (-1 – 4M)x₂ + Mx₃ = -9M.

Искусственные переменные вводятся в 1-ое и 2-ое уравнения.

2. Необходимо ли использование искусственных переменных для получения начального решения в следующих задачах? (Все переменные неотрицательны).

а). Максимизировать: Z = x₁ + x₂

при ограничениях 2x₁ + 3x₂ = 5

7x₁ + 2x₂ £6

Ответ: Да, следует ввести искусственные переменные R₁ в первое уравнение и остаточные переменные – во второе.

б). Минимизировать: Z = x₁ + x₂ + x₃ + x₄

при ограничениях 2x₁ + x₂ + x₃ = 7

4x₁ + 8x₂ + x₄ = 8

Ответ: Нет, следует использовать переменные х₃ и х₄, предварительно исключив их из целевой функции путем подстановок

х₃ = 7 – 2х₁ – х₂

х₄ = 8 – 4х₁ – 3х₂.

Двухэтапный метод

Недостаток М-метода связан с возможностью ошибок в вычисле­ниях, обусловленных очень большой величиной коэффициента М. Чтобы пояснить это, допустим, что в примере из подразд. 3.2.3 значение М было принято равным 100 000. Тогда коэффициенты при х₁ и х₂ в z-уравнении начальной симплекс-таблицы будут равны (—4+700000) и (—1+400000) соответственно. Из-за большой величины М вклад исходных коэффициентов (4 и 1) оказывается ничтожным. Вследствие ошибок округления, свойственных любой цифровой ЭВМ, процесс вычислений может стать нечувстви­тельным к значениям исходных коэффициентов при х_х и х₂. При этом возникает опасность того, что эти переменные будут интерпретиро­ваться как переменные, фигурирующие в целевой функции с нуле­выми коэффициентами.

Двухэтапный метод позволяет избежать этих затруднений. При использовании двухэтапного метода искусственные переменные вводятся таким же образом, как и в М-методе. Однако коэффициент М при этом не фигурирует, что достигается расчленением процесса решения задачи на два этапа (отсюда и название метода - двух­этапный). Этапы реализации данного метода включают следующие процедуры.

Этап I. Вводятся искусственные переменные, необходимые для получения стартовой точки. Записывается новая целевая функ­ция, предусматривающая минимизацию суммы искусственных пере­менных при исходных ограничениях, видоизмененных за счет вве­дения искусственных переменных. Если минимальное значение но­вой целевой функции равно нулю (т. е. все искусственные перемен­ные имеют в оптимуме нулевые значения), исходная задача имеет допустимое решение. Переходят к этапу II. В противном случае, когда минимум новой целевой функции оказывается больше нуля, исходная задача не имеет допустимых решений, и процесс вычисле­ний заканчивается.

Э т а п II. Оптимальное базисное решение, полученное на этапе I, используется в качестве начального решения исходной задачи.

Реализацию двухэтапного метода проиллюстрируем опять напримере из подразд. 3.2.3.

Этап I. Так как необходимо ввести искусственные переменные R₁ и R₂ в первое и второе уравнения соответственно, этап I сводится к

Минимизации r = R₁ + R₂

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

3x₁ + x₂ + R₁ =3,

4x₁ + 3x₂ – x₃ + R₂ = 6,

x₁ + 2x₂ + x₄ = 4,

x₁, x₂, x₃, R₁, R₂, x₄ ³ 0.

Поскольку R₁ и R₂ фигурируют в начальном решении, следует подставить в целевую функцию их выражения, полученные из соот­ветствующих ограничений (сравните с процедурой, использованной в М -методе):

r = R₁ + R₂ = (3 – 3x₁ – x₂) + (6 – 4x₁ – 3x₂ + x₃) = - 7x₁ – 4x₂ + x₃ + 9.

С помощью этого соотношения получим начальную симплекс-таблицу:

Базисные переменные	x1 x2 x3 R1 R2 x4	Решение
r	7 4 -1 0 0 0
R1	3 1 0 1 0 0 4 3 -1 0 1 0 1 2 0 0 0 1
R2
x4

Оптимальная таблица, получаемая за две итерации, имеет следующий вид. (Проверьте!)

Базисные переменные	x1 x2 x3 R1 R2 x4	Решение
r	0 0 0 -1 -1 0
R1	1 0 1/5 3/5 -1/5 0 0 1 -3/5 -4/5 3/5 0 0 0 1 1 -1 1	3/5 6/5
R2
x4

Так как r = 0, задача имеет допустимое решение, и можно перходить к этапу II.

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

х₁ + 1/5х₃ = 3/5,

х₂ – 3/5х₃ = 6/5,

х₃ + х₄ = 1.

Эти уравнения полностью эквивалентны уравнениям исходной зада­чи, записанной в стандартной форме (до введения искусственных переменных). Поэтому исходную задачу можно сформулировать сле­дующим образом;

минимизировать z = 4x1 + x₂

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

х₁ + 1/5х₃ = 3/5,

х₂ – 3/5х₃ = 6/5,

х₃ + х₄ = 1,

х₁, х₂, х₃, х₄ ³ 0.

Главная цель первого этапа вычислений состоит в том, чтобы обеспечить получение начального решения исходной задачи. Так как задача содержит три уравнения и четыре переменные, то, при­писывая одной (4—3==1) из переменных, а именно х₃, нулевое зна­чение, можно сразу получить начальное допустимое базисное реше­ние: х₁ = 3/5, х₂ = 6/5 и х₄ = 1.

Для решения задачи необходимо, как и при использовании Л1-метода, подставить в целевую функцию выражения для базисных переменных а;! и л-з, получаемые из соответствующих ограничений;

z = 4х₁ + х₂ = 4 (3/5 – 1/5х₃) + (6/5 + 3/5х₃) = -1/5х₃ + 18/5.

В результате будем иметь следующую начальную симплекс-таблицу для этапа II:

Базисные переменные	x1 x2 x3 x4	Решение
r	0 0 1/5 0	18/5
R1	1 0 1/5 0 0 1 -3/5 0 0 0 1 1	3/5 6/5
R2
x4

Решение, представленное в данной таблице, не оптимально, так как переменная х₃ подлежит включению в базис. Если выполнить необходимые вычислительные процедуры симплекс-алгоритма, оп­тимальное решение будет получено за одну итерацию. (Проверьте!)

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

Следует подчеркнуть, что на этапе II искусственные переменные не фигурируют только в том случае, если в конце этапа I они становятся небазисными переменными (как это было в рассмотренного примере). Однако возможен и такой случай, когда при завершении этапа I искусственные переменные, имея нулевые значения, остаются базисными. Это требует принятия особых мер предосторожности, исключающих возможность появления положительных искусственных переменных на этапе II вычислений. С деталями соответствующих процедур можно познакомиться в книге [2, разд. 5.2].

Упражнение 3.2.5

(а) Как можно интерпретировать искусственные переменные, используемые на этапе I двухэтапного метода? В частности, почему необходимо минимизировать сумму искусственных переменных?

[Ответ. Искусственные переменные можно рассматривать как «меру недопустимости» при проверке выполнения исходных ограничений. Когда минимум суммы (неотрицательных) искусственных переменных равен нулю каждая из этих искусственных переменных имеет нулевое значение. По этому получаемое базисное решение является допустимым решением исходной задачи.]

(б) Следует ли максимизировать сумму искусственных переменных на этапеI, если целевая функция исходной задачи ЛП подлежит максимизации?

[Ответ. Нет, в рамках этапа I всегда осуществляется минимизация, так какименно процесс минимизации эквивалентен «штрафованию» искусственных переменных.]

Лекция 9:

ИНТЕРПРЕТАЦИЯ СИМПЛЕКС - ТАБЛИЦ. АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ

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

Из вышеизложенного следует, что основное внимание следует теперь уделить интерпретации и анализу результатов, полученных с помощью ЭВМ. Однако, было бы ошибочным считать, что интерпретация информации, выведенной ЭВМ на печать, возможна без ясного представления о том, почему и как «работает» СМ. Соответствующие вопросы мы рассмотрели выше. Следует еще раз подчеркнуть важность понимания положений, определяющих возможность применения СМ. В противном случае всегда есть опасность получения ошибочных решений и как следствие «вотума недоверия».

Исследователя вряд ли устроила бы заключительная С – Т, из которой можно было бы получить только список переменных и их значения. На самом же деле результирующая С – Т «насыщена» весьма важными данными, лишь небольшую часть которых составляют оптимальные значения переменных. Из С-Т либо непосредственно, либо при помощи простых дополнительных вычислений можно получить информацию относительно

1. оптимального решения,

2. статуса ресурсов,

3. ценности каждого ресурса,

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

Сведения, относящиеся к первым трем пунктам, можно извлечь непосредственно из С – Т для оптимального решения. Получение информации, относящейся к 4-му пункту, требует дополнительных вычислений.

Для иллюстрации возможностей получения указанной выше интерпретации из заключенной С – Т воспользуемся опять задачей фирмы Reddy Mikks Эта задача формируется следующим образом:

Максимизировать: Z = 3x_E + 2x₁ (прибыль)

При ограничениях: x_E + 2x₁ +S₁ = 6 (продукт А)

2х_E + x₁ + S₂ = 8 (продукт В)

-x_E + x₁ + S₃ = 1 (спрос)

x₁ + S₄ = 2 (спрос)

x_E, S₁; S₂; S₃; S₄ ³ 0

Оптимальная С – Т имеет вид:

Базисные переменные	xe	xi	S1	S2	S3	S4	Решение
z			1/3	4/3			12 х 2/3
х1			2/3	-1/3			1х 1/3
хе			-1/3	2/3			3х 1/3
S3			-1
S4			-2/3	1/3			2/3

Оптимальное решение.

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

Переменные, отсутствующие в столбце «Базисные переменные», обязательно имеют нулевое значение. Значения остальных переменных приводятся в столбце «Решение». При интерпретации результатов оптимизации в задаче фирмы Reddy Mikks нас прежде всего интересуют объемы производства красок для внутренних (I) и наружных (E) работ, то есть значения управляемых переменных Х₁ и Х_Е. Используя данные, содержащиеся с С – Т для оптимального решения, основные результаты можно представить в следующем виде:

Управляемые переменные	Оптимальные решения	Решение
хЕ	3 1/3	Объем производства краски Е должен быть равен 3 1/3т. в сутки
Х1	1 1/3	Объем производства краски I должен быть равен 1 1/3т. в сутки
Z	12 2/3	Прибыль от реализации продукции равна 12 2/3тыс.долл. (в сутки)

Заметим, что Z = 3х_Е + 2х_I = 3(3 1/3) + 2(1 1/3) = 12 2/3. Это соответствует данным заключительной С – Т.

Статус ресурсов.

Ресурсы относят к дефицитным или недефицитным в зависимости от того, полное или частичное их использование предусматривает оптимальное решение задачи. Сейчас цель состоит в том, чтобы получить соответствующую информацию непосредственно из С – Т для оптимального решения. Однако сначало следует четко уяснить следующее. Говоря о ресурсах, фигурирующих в задачи ЛП, мы подразумеваем, что установлены некоторые максимальные пределы их запасов, поэтому в соответствующих исходных ограничениях должен использоваться знак £. Следовательно, ограничения со знаком ³ не могут рассматриваться как ограничения на ресурсы. Скорее, ограничения такого типа отражают то обстоятельство, что решение должно удовлетворять определенным требованиям, например, обеспечению минимального спроса или минимальных отклонений от установленных структурных характеристик производства (сбыта).

В модели, построенной для фирмы Reddy Mikks, фигурируют 4 ограничения со знаком £. Первые два ограничения (определяющие допустимый расход исходных продуктов) представляют собой «истинные» ограничения на ресурсы. 3-е и 4-е ограничения относятся к спросу. Эти требования можно рассматривать как ограничения на соответствующие «ресурсы», так как увеличение спроса на продукцию эквивалентно расширению «представительства» фирмы на рынке сбыта. В отношении финансовых средств такая ситуация имеет те же последствия, что и увеличение запасов ресурсов (исходных продуктов), требующее распределение дополнительных вложений.

Таким образом, следует, что статус ресурсов (дефицитный или недефицитный) для любой модели ЛП можно установить непосредственно из результирующей С – Т, обращая внимание на значения остаточных переменных. Применительно к задаче фирмы Reddy Mikks можно привести следующую сводку результатов:

Ресурс	Остаточная переменная	Статус Ресурса
Исходный продукт А	S1 = 0	Дефицитный
Исходный продукт В	S2 = 0	Дефицитный
Повышение объема производства краски I по отношению к объему производства краски Е	S3 = 3	Недефицитный
Спрос на краску I	S4 = 2/3	Недефицитный

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

Ресурсы, увеличение запасов которых позволяет улучшить решение (увеличить прибыль), - это исходные продукты А и В, поскольку из С – Т для оптимального решения видно, что они дефицитны. В связи с этим логично поставить следующий вопрос: какому из дефицитных ресурсов следует отдать предпочтение при вложении дополнительных средств на увеличение их запасов, с тем чтобы получить от них максимум отдачу? Ответ на этот вопрос будет дан в следующей теме, где рассмотрим ценность ресурсов.

Пример: Применительно к задаче фирмы Reddy Mikks найти экономическую интерпретацию оптимальным значением остаточных переменных S₃ = 3 и S₄ = 2/3

Ответ: Так как Х_Е - Х₁ = S₃ – 1, то переменная S₃ характеризует увеличенное на 1т. превышение объема производства краски Е по отношению к объему производства краски I. Таким образом, S₃ = 3 соответствующее случаю, когда объем производства краски Е превышает объем производства краски I на 2т. Переменная S₄ характеризует предельное увеличение производства краски I, при котором не будет превышен максимум спрос на рынке сбыта.

Ценность ресурса.

Ценность ресурса характеризуется величиной улучшения оптимального значения Z, приходящегося на единицу прироста объема данного ресурса. Графическая интерпретация этого определения применительно к условиям задачи фирмы Reddy Mikks была дана выше. Прежде чем продолжить изучение данного вопроса, целесообразно вернуться к рис. Графический анализ показывает, что ценность ресурсов 1, 2, 3 и 4 равна.

Y₁ = 1/3 тыс. долл. на 1т. прироста запасов ресурса А,

Y₂ = 4/3 тыс. долл. На 1т. прироста запасов ресурса В,

Y₃ = 0, Y₄ = 0.

Эта информация представлена в С – Т для оптимального решения задачи. Обратим внимание на значения коэффициентов Z – уравнения, состоящих при переменных начального базиса S₁, S₂, S₃ и S₄.

рис. С: (3 1/3, 1 1/3); Z = 12 1/3; К(3,2); Z = 13

X₁

Е D K

3 4 1 C Ресурс А = 7т.

F 5 6 2 Ресурс А = 6т.

A B Х_Е

Выделим для удобства соответствующую часть С – Т:

Базисные переменные	ХЕ Х1 S1 S2 S3 S4	Решение
Z	0 0 1/3 4/3 0 0	12 2/3

Значения указанных коэффициентов (1/3; 4/3; 0; 0) в точности соответствуют значениям у₁; у₂; у₃; у₄. Как следует из теории решения задач ЛП, ценность ресурсов всегда можно определить по значениям коэффициентов при переменных начального базиса, фигурирующих в Z – уравнении оптимальной С – Т. Так как переменная S_i всегда связана только с ресурсом i, идентификация ресурса по коэффициенту не должна вызывать затруднений.

Покажем, каким образом аналогичный результат можно получить непосредственно из С – Т для оптимального решения задачи фирмы Reddy Mikks.

Z = 12 2/3 – (1/3S₁ + 4/3S₂ + 0S₃ + 0S₄)

Положительное приращение переменной S₁ относительно ее текущего нулевого значения приводит к пропорциональному уменьшению Z, причем коэффициент пропорциональности = 1/3тыс. долл./т. Но, как следует из первого ограничения модели,

Х_Е + 2Х₁ + S₁ = 6,

Увеличение S₁ эквивалентно снижению запаса ресурса 1 (продукта А). Отсюда следует, что уменьшение запаса первого ресурса вызывает пропорциональное уменьшение целевой функции с тем же коэффициентом пропорциональности, равным 1/3тыс. долл./т. Так как мы оперируем с линейными функциями, полученный вывод можно обобщить, считая, что и увеличение запаса первого ресурса (эквивалентно введению избыточной переменной S₁ < 0) приводит к пропорциональному увеличению Z с тем же коэффициентом пропорциональности, равным 1/3тыс. долл./т. Аналогичные рассуждения справедливы для ресурса 2.

В отношении ресурсов 3 и 4 было установлено, что их ценность = 0 (у₃ = у₄ = 0). Этого и следовало ожидать, так как ресурсы 3 и 4 оказались недефицитными. Такой результат получается всякий раз, когда соответствующие остаточные переменные имеют положительное значение.

Несмотря на то, что ценность различных ресурсов, определяемая значениями переменных у_i, была представлена в стоимостном (тыс. долл.) выражении, ее нельзя отождествлять с действительными ценами, по которым возможна закупка соответствующих ресурсов. На самом деле речь идет о некоторой мере, имеющей экономическую природу и количественно характеризующей ценность ресурса только относительно полученного оптимального значения целевой функции. При изменении ограничений модели соответствующие экономические оценки будут меняться даже тогда, когда оптимизируемый процесс предполагает применение тех же ресурсов. Поэтому при характеристики ценность ресурсов экономисты предпочитают использовать такие термины, как теневая цена, скрытая цена или более специфический термин – двойственная оценка.

Дата добавления: 2015-06-04