Поиск: Рекомендуем: Почему я выбрал профессую экономиста Почему одни успешнее, чем другие Периферийные устройства ЭВМ Нейроглия (или проще глия, глиальные клетки) Категории: Астрономия Биология География Другие языки Интернет Информатика История Культура Литература Логика Математика Медицина Механика Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Транспорт Физика Философия Финансы Химия Экология Экономика Электроника	Главная О нас Популярное ТОП Новые страницы Случайная страница Контакты FAQ ЗАКАЗАТЬ РАБОТУ Глава 3 Специальные разделы математического программирования ⇐ Предыдущая123Следующая ⇒   Упражнение 1.Найдите решение задачи методами: а) графическим; б) Гомори, сделав графическую иллюстрацию. Решение. x 2                       O A C K B G G K G K G E L G K G K G F G K G K G D G K G K G 0 1 2 3 4 5 6 7 8 9 x 1 а) Графический метод. Область допустимых значений OABC без учёта целочисленности представлена на рис. 8а.   Рисунок 8а Перемещаем линию уровня по направлению вектора . Точкой выхода из области допустимых решений является точка B (11/2; 21/4). Полученное оптимальное решение – нецелочисленное. Для нахождения целочисленного решения отметим в области OABC все точки с целочисленными координатами, заменим многоугольник OABC на многоугольник OADEFGKLC, у которого координаты вершин целочисленные, и найдём оптимальное решение для этой области. В данном случае точкой выхода из области допустимых решений является точка (7; 3). Таким образом, . б) Метод Гомори. Сначала решаем задачу симплекс-методом, без учёта целочисленности. Для этого приведем задачу к каноническому виду: (1) Внесём данные задачи в симплекс-таблицу 53. Таблица 53 План Базис Сб bi         di x 1 x 2 x 3 x 4 I x 3             16 x 4                               F =   –4 –3                       Базисным решением на первом шаге будет X 1 = (0; 0; 16; 27) (точка O (0; 0) рис. 8б), при котором целевая функция будет F равна 0, то есть F 1= 0. Для базисного решения X 1 критерий оптимальности не выполнен. Чтобы перейти к построению плана II нужно перевести переменную x 1 в базис, а базисную переменную x 4 – в свободные. Вычисляем элементы новой симплекс-таблицы54. Таблица 54 План Базис Сб bi         di x 1 x 2 x 3 x 4 II x 3       4/3   –1/3 21/4 x 1       2/3   1/3 27/2                 F =     –1/3   4/3                   Базисным решением на втором шаге будет X 2 = (9; 0; 7; 0) (точка C (9; 0) рис. 8б), при котором целевая функция будет F равна 36, то есть F 2= 36. Для базисного решения X 2 критерий оптимальности не выполнен. Чтобы перейти к построению III плана, нужно перевести переменную x 2 в базис, а базисную переменную x 3 – в свободные. Вычисляем элементы новой симплекс-таблицы 55. Таблица 55 План Базис Сб bi         di x 1 x 2 x 3 x 4 III x 2   21/4     3/4 –1/4   x 1   11/2     –1/2 1/2                   F = 151/4     1/4 5/4                   Базисным решением на третьем шаге будет X 3 = (11/2; 21/4; 0; 0) (точка B (11/2; 21/4) рис. 8б), при котором целевая функция будет F равна 151/4, то есть F 3= 151/4. Для базисного решения X 3 выполнен критерий оптимальности, так как в целевой функции нет отрицательных элементов. Кроме того, все коэффициенты при свободных переменных (x 3, x 4) отличны от нуля, следовательно, полученное решение X 3 оптимально и единственно. Таким образом, = (11/2; 21/4; 0; 0), = 151/4. План III – оптимальный, но компоненты оптимального решения нецелочисленные. Для построения отсечения каждая нецелочисленная компонента оптимального решения раскладывается на целую и дробную часть при условии, что дробная часть является строго положительной. Например, , но , где – дробная часть числа a. Из всех нецелочисленных компонент и оптимального решения выбираем компоненту с наибольшей дробной частью (если целые части одинаковые, как в нашем случае, то берём любую из компонент, например, x 1) и выписываем из симплекс-таблицы 55 соответствующее ей уравнение: . Правильное отсечение определяется по формуле: , то есть: Û Û Û Û . (1-ое отсечение) Это ограничение добавляется в качестве дополнительного условия (2) в оптимальную симплекс-таблицу 55, то есть получаем таблицу 56. Таблица 56 План Базис Сб bi           –M di x 1 x 2 x 3 x 4 x 5 r 1 III¢ x 2   21/4     3/4 –1/4       x 1   11/2     –1/2 1/2     ¥ r 1 –M 1/2     1/2 1/2 –1                         F = 151/4     1/4 5/4       M = –1/2     –1/2 –1/2                           Базисным решением в таком случае будет X 3 = (11/2; 21/4; 0; 0; 0) (точка X 3(11/2; 21/4) рис. 8б), при котором целевая функция будет F равна 151/4, то есть F 3= 151/4. Таблица 57 План Базис Сб bi           –M di x 1 x 2 x 3 x 4 x 5 r 1 IV x 2   9/2       –1 3/2     x 1             –1     x 3             –2                         F = 75/2         1/2     M =                                     Для базисного решения X 3 критерий оптимальности целочисленной задачи не выполнен, так как в столбце, соответствующем свободной переменной x 3, в M -функции есть отрицательный элемент (–1/2). Чтобы перейти к построению плана IV, нужно перевести переменную x 3 в базис, а базисную переменную r 1 – в свободные. Вычисляем элементы новой симплекс-таблицы 57. Базисным решением на четвёртом шаге будет X 4 = (6; 9/2; 1; 0; 0) (точка X 4(6; 9/2) рис. 8б), при котором целевая функция будет F равна 75/2, то есть F 4= 75/2. Для базисного решения X 4 критерий оптимальности целочисленной задачи выполнен, так как из базисного решения выведена единственная искусственная переменная r 1, а в целевой функции нет отрицательных элементов. Таким образом, = (6; 9/2; 1; 0; 0) и = 75/2. Однако компоненты оптимального решения нецелочисленные. Единственная нецелочисленная компонента – x 2 = 9/2. Выписываем из симплекс-таблицы 57 соответствующее ей уравнение: . Правильное отсечение имеет вид: или , или . (2-ое отсечение) Это ограничение добавляется в качестве дополнительного условия: , в оптимальную нецелочисленную симплекс-таблицу 57, то есть получаем таблицу 58. Таблица 58 План Базис Сб bi             – M di x 1 x 2 x 3 x 4 x 5 x 6 r 2 IV¢ x 2   9/2       –1 3/2       x 1             –1     ¥ x 3             –2     ¥ r 2 – M 1/2         1/2 –1                           F = 75/2         1/2       M = –1/2         –1/2                             Базисным решением в таком случае будет X 4¢ = (6; 9/2; 1; 0; 0; 0) (точка X 4(6; 9/2) рис. 8б), при котором целевая функция будет F равна 75/2, то есть F 4= 75/2. Для базисного решения X 4¢ критерий оптимальности целочисленной задачи не выполнен, так как в столбце, соответствующем свободной переменной x 5, в M -функции есть отрицательный элемент (–1/2). Чтобы перейти к построению плана V, нужно перевести переменную x 5 в базис, а базисную переменную r 2 – в свободные. Вычисляем элементы новой симплекс-таблицы 59. Базисным решением на пятом шаге будет X 5 = (7; 3; 3;0; 1; 0) (точка X 5(7; 3) рисунка 8б), при котором целевая функция будет F равна 37, то есть F 4= 37. Для решения X 5 критерий оптимальности целочисленной задачи выполнен, так как из базисного решения выведена единственная искусственная переменная r 2, а в целевой функции нет отрицательных элементов. Все компоненты оптимального решения целочисленные, поэтому . Таблица 59 План Базис Сб bi             – M di x 1 x 2 x 3 x 4 x 5 x 6 r 2 V x 2           –1         x 1               –2     x 3               –4     x 5               –2                           F =                   M =                                         Проиллюстрируем графически метод Гомори (рисунок 8б). Мы начинаем с оптимального решения непрерывной задачи линейного программирования = (11/2;21/4), = 151/4. Затем прибавляем 1-ое отсечение: Û x 3 + x 4 ³ 1. Выражая переменные x 3 и x 4 из системы ограничений (1) x 3 = 16 – x 1 – 2 x 2 и x 4 = 27 – 3 x 1 – 2 x 2, получаем, что x 3 + x 4 ³ 1 Û (16 – x 1 – 2 x 2) + (27 – 3 x 1 – 2 x 2) ³ 1 Û Û – 4 x 1 – 4 x 2 ³ – 42 Û x 1 + x 2 £ 21/2. Это отсечение вместе с ограничениями исходной задачи линейного программирования приводит к оптимальному решению = (6; 9/2), = 75/2. После этого прибавляется 2-ое отсечение: Û x 5 ³ 1. Выражая переменную x 5 из системы ограничений (2) и пользуясь ранее полученными выражениями для переменных x 3 и x 4, получаем, что Û x 3 + x 4 ³ 3 Û (16 – x 1 – 2 x 2) + (27 – 3 x 1 – 2 x 2) ³ 3 Û Û – 4 x 1 – 4 x 2 ³ – 40 Û x 1 + x 2 £ 10. Оптимальным решением после второго отсечения является точка в которой .   1-ое отсечение 2-ое отсечение x 2                       O 0 1 2 3 4 5 6 7 8 9 x 1         Рисунок 8а Ответ: . Задача 1. Найдите решение задачи методами: а) графическим; б) Гомори, сделайте графическую иллюстрацию.     1.7.     Упражнение 2.Найдите решение задачи методами: а) графическим; б) ветвей и границ графически.   Решение. а) Графический метод. Область допустимых значений непрерывной задачи представлена на рисунке 9, а множество допустимых решений задачи целочисленного линейного программирования – точками на этом рисунке.   x 2                       B 0 1 2 3 4 5 6 7 8 9 x 1 XZ*     Рисунок 9 Перемещаем линию уровня по направлению вектора (подробнее смотри упражнение 1, глава 1). Точкой выхода из области допустимых решений непрерывной задачи является точка B (16/3; 5), а для целочисленной задачи – (5; 5). Таким образом, . б) Метод ветвей и границ. x 2 0 1 2 3 4 5 6 7 8 9 x 1 X 1   Рисунок 10а Начальная задача линейного программирования (задача 1) получается путём отбрасывания условия целочисленности. Её оптимальным решением будет точка X 1(16/3; 5), в которой F 1 = 109/3 (рис 10а). Это решение не удовлетворяет условия целочисленности. Метод ветвей и границ изменяет пространство решений задачи линейного программирования так, что в конечном счёте получается оптимальное решение задачи целочисленного линейного программирования. Для этого сначала выбирается одна из целочисленных переменных, значение которой в оптимальном решении задачи 1 не является целочисленным. Выбирая x 1, замечаем, что область 5 < x 1 < 6 пространства допустимых решений задачи 1 не содержит целочисленных значений переменной x 1, и, следовательно, может быть исключена из рассмотрения как бесперспективная. Это эквивалентно замене исходной задачи 1 двумя новыми задачами линейного программирования (задача 2 и задача 3). задача 1 задача 2 задача 3 x 2 0 1 2 3 4 5 6 7 8 9 x 1 X 2   Рисунок 10б	x 2 0 1 2 3 4 5 6 7 8 9 x 1 X 3   Рисунок 10в
X 2(5; 21/4) и F 2 = 143/4;	X 3(6; 3) и F 3 = 33.

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

