3. Решите следующие задачи ЛП методом решения задач с ограниченными переменными.
a) Минимизировать z = бдс, - 2х2 - Зх3 при ограничениях
2xt + 4х2 + 2х, < 8, х1-2х2 + 3х3<7, О < х, < 2, 0 < х2 < 2, 0 < х3 < 1.
b) Максимизировать z = Зхх + Ъх2 + 2х3 при ограничениях
х1 + 2х2 + 2х3<ю,
2х, + 4х2 + 3х3< 15, О < х, < 4, 0 < х2 < 3, 0 < х3 < 3.
4. В следующих задачах некоторые переменные имеют положительные нижние границы. Решите эти задачи методом решения задач с ограниченными переменными.
a) Максимизировать z = 3*, + 2х2 - 2х3 при ограничениях
2х1 + х2 + х3 < 8, х, + 2х2 - х3 > 3, хЗ, 0<х2<3, 2<х3.
b) Максимизировать z = xl + 2х2 при ограничениях
-Xj + 2х2>0, Зх, +2х2< 10, -х, + х2< 1, lxe.Oxl.
c) Максимизировать z = 4х, + 2х2 + 6х3 при ограничениях
4х, - х2 < 9, -х, +х2 + 2х3<8, -Зх1 + х2 + 4х3<12, 1<х,<3,0<х2<5, 0<х3<2.
5. Рассмотрим матричное представление задачи с ограниченными переменными. Разобьем вектор X на две части (Хг, Хц), где элементами вектора Хц являются переменные, к которым в процессе выполнения алгоритма будет применена подстановка, эквивалентная их верхнему пределу. Тогда задачу ЛП с ограниченными переменными можно записать следующим образом.
f 7
1 -с; -с,Л
0 D, D.
Пусть В (и Хв) - базисное решение текущей симплексной итерации, полученное после подстановки Хц = U„ - Хи, где U„ - подмножество элементов вектора значений верхних границ U, соответствующего переменным Хц. Покажите, что в данном случае симплекс-таблица имеет следующий вид.
Базис | | | Решение |
| CSB 1DZ-CZ | - СвВ 1Du + Си | CsB-1 ь + с„иц |
| B"1D; | -в-1ои | В"1 Ь |
Здесь b = b - DUUU.
6. В задаче из примера 7.3.1 выполните следующее.
a) На этапе итерации 1, используя матричные представления, проверьте, что Хв = (х4, х1)г = (5/2,3/2)г.
b) На этапе итерации 2 покажите, как на основе исходных данных задачи можно вычислить В"1. Затем, используя матричные представления, проверьте вычисленные в примере значения переменных xt и х,.
7. Решите задачу из упражнения 3.1 с помощью модифицированного (использующего матричные представления) симплекс-метода.
8. Двойственный симплекс-метод решения задач с ограниченными переменными. Двойственный симплекс-метод (раздел 4.4) также можно модифицировать для учета явных ограничений, налагаемых на переменные. Для этого после подстановок xt = u;- xt (uj - верхняя граница переменной х-, если uf
бесконечна, заменяем ее достаточно большим положительным числом М) исходная задача записывается в двойственной форме. Далее выполняются следующие действия.
Шаг 1. Если значение какой-либо базисной переменной (Хв), превышает ее верхнюю границу, выполняем замену (ХД = (UB), - (Х6)..
Шаг 2. Если базисное решение допустимо, вычисления заканчиваются.
В противном случае среди базисных переменных определяем исключаемую из базиса переменную хг как имеющую наибольшее отрицательное значение.
Шаг 3. В соответствии с условием оптимальности двойственного симплекс-метода определяем вводимую в базис переменную.
Шаг 4. Выполняем пересчет базиса. Переходим к шагу 1.
Примените описанный алгоритм к следующим задачам.
а) Минимизировать г = -Зхг - 2хг + 2х3
при ограничениях
2х, + х2 + х3 < 8, -х1 + 2х2 + х3>13, 0<х,<2, 0<х2<3, 0<х3<1.
Ь) Максимизировать г = хг + 5х2 - 2х3 при ограничениях
4*! + 2х2 + 2х3 < 26, + Здс2 + 4х3> 17, О < х, < 2, 0 < х2 < 3, 0 < х3 (х3 сверху не ограничена).
7.4. МЕТОД ДЕКОМПОЗИЦИИ
Рассмотрим разработку производственного плана предприятия, состоящего из нескольких подразделений. Хотя каждое подразделение имеет собственные производственные возможности и соответствующие ограничения, производственные планы отдельных подразделений обобщаются на уровне управления предприятием. Таким образом, результирующая модель рассматриваемого предприятия будет содержать ограничения двух типов: общие, соответствующие уровню всего предприятия, и независимые, отображающие производственные ограничения отдельных подразделений. На рис. 7.5 показана структура ограничений для п подразделений. Отсутствие общих ограничений означает, что все подразделения независимы.
Метод декомпозиции предлагает эффективный вычислительный алгоритм решения задач со структурой ограничений, подобной показанной на рис. 7.5, путем разбиения исходной задачи на п подзадач, которые решаются независимо друг от друга. Вместе с тем отметим, что применение этого метода особенно оправдано, когда расчеты выполняются на вычислительном устройстве с ограниченной скоростью выполнения операций и ограниченным объемом памяти. Сегодня, когда вычислительная техника имеет огромную (по сравнению с недавним прошлым) производительность, необходимость в методе декомпозиции не так очевидна. Несмотря на это мы рассмотрим данный метод, поскольку он представляет интерес в теоретическом плане.
Общие ограничения
Независимые ограничения
Подразделение 1
Подразделение 2
Подразделение л
Рис. 7.5. Структура декомпозиции задачи линейного программирования
Математическую модель, к которой применяется метод декомпозиции, запишем в следующем виде.
Максимизировать г = С;Х, + С2Х2 + ... + СлХп
при ограничениях