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

4х₁ + 5х₂ ³ 10 (2)

х₁ + 2х₂ £ 5 (3)

6х₁ + 7х₂ £ 3 (4)

4х₁ + 8х₂ ³ 5 (5)

Пусть х₁; х₂ ³ 0. С помощью подстановки искусственных переменных, используемой в М – методе, составьте начальное Z – уравнение для каждого из следующих случаев:

а) максимизировать Z = 5х₁ + 6х₂ при ограничениях (1), (3) и (4)

б) максимизироватьZ = 2х₁ – 7х₂ при ограничениях (1), (2), (4) и (5)

в) минимизировать Z = 3х₁ + 6х₂ при ограничениях (3), (4) и (5)

г) минимизировать Z = 4х₁ + 6х₂ при ограничениях (1), (2) и (5)

д) минимизировать Z = 3х₁ + 2х₂ при ограничениях (1) и (5)

№3.17. С помощью М – метода решите задачу ЛП, имеющую систему ограничений.

х₁ + х₂ +х₃ = 7

2х₁ – 5х₂ + х₃ ³ 10

х₁; х₂; х₃ ³ 0

и следующую целевую функцию:

а) максимизировать Z = 2х₁ + 3х₂ – 5х₃

б) минимизировать Z = 2х₁ + 3х₂ – 5х₃

в) максимизировать Z = х₁ + 2х₂ + х₃

г)минимизировать Z = 4х₁ – 8х₂ + 3х₃

№3.18. Рассмотрите следующую задачу: (на экзамен)

максимизировать Z = х₁ + 5х₂ + 3х₃

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

2х₁ – х ₂ = 4

х₁; х₂ ³ 0.

Пусть R соответствует искусственной переменной, вводимой в уравнение второго ограничения. Решите задачу, используя в начальном базисном решении переменные х₃ и R.

№3.19. Рассмотрите следующую задачу:

максимизировать Z = 2х₁ + 4х2 + 4х₃ – 3х₄

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

х₁ + 4х + х₄ = 8

х₁, … х₄ ³ 0

Найдите оптимальное решение, используя в начальном базисном решении переменные х₃ и х₄.

№3.20. Решите следующую задачу, используя в начальном допустимом базисном решении переменные х₃ и х₄.

минимизировать Z = 3х₁ + 2х₂ + 3х₃

при ограничениях х₁ +4 х₂ + х₃ ³ 7

2х₁ + х₂ + х₄ ³ 10

х₁, … х₄ ³ 0.

№3.21. Применительно к каждому из случаев, перечисленных в задаче №3.16., постройте целевую функцию для этапа I двухэтапного метода решения. (не рассматривали в лекциях).

Тема: Анализ модели на чувствительность.

№3.30. Рассмотрите следующую задачу ЛП, связанную с распределением ресурсов:

максимизировать Z = 3х₁ + 2х₂ (прибыль)

при ограничениях 4х₁ + 3х₂ £ 12 (ресурс 1)

4х₁ + х² £ 8 (ресурс 2)

4х₁ – х₂ £ 8 (ресурс 3)

х₁; х₂ ³ 0

С – Т, соответствует оптимальному решению задачи:

Базисные переменные	х1 х2 х3 х4 х5	Решение
Z	0 0 5/8 1/8 0	17/2
Х2 Х1 Х5	0 1 ½ -1/2 0 1 0 -1/8 3/8 0 0 0 1 -2 1	3/2

а) Определите статус каждого ресурса.

б) Определите ценность каждого ресурса.

в) Используя данные о ценности каждого ресурса, определите, запрос какого из них следует увеличить в первую очередь.

г) – Определите максимальный интервал изменения запасов ресурса 1, в пределах которого текущее решение остается допустимым.

д) – Выполните задание пп.(г) применительно к ресурсу 2.

е) – Для пп.(г) и (д) определите соответствующие изменения оптимальных значений Z.

ж) – Определите максимальный интервал изменения удельной прибыли для переменной х₁, в пределах которого полученное решение остается оптимальным.

з) – Выполните задание пп.(ж) применительно к переменной х₂.

№3.31. Рассмотрите следующую линейную оптимальную модель распределения ресурсов:

максимизировать Z = 2х₁ + 4х₂ (прибыль)

при ограничениях х₁ + 2х₂ £ 5 (ресурс 1)

х₁ + х₂ £ 4 (ресурс 2)

х₁; х₂ ³ 0

С – Т, соответствует оптимальному, имеет вид:

Базисные переменные	х1 х2 х3 х4	Решите
Z	0 0 2 0
Х2 Х4	½ 1 ½ 0 ½ 0 -1/2 1	5/2 3/2