На рисунках 10б и 10в изображены пространства допустимых решений задач 2 и 3. Оптимальное решение исходной задачи находится в пространстве допустимых решений либо задачи 2, либо задачи3, следовательно, обе задачи должны быть решены.

Оптимальное решение задачи 2 не является целочисленным, поэтому обращаемся к целочисленной переменной x ₂, значение которой в оптимальном решении задачи 2 не является целочисленным. Так как в области 5 < x ₁ < 6 пространства допустимых решений задачи 1 не содержит целочисленных значений переменной x ₂, заменяем задачу 2 двумя новыми задачами линейного программирования (задача 4 и задача 5), которые обе должны быть решены.

задача 2
задача 4	задача 5
x 2 0 1 2 3 4 5 6 7 8 9 x 1 X 4     Рисунок 10г	x 2 0 1 2 3 4 5 6 7 8 9 x 1 X 5     Рисунок 10д
X 4(5; 5) и F 4 = 5;	X 5(4; 6) и F 5 = 34.

На рисунках 10г и 10д изображены пространства допустимых решений задач 4 и 5.

Оптимальные решения задач 4 и 5 целочисленные, поэтому дальнейшего ветвления не требуется.

Таким образом, схематически:

1.
2.	3.
4.	3.

Ответ:

Задача 2. Найдите решение задачи методами:

