Задание (Транспортная задача)
Имеются 3 пункта поставки однородного груза А1, А 2 , А 3 и 5 пунктов по- требления этого груза В 1 , В 2 , В 3 , В 4 , В 5 . На пунктах А I ( I = 1,2,3 ) груз находится соответственно в количествах а1, а 2 , а 3 условных единиц. В пункты В J ( J= 1,2,3,4,5 ) требуется доставить соответственно b J единиц груза. Стоимость пере- возки единицы груза (с учетом расстояний) из А I в В J определена матрицей С={c ij }. Решить задачу тремя методами (северо-западного угла, минимальной стоимости и методом Фогеля) и найти такой план закрепления потребителей и поставщиков, чтобы общие затраты на перевозки были минимальны. 1). а1= 200, а 2 =170, а 3 = 180, b1= 100, b 2 = 70, b 3 = 180, b 4 = 150, b 5 = 50 2). а1= 120, а 2 = 250, а 3 = 150, b1= 90, b 2 = 70, b 3 = 160,
8 12÷ è11 5 7 13 12÷
3). а1= 280, а 2 =350, а 3 = 250, b1=130, b 2 =100, b 3 = 300, b 4 = 270, b 5 = 80 4). а1= 250, а 2 = 270, а 3 = 150, b1= 100, b 2 = 170, b 3 = 160, b 4 = 170, b 5 = 70
7 10 14 ÷ è10 11 13 7 20÷
b1=100, b 2 =180, b 3 = 160, b 4 = 160, b 5 = 80 6). а1= 100, а 2 = 140, а 3 = 150, b1= 60, b 2 = 50, b 3 = 80, b 4 = 160, b 5 = 40
14 10÷ è 9 6 5 3 ø
b1= 105, b 2 = 75, b 3 = 50, b 4 = 145, b 5 = 75 8). а1= 200, а 2 = 250, а 3 = 160, b1= 120, b 2 = 120, b 3 = 100, b 4 = 210, b 5 = 60
7 10÷ è12 15 16 13 21÷
b1=310, b 2 =250, b 3 = 150,
10). а1= 300, а 2 = 360, а 3 = 400, b1= 150, b 2 = 350, b 3 = 300,
7 10 13 22÷ è10 7 11 15 20÷
11). а1=270, а 2 = 390, а 3 = 290, b1=150, b 2 =100, b 3 = 250, b 4 = 340, b 5 = 110 12). а1= 380, а 2 = 450, а 3 = 420, b1= 230, b 2 = 200, b 3 = 400, b 4 = 270, b 5 = 230
9 15 7 25÷ è16 8 10 12 17 ÷
b1=110, b 2 =100, b 3 = 200, b 4 = 140, b 5 = 80, 14). а1= 250, а 2 = 190, а 3 = 200, b1= 180, b 2 = 100, b 3 = 130, b 4 = 140, b 5 = 90
è 2 9 6 5 ø
b1=100, b 2 =150, b 3 = 130, b 4 = 120, b 5 = 80 16). а1= 310, а 2 = 250, а 3 = 240, b1= 290, b 2 = 110, b 3 = 170, b 4 = 130, b 5 = 100
3 5 ø è 6 4 9 5 ÷
b1=110, b 2 =100, b 3 = 220, b 4 = 180, b 5 = 90 18). а1= 170, а 2 = 230, а 3 = 180, b1= 95, b 2 = 130, b 3 = 120,
è 8 5 7 6 ÷
19). а1=260, а 2 = 190, а 3 = 120, b1=100, b 2 = 120, b 3 = 200 b 4 = 80, b 5 = 70 20). а1= 330, а 2 = 300, а 3 = 270, b1= 120, b 2 = 200, b 3 = 310, b 4 = 190, b 5 = 80
è 7 14 10 11 ÷
b1=160, b 2 =140, b 3 = 200, b 4 = 100, b 5 = 110 22). а1= 300, а 2 = 260, а 3 = 230, b1= 140, b 2 = 250, b 3 = 150, b 4 = 160, b 5 = 90
è 7 13 5 6 ø
b1= 60, b 2 = 70, b 3 = 80, b 4 = 90, b 5 = 100 24). а1= 200, а 2 = 130, а 3 = 250, b1= 90, b 2 = 100, b 3 = 160, b 4 = 150, b 5 = 80
è 6 7 10 5 ÷
b1=120, b 2 =180, b 3 = 210, b 4 = 90, b 5 = 100, 26) а1= 200, а 2 = 170, а 3 = 180, b1= 100, b 2 = 70, b 3 = 180,
è10 3 5 8 12÷
27). а1=250, а 2 = 190, а 3 = 200, b 1 = 180, b 2 = 100, b 3 = 130, b 4 = 140, b 5 = 90 28). а1= 200, а 2 = 250, а 3 = 160, b1= 120, b 2 = 120, b 3 = 100, b 4 = 210, b 5 =
6 5 ø è12 15 16 13 21÷
b1 = 100, b 2 = 180, b 3 = 160, b 4 = 160, b 5 = 80 30) 1 = 270, а 2 = 390, а 3 = 290, b1= 150, b 2 = 100, b 3 = 250, b 4 = 340, b 5 = 110
ç
9 15 7 ÷
Задание 3. Дана целевая функция и нелинейная система ограничений. Графическим мето- дом найти глобальные экстремумы (максимум и минимум) задачи.
Задание 4 Для задачи с нелинейной целевой функцией и линейной системой ограничений графическим методом найти максимум и минимум.
Задание 5. Найти точки условного экстремума функции U при заданных ограничениях ме- тодом Лагранжа.
V. ЛЕКЦИОННЫЙ МАТЕРИАЛ.
Линейное программирование. Симплексный метод
Пусть требуется найти max Z,
n Z = åc j x j , (1) j = 1
при условиях:
ìx1 ï ïx2 í + a1m+1 xm+1 + a 2m+1 xm+1 + ... + a1nxn + ... + a 2nxn = b1, = b2,
(2) ï. . . . . . . . . . . . . . . . . . îïx m + a mm+1 xm+1 + ... + a mnxn = bm ,
xj ³ 0 (j=1..n), где aij, cj bi - постоянные числа (bi > 0 , m < n ).
Введя векторы:
æ 1ö æ 0ö æ 0ö æ a1m+1 ö æ a1nö æ b1 ö ç 0÷ ç 1÷ ç 0÷ ç a ÷ ç a ÷ ç b ÷ A1= ç ÷ ,A2= ç ÷ ,...,Am= ç ÷ , Am+1= ç 2m+1 ÷ ,...,An= ç 2n ÷ ,A0= ç 2 ÷ , ç...÷ ç...÷ ç...÷ ç ... ÷ ç ... ÷ ç ... ÷ ç ÷ ç ÷ ç ÷ ç ÷ ç ÷ ç ÷ è 0ø è 0ø è 1ø èamm+1 ø èamnø è bmø
можно записать систему (2) в векторной форме : x1 A1+ x2A2+ ... xm Am + xm+1Am+1+ ... + xn An= A0. (3) Нетрудно заметить. что справедливо равенство: b1A1 + b2A2+ ... +bmAm = A0, а это означает, что X0= (b1,b2,...,bm,0,..,0) является решением системы (2) или начальным опорным планом задачи. Этот план определяется системой базисных векторов A1,A2,...,Am m-мерного пространства. Каждый вектор Aj может быть представлен в виде линейной комбинации векторов этого базиса: Aj=
(j=0..n). m åxij Ai i = 1
Положим Zj= Cб Aj= m åci xij i = 1 , где Cб = (c1, c2, ...,cm) - ценовoй вектор базиса и
Dj = Zj- cj (xij- компоненты вектора Aj в данном базисе). Оптимальность опорного плана и последующие шаги решения задачи опре- деляются следующими теоремами: Теорема 1.Опорный план X=(x1, x2,..,xm,0,...,0) задачи линейного програм- мирования (1)-(2) является оптимальным, если Dj³0 для всех j (j=1,...,n). Теорема 2. Если для некоторого j=k Dj<0 и среди чисел aik (i=1,..,m) нет по- ложительных чисел, то целевая функция задачи не ограничена на множестве ее планов. Теорема 3.Если опорный план X задачи не вырожден и Dk < 0, но среди чи- сел aik есть положительные (не все aik£ 0 ), то существует опорный план X1такой, что Z(X1)>Z(X). Исходные данные и процесс вычисления (переход к новому опорному плану) удобно записывать в табл. 1
Таблица 1
Базисный вектор Ei(i=1,...,m) совпадает с As, если ais = 1, а все остальные компоненты равны нулю. Соответствующий коэффициент csпри xs целевой функ- ции записан в Cб. Значения Dj=Zj-cj=AjCб-cj(j=0,...,n) записаны в (m + 1)-й строке. В столбце A0 записаны свободные члены biсистемы (8) в порядке, соответствующем каждому базисному вектору. Компоненты вектора A0и составляют опорный план (bi>0); в (m+1)-й строке этого столбца получаем значение целевой функции Z0=CбA0при этом плане. Приведем алгоритм решения задачи симплекс-методом. 1. Находят опорный план X0 = (b1, b2,...,bm, 0,..., 0). 2. Составляют симплекс-таблицу типа 1. 3. Выясняют, имеется ли хотя бы одно Dj<0. Если нет таких чисел, то найденный опорный план будет оптимальным. В противном случае устанавливают либо неразрешимость задачи (все компоненты вектора Ajнеположительны), либо переходят к новому опорному плану. 4.
j < 0, a
Q0 = bk / aks = min (bi / ais) , ais > 0. Элемент aksявляется разрешающим, который и опре- i
деляет базисный вектор Ek, подлежащий замене вектором As. 5. В новом базисе таблица пересчитывается так: а) все элементы k-ой строки, начиная со столбца А0, делятся на aks; б) все элементы столбца As заменяются нулями, кроме aks=1. Координаты остальных базисных векторов остаются неизменными;
(j ¹ s) определяется по формуле:
a*= 1 (a a - a a )
akjais = a -
(4) ij ks ks ij kj is ij a ks
г) (m+1)-я строка вычисляется аналогично:
1 aks (aksD j - a kjDs) = D j - a kj a ks Ds . 6.
³ 0 , то полученный план оптимальный (составляется из ком-
понент Ao) и Zmax = D0. В противном случае возвращаемся к п.4 алгоритма. После
конечного числа итераций получим оптимальный план или докажем отсутствие та- кого плана. Задача 1.1. Решить симплекс-методом задачу: для изготовления различных изделий А, В, С предприятие использует три вида сырья. Нормы расхода сырья на производство одного изделия каждого вида, цена одного изделия А, В и С, а также общее количество сырья каждого вида, которое может быть использовано пред- приятием, приведены в табл.2. Изделия А, В и С могут производиться в любых со- отношениях (сбыт обеспечен), но производство ограничено выделенным предприятию сырьем каждого вида. Составить план производства изделий, при котором общая стоимость всей произведенной предприятием продукции является максимальной. Таблица 2.
Решение. В векторной форме будем иметь x1A1 + x2A2+ x3A3+ x4A4 + x5A5 + x6A6= A0, где
æ18ö
æ15ö
æ 1ö
A1= ç 6 ÷ ,A = ç 4 ÷ , A = ç 8 ÷ , A = ç ÷ ,A = ç ÷ ,A = ç ÷ , A = ç ÷ ç ÷ 2 ç ÷ ç ÷ ç ÷ 3 ç ÷ ç ÷ 4 ç ÷ ç ÷ 5 ç ÷ ç ÷ 6 ç ÷ ç ÷ 0 ç ÷ ç ÷ è 5 ø è 3 ø è 3 ø è 0ø è 0ø è 1ø è180ø
Среди векторов A4, A5, A6- единичные, их принимаем за базисные и, поло- жив x1=x2=x3=0, получаем начальный опорный план: X0=(0, 0, 0 ,360, 192, 180). Составляем симплексную таблицу для 1-ой итерации и вычисляем Z0=CбA0=0, D1=Z1-c1=0-9=-9, D2=Z2-c2=-10, D3=Z3-c3=-16 и для векторов базиса D4=D5=D6=0. Как видно, основные переменные x1, x2, x3 равны нулю, т.е. производ- ство не начато, прибыль Z0=0, и потому план X0не является оптимальным. Нахо- дим в каждом из столбцов A1, A2, A3 bi Q j = mi n i aij (j=1, 2, 3)
192 , 180ö ÷ = 20 = b1 и Q1D1= -20 × 9 = -180 , i è 18 6 5 ø a11
192 , 180ö ÷ = 24 = b1 и Q2D2= -24 ×10 = -240 , i è 15 4 3 ø a12
192 , 180ö ÷ = 24 = b 2 и Q3D3= -24 ×16 = -384 . i è 12 8 3 ø a 23
Очевидно mi n (Q j D j ) = j Q3D3 = - 384 .
Поэтому вектор A3подлежит включению в базис вместо A5( Q3 = b2/a23, разрешающий элемент a23). Составляем новую таблицу в базисе векторов A4, A3, A6. Для удобства поме- стим все итерации последовательно в одну табл. 3. Таблица 3
(0.009 сек.) |