Определите статус ресурса (дефицит, недефицит)

Лекция 10:

Линейное программирование: двойственность. Определение двойственной задачи. Соотношения двойственности.

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

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

Максимизировать n

или Z = å C_j X_j

минимизировать j=1

при ограничениях å a_ij x_j = b_i I = 1, 2 … m

j=1 x_j ³ 0 j = 1, 2 … n

Заметим, что в состав n переменных х_j включаются также избыточные переменные. Чтобы сформулировать условия двойственной задачи, расположим коэффициенты, фигурирующие в условиях прямой задачи, так, как схематически показано в таблице:

Переменные прямой задачи

	х1 х2 … хj … хn
Правые части ограничений двойственной задачи	С1 С2 … Сj … Сn
Коэффициенты левых частей ограничений двойственной задачи	а11 а12 … а1j … а1m а21 а22 … а2j … а2m … … … … … … … … … … … … аm1 аm2 … amj … amn	b1 b2 … … bm	y1 y2 … … ym	Перемен- ные двойст- венной задачи

Из приведенной схемы следует, что двойственная задача получается путем симметричного структурного преобразования условий прямой задачи в соответствии со следующими правилами:

1) каждому ограничению прямой задачи соответствует переменная двойственной задачи;

2) каждой переменной прямой задачи соответствует ограничение двойственной задачи;

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

Из указанных правил построения двойственной задачи следует, что она имеет m переменных (y₁, y₂ … y_m) и n ограничений (соответствующие n переменным прямой задачи (х₁; х₂; … х_n).

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

Прямая задача в стандартной форме^*) Целевая функция.	Двойственная задача
Целевая функция	Ограничения	Переменные
Максимизация минимизация	Минимизация максимизация	³ £	Не ограничены в знаке Не ограничены в знаке

^*) Все ограничения прямой задачи – равенства с неотрицательными правыми частями, а все переменные неотрицательные.

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

Рассмотрим примеры построения двойственной задачи.

Пример №1. Прямая задача:

Максимизировать Z = 5х₁ + 12х₂ + 4х₃

при ограничениях х₁ + 2х₂ + х₃ £ 10

2х₁ – х₂ + 3х₃ = 8

х₁; х₂; х₃ ³ 0

Прямая задача в стандартной форме:

Максимизировать Z = 5х₁ + 12х₂ + 4х₃ + 0х₄

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

2х₁ – х₂ + 3х₃ + 0х₄ = 8

х₁ … х₄ ³ 0.

Заметим, что х₄ – остаточная переменная, введенная в 1-ое ограничение. Поэтому коэффициенты, фигурирующие при этой переменной в целевой функции и во 2-ом ограничении = 0.

Двойственная задача:

Минимизировать w = 10y₁ + 8y₂ при ограничениях

Х₁: у₁ + 2х₂ ³ 5

Х₂: 2у₁ – у₂ ³ 12

Х₃: у₁ + 3у₂ ³ 4

Х₄: у₁ + 0у₂ ³ 0 (означает, что у₁ ³ 0)

у₁; у₂ не ограничены в знаке

Следует отметить, что у₁ ³ 0 является более жестким, чем условие неограничения у₁ в знаке. Поэтому при исключении этой избыточности ограничений двойственная задача формулируется следующим образом:

Минимизировать w = 10у₁ + 8у₂

При ограничениях у₁ + 2у₂ ³ 5

2у₁ – у₂ ³ 12

у₁ + 3у₂ ³ 4,

у₁ ³ 0; у₂ не ограничена в знаке.

Пример №2. Прямая задача:

Минимизировать Z = 5х₁ – 2х₂ при ограничениях

-х₁ + х₂ ³ -3

2х₁ + 3х₂ £ 5

х₁; х₂ ³ 0.

Прямая задача в стандартной форме:

Минимизировать Z = 5х₁ – 2х₂

При ограничениях х₁ – х₂ + х₃ = 5

х₁ … х₄ ³ 0.

Двойственная задача:

Максимизировать w = 3у₁ + 5у₂

При ограничениях у₁ + 2у £ 5

-у₁ + 3у₂ £ -2

у₁ £ 0; у₂ £ 0

у₁; у₂ не ограничены в знаке

(избыточные ограничения)

Упражнение к примеру №2. Как изменяются условия сформулированной выше двойственной задачи, если знак неравенства (£) во втором ограничении прямой задачи изменится на противопол. (³)?

Ответ: Ограничение у₂ £ 0 примет вид у₂ ³ 0.