а) графическим;

б) ветвей и границ графически.

2.7.

Упражнение 3. Параметрическое программирование Найдите решение задачи параметрического программирования графическим методом.

Решение.

Чтобы найти решение задачи, построим многоугольник решений (рис. 11), определяемый системой ограничений:

Ответ:

если , то X * = (0; 5), F _max = 65,

если t = 1/5, то X * = (4–4a; 4+a), aÎ[0; 1], F _max = 64,

если , то X * = (4; 4), F _max = 64,

если t = 23/3, то X * = (6–2a; 4a), aÎ[0; 1], F _max = 64,

если , то X * = (6; 0), F _max = 18 + 6 t.

Задача 3. Найдите решение задачи параметрического программирования графическим методом.

3.7.

Упражнение 4. Найдите решение задачи параметрического программирования симплексным методом.

Решение.

Решим задачу симплекс-методом (подробно этот метод был описан в упражнении 2, глава 1). Для этого приведем задачу к каноническому виду:

Внесём данные задачи в симплекс-таблицу 60.

Таблица 60

Базисным решением в таком случае будет X ₁ = (0; 0; 32; 30), при котором целевая функция будет F равна 0, то есть F ₁= 0.

Для базисного решения X ₁ критерий оптимальности не выполнен, так как в столбце, соответствующем свободной переменной x ₂, в целевой функции есть отрицательный элемент (–11). Чтобы перейти к построению плана II, нужно перевести переменную x ₂ в базис, а базисную переменную x ₃ – в свободные.