Пример № 3. Прямая задача:

Максимизировать Z = 5х₁ + 6х₂

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

-х₁ + 5х₂ ³ 3

4х₁ + 7х₂ £ 8

х₁ не ограничена в знаке, х₂ ³ 0.

Прямая задача в стандартной форме:

Пусть х₁ = х₁¹ – х₁¹¹ где х₁¹, х₁¹¹ ³ 0. Стандартная формулировка прямой задачи при использовании такой подстановки имеет вид:

Максимизировать х = 5х₁¹ – 5х₁¹¹ + 6х₂

При ограничениях х₁¹ – х₁¹¹ + 2х₂ = 5

-х₁¹ + х₁¹¹ + 5х₂ – х₃ = 3

4х₁¹ – 4х₁¹¹ + 7х₂ + х₄ = 8

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

Двойственная задача

Минимизировать w = 5у₁ + 3у₂ + 8у₃

При ограничениях у₁ – у₂ 4у₃ ³ 5 ü

ý означает, что у₁ – у₂ + 4у₃ = 5

-у₁ + у₂ – 4у₃ ³ -5 þ

2у₁ + 5у₂ + 7у₃ ³ 6

-у₂ ³ 0 (означает, что у₂ £ 0)

у₃ ³ 0

у₁ не ограничена в знаке.

у₂; у₃ не ограничены в знаке (избыточные условия)

Заметим, что 1-ое и 2-ое ограничения двойственной задачи можно (но не обязательно) заменить одним ограничением в виде равенства у₁ – у₂ + 4у₃ = 5. Такая замена возможна всякий раз, когда переменная прямой задачи не ограничена в знаке, то есть неограниченность в знаке переменной прямой задачи всегда обуславливает появления ограничения двойственной задачи в виде равенства (а не неравенства) как при максимизации, так и минимизации целевой функции прямой задачи.

Задачи.

№4.1 Для каждой из приведенных ниже задач сформулируйте двойственную задачу:

а) максимизировать Z = -5х₁ + 2х₂

при ограничениях -х₁ + х₂ £ - 3

2х₁ + 3х₂ £ 5

х₁ х₂ ³ 0

б) минимизировать Z = 6х₁ + 3х₂

при ограничениях 6х₁ – 3х₂ + х₃ ³ 2

3х₁ + 4х₂ + х₃ ³ 5

х₁ х₂ х₃ ³ 0

в) максимизировать Z = 5х₁ + 6х₂

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

-х₁ + 5х₂ ³ 3

х₁ не ограничена в знаке х₂ ³ 0

г) минимизировать Z = 3х₁ + 4х₂ + 6х₃

при ограничениях х₁ + х₂ ³ 10

х₁ х₃ ³ 0 х₂ £ 0

д) максимизировать Z = х₁ + х₂

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

3х₁ – х₂ = 6

х₁; х₂ не ограничены в знаке.

№ 4.2. Рассмотрим следующую задачу:

минимизировать Z = х₁ + 2х₂ – 3х₃

при ограничениях -х₁ – х₂ + х₃ = 5

12х₁ – 9х₂ + 9х₃ ³ 8

х₁; х₂; х₃ ³ 0

Для решения данной задачи СМ-ом в каждое из 2^х ограничений необходимо ввести искусственные переменные. Покажите, что двойственные задачи, получаемые из прямой задачи в стандартной форме до и после введения искусственных переменных тождественны. Искусственным переменным могут соответствовать только избыточные ограничения двойственной задачи.

№ 4.3. Решите задачу № 4.2. заменив целевую функцию вида:

максимизировать Z = 5х₁ – 6х₂ + 7х₃

Лекция 11:

Определение транспортной модели и ее применение.

Транспортная модель используется при разработке плана перевозок одного вида продукции из нескольких пунктов отправления в пункты назначения. При построении модели используются:

1) величины, характеризующие объём производства в каждом пункте назначения;

2) стоимость перевозки единицы продукции из каждого исходного пункта в каждый пункт назначения.

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

Основное предположение, используемое при построении модели, состоит в том, что величина транспортных расходов на каждом маршруте прямо пропорциональна объему перевозимой продукции. Единицами измерения объема перевозимой продукции м.б. н-р., одна стальная балка, направляемая на строительство моста, или грузовик. В любом случае единица производства и потребления должны соответствовать принятым определением единицам перевозимой продукции.

Исходные пункты. Пункты назначения.

а₁ ® 1 С₁₁ : Х₁₁

1 ®в₁

объем производства спрос

а₂® 2 2 ®в₂

… …

… …

а_m ® m n ®в_n