Вычисляем элементы новой симплекс-таблицы 61.

Таблица 61

Базисным решением в таком случае будет X ₂ = (0; 8; 0; 14), при котором целевая функция будет F равна 88, то есть F ₂= 88.

Для базисного решения X ₂ при проверке критерия оптимальности возможны три случая:

а) 29/4 – t > 0 Û t < 29/4, тогда решение X ₂ является оптимальным и единственным;

б) 29/4 – t = 0 Û t = 29/4, тогда решение X ₂ является оптимальным, но не единственным, и следует продолжать поиск;

в) 29/4 – t < 0 Û t > 29/4, тогда решение X ₂ не оптимальное, и поиск решения продолжается.

Чтобы в случаях б) и в) перейти к построению плана III, нужно перевести переменную x ₁ в базис, а базисную переменную x ₄ – в свободные.

Вычисляем элементы новой симплекс-таблицы 62.

Таблица 62

План	Базис	Сб	bi	1+ t				di
x 1	x 2	x 3	x 4
III¢	x 2					5/14	–3/14	14
x 1	1+ t				–1/7	2/7	¥
F	=	59+4 t

Базисным решением в таком случае будет X ₃ = (4; 5; 0; 0), при котором целевая функция будет F равна (59+4 t), то есть F ₃= 59+4 t.

Для базисного решения X ₃ при проверке критерия оптимальности возможны четыре случая:

а) t = 29/4, тогда решение X ₃ является оптимальным, но не единственным. Общий вид оптимального решения можно записать:

X * = a×(0; 8; 0; 14) + (1–a)×(4; 5; 0; 0) = (4–4a; 5+3a; 0; 14a), aÎ[0; 1],

при этом F _max = 88;

б)

,

тогда решение X ₃ является оптимальным и единственным;

в) 53/14 – 1/7· t = 0 Û t = 53/2, тогда решение X ₃ является оптимальным, но не единственным, и следует продолжать поиск решения;

г) t > 53/2, тогда решение X ₃ не оптимальное, и поиск решения продолжается.

Чтобы в случаях в) и г) перейти к построению плана IV, нужно перевести переменную x ₃ в базис, а базисную переменную x ₂ – в свободные.

Вычисляем элементы новой симплекс-таблицы 63.

Таблица 63

План	Базис	Сб	bi	1+ t				di
x 1	x 2	x 3	x 4
IV²	x 3				14/5		–3/5
x 1	1+ t			2/5		1/5
F	=	6+6 t

Базисным решением в таком случае будет X ₄ = (6; 0; 14; 0), при котором целевая функция будет F равна (6+6 t), то есть F ₄= 6+6 t.

Для базисного решения X ₄ при проверке критерия оптимальности возникают два случая:

а) t = 53/2, тогда решение X ₄ является оптимальным, но не единственным. Общий вид оптимального решения можно записать:

X * = a×(4; 5; 0; 0) + (1–a)×(6; 0; 14; 0) = (6–2a; 5a; 14–14a; 0), aÎ[0; 1],

при этом F _max = 165;

б)

тогда решение X ₄ является оптимальным и единственным.

Ответ:

если , то X * = (0; 8; 0; 14), F _max = 88,

если t = 29/4, то X * = (4–4a; 5+3a; 0; 14a), aÎ[0; 1], F _max = 88,

если , то X * = (4; 5; 0; 0), F _max = 59 + 4 t,

если t = 53/2, то X * = (6–2a; 5a; 14–14a; 0), aÎ[0; 1], F _max = 165,

если , то X * = (6; 0; 14; 0), F _max = 6 + 6 t.

Задача 4. Найдите решение задачи параметрического программирования симплексным методом.

4.7.

Упражнение 5. Найдите решение задачи параметрического программирования симплексным методом.

Решение.

Решим задачу симплекс-методом. Для этого приведем задачу к каноническому виду:

Внесём данные задачи в симплекс-таблицу 64.

Таблица 64

Базисным решением в таком случае будет X ₁ = (0; 0; 35– t; 14– t), при котором целевая функция будет F равна 0, то есть F ₁= 0.

Для базисного решения X ₁ критерий оптимальности не выполнен, так как в целевой функции есть отрицательные элементы. Чтобы перейти к построению плана II нужно перевести переменную x ₁ в базис.

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

а) Û –34 £ t £ –28/5, тогда в свободные переводим переменную x ₃ (план II¢);

б) Û –28/5 < t £ 13, тогда в свободные переводим переменную x ₄ (план II²).

Вычисляем элементы новой симплекс-таблицы 65 в случае а).

Таблица 65

Базисным решением в таком случае будет

X ₂¢ = (35/3 + 1/3 t; 0; 0; –28/3 – 5/3 t),

при котором целевая функция будет F равна 35 + t, то есть F ₂¢= 35 + t.

Для решения X ₂¢ выполнен критерий оптимальности, так как в целевой функции нет отрицательных элементов. Кроме того, все коэффициенты при свободных переменных (x ₂, x ₃) отличны от нуля, следовательно, полученное решение X ₂¢ оптимально и единственно.

Вычисляем элементы новой симплекс-таблицы 66 в случае б).

Таблица 66

Базисным решением в таком случае будет X ₂² = (7–1/2 t; 0; 14 + 5/2 t; 0), при котором целевая функция будет F равна 21 – 3/2 t, то есть F ₂²= 21 – 3/2 t.

Для базисного решения X ₂² критерий оптимальности не выполнен, так как в целевой функции есть отрицательные элементы. Чтобы перейти к построению плана III нужно перевести переменную x ₂ в базис.

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

а)

тогда в свободные переводим переменную x ₃ (план III¢);

б)

тогда в свободные переводим переменную x ₁ (план III²).

Вычисляем элементы новой симплекс-таблицы 67 в случае а).

Таблица 67

Базисным решением в таком случае будет X ₃¢ = (5 – 6/7 t; 4 + 5/7 t; 0; 0), при котором целевая функция будет F равна 23 – 8/7 t, то есть F ₃¢= 23 – 8/7 t.

Таблица 68

Для решения X ₃¢ выполнен критерий оптимальности, так как в целевой функции нет отрицательных элементов. Кроме того, все коэффициенты при свободных переменных (x ₃, x ₄) отличны от нуля, следовательно, полученное решение X ₃¢ оптимально и единственно.

Вычисляем элементы новой симплекс-таблицы 68 в случае б).

Базисным решением в таком случае будет X ₃² = (0; 14 – t; –35 + 6 t; 0), при котором целевая функция будет F равна 28 – 2 t, то есть F ₃²= 28 – 2 t.

Для решения X ₃² выполнен критерий оптимальности, так как в целевой функции нет отрицательных элементов. Кроме того, все коэффициенты при свободных переменных (x ₁, x ₄) отличны от нуля, следовательно, полученное решение X ₃² оптимально и единственно.

Ответ:

если , то X * = (35/3 + 1/3 t; 0; 0; –28/3 – 5/3 t), F _max = 35 + t,

если , то X * = (5 – 6/7 t; 4 + 5/7 t; 0; 0), F _max = 23 – 8/7 t,

если , то X * = (0; 14 – t; –35 + 6 t; 0), F _max = 28 – 2 t.

Задача 5. Найдите решение задачи параметрического программирования симплексным методом.

5.7.

Дата добавления: 2017-02-25; Мы поможем в написании ваших работ!; просмотров: 339 | Нарушение авторских прав

Лучшие изречения:

Два самых важных дня в твоей жизни: день, когда ты появился на свет, и день, когда понял, зачем. © Марк Твен
==> читать все изречения...

1476 - | 1359 -