C_mn: X_mn

Рис 1.

На рис. 1. изображена транспортная модель (ТМ) в виде сети с m исходными пунктами и n пунктами назначения. Исходным пунктом и пунктом назначения соответствуют вершины. Дуга, соединяющая и.п. с п.н., представляют маршрут, по которому перевозится продукция. Количество продукции, производимой в пункте i, обозначено через а_i, а количество продукции, потребляемой в пункте j, - через в_j.

C_ij – стоимость перевозки единицы продукции из i в j.

Пусть х_ij – количество продукции, перевозимой из исходного пункта i в пункт назначения j; тогда задача ЛП транспортного типа в общем виде формулируются следующим образом:

m n

Минимизировать Z = å å C_ij X_ij

i=1 j=1

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

n

å X_ij £ a_i; I = 1,2,…m

j=1 m

å X_ij ³ b_j, j = 1,2,…n

i=1

x_ij ³ 0 для всех i и j.

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

Из представленной модели видно, что суммарный объем производства в исходных пунктах åа_i не должны быть меньше суммарного спроса в пунктах назначения åb_j Если суммарный объем производства равен суммарному спросу (åа_i = åb_j), то модель называется сбалансированной транспортной моделью. Она отличается от вышеприведенной модели лишь тем, что все ограничения превращаются в равенства, то есть

åХ_ij = a_i I = 1,2,…m

åX_ij = b_j j = 1,2,…n

В реальных условиях не всегда объем производства равен спросу или превосходит его. Однако, ТМ всегда можно сбалансировать.

Лекция 12:

Решение транспортной задачи. Метод решения транспортной задачи.

Основные шаги алгоритма.

Шаг 1. Найти начальное допустимое решение.

Шаг 2. Выделить из числа небазисных переменных вводимую в базис. Если все небазисные переменные удовлетворяют условию оптимальности (СМ), закончить вычисления; в противном случае перейти к шагу 3.

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

Рассмотрим алгоритм подробнее. Для пояснения воспользуемся задачей, соответствующей таблице 1. Стоимость перевозки единицы продукции С_ij дана в долларах. Объем производства и величины спроса представляются в количествах изделий.

Таблица 1

Исходные пункты	П у н к т ы н а з н а ч е н и я	Объем производства
	1	2	3	4
	Х11	Х12	Х13	Х14
	Х21	Х22	Х23	Х24
	Х31	Х32	Х33	Х34
	С п р о с

Определение начального решения.

Согласно общему определению ТМ, необходимо, чтобы åа_i = åb_j. Из этого требования следует, что одно уравнение оказывается зависимым, то есть ТМ содержит только m + n – 1 независимых уравнений.

Таким образом, как и в СМ, начальное базисное допустимое решение должно иметь m + n – 1 базисную переменную.

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

Следуя правилу северо-западного угла, начинают с того, что приписывают переменной х₁₁ (Расположить в северо-западном углу таблицы) максимальное значение, допустимое ограничениями на спрос и объем производства. После этого вычерчивают столбец (или строку), фиксируя этим, что остальные переменные вычеркнутого столбца (строки) полагаются равными 0.

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

Применим описанную процедуру к примеру табл. 1.

1. х₁₁ = 5, столбец 1 вычеркивается. Тем самым в 1-ом столбце нельзя больше производить никаких операций. На строку 1 теперь приходится 10 единиц.

2. х₁₂ = 10, строка 1 вычеркивается, а на долю столбца 2 остается 5 единиц.

3. х₂₂ = 5, столбец 2 вычеркивается, а в строке 2 остается 20 единиц.

4. х₂₃ = 15, столбец 3 вычеркивается, в столбце 4 остается 5 единиц.

5. х₂₄ = 5, строка 2 вычеркивается, в столбце 4 остается 5 единиц.

6. х₃₄ = 5, вычеркивается строка 3 или столбец 4. Поскольку остается только один столбец или только одна строка, процесс заканчивается. Полученное базисное решение приведено в табл. 2.

Базисные переменные принимают значения: х₁₁ = 5; х₁₂ = 10; х₂₂ = 5;

х₂₃ = 15; х₂₄ = 5; х₃₄ = 5.

Остальные переменные небазисные, со значениями = 0. Соответствующие транспортные расходы равны 5*10+10*0+5*7+15*9+5*20+5*18=410 долл.

Если одновременно и столбец, и строка удовлетворяют ограничениям, очередная переменная, включаемая, в базисное решение, обязательно имеет нулевое значение. Табл. 3 иллюстрирует эту ситуацию.

					10 5
					5 0

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