Решить предложенную задачу симплексным методом с искусственным базисом.
На двух линиях с заданным объемом перевозок можно использовать суда трех типов. Объем перевозок, производительность судов и их эксплуатационные расходы приведены в табл. 1
Построить план расстановки судов по линиям, обеспечивающим минимум эксплуатационных расходов, при условии выполнения заданного на линиях объема перевозок.
Тип судна Производительность судов, млн тонно-миль/сут
Эксплуатационные расходы, ты сруб/сут Эксплуатационный период, сут
1-я линия 2-я линия 1-я линия 2-я линия
1
2
3 12
12
8 14
16
14 12
10
20 10
12
10 300
300
300
Заданный объем перевозок, млн тонно-миль 4000 4500
Решение
Пусть xij доли эксплуатационного периода i -го судна в j – ом районе промысла. Тогда целевая функция z1 , обозначающая суммарные эксплуатационные расходы, будет
z1=300(12x11+10x12+10x21+12x22+20x31+10x32)→min
Ограничения:
1)Сумма долей эксплуатационного периода, отведенных для работы судов данного типа в обоих районах промысла, не может превышать единицы:
x11+x12≤1x21+x22≤1x31+x32≤1
2) Записываем ограничения на выполнение объема перевозок из каждого района промысла
300(12x11+12x21+8x31)=400030014x12+16x22+14x32=4500xij≥0(i=1;3, j=1;2
Введем целевую функцию: z=z1/300, а так же сократим на 300 неравенства второй группы, запишем модель задачи в следующем виде:
z=12x11+10x12+10x21+12x22+20x31+10x32→min
x11+x12≤1x21+x22≤1x31+x32≤1
(12x11+12x21+8x31)=40/314x12+16x22+14x32=15xij≥0(i=1;3, j=1;2
переход к канонической форме:
x11+x12+y1 = 1
x21+x22+y2 = 1
x31+x32+y3 = 1
12x11+12x21+8x31 = 131/3
14x12+16x22+14x32 = 15
Введем искусственные переменные x:
x11+x12+y1 = 1
x21+x22+y2 = 1
x31+x32+y3 = 1
12x11+12x21+8x31 +y4= 131/3
14x12+16x22+14x32 +y5= 15
Для постановки задачи на минимум целевую функцию запишем так:
z=12x11+10x12+10x21+12x22+20x31+10x32+My4+My5→ min
Из уравнений выражаем искусственные переменные:
y4= 131/3-12x11-12x21-8x31
y5 = 15-14x12-16x22-14x32
которые подставим в целевую функцию:
z = (12-12M)x11+(10-14M)x12+(10-12M)x21+(12-16M)x22+(20-8M)x31+(10-14M)x32+(281/3M) → min
Базисные переменные : y1,y2,y3,y4,y5
Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,0,0,0,0,1,1,1,131/3,15). Базисное решение называется допустимым, если оно неотрицательно.
Базис B x11 X12 X21 X22 X31 X32 Y1 Y2 Y3 Y4 Y5
Y1 1 1 1 0 0 0 0 1 0 0 0 0
Y2 1 0 0 1 1 0 0 0 1 0 0 0
Y3 1 0 0 0 0 1 1 0 0 1 0 0
Y4 40/3 12 0 12 0 8 0 0 0 0 1 0
Y5 15 0 14 0 16 0 14 0 0 0 0 1
z 281/3M -12+12M -10+14M -10+12M -12+16M -20+8M -10+14M 0 0 0 0 0
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
Базис B x11 X12 X21 X22 X31 X32 Y1 Y2 Y3 Y4 Y5 min
Y1 1 1 1 0 0 0 0 1 0 0 0 0 -
Y2 1 0 0 1 1 0 0 0 1 0 0 0 1
Y3 1 0 0 0 0 1 1 0 0 1 0 0 -
Y4 40/3 12 0 12 0 8 0 0 0 0 1 0 -
Y5 15 0 14 0 16 0 14 0 0 0 0 1 15/16
z 281/3M -12+12M -10+14M -10+12M -12+16M -20+8M -10+14M 0 0 0 0 0
Пересчет симплекс-таблицы.
Базис B x11 X12 X21 X22 X31 X32 Y1 Y2 Y3 Y4 Y5 min
Y1 1 1 1 0 0 0 0 1 0 0 0 0 -
Y2 1/16 0 -7/8 1 0 0 -7/8 0 1 0 0 -1/16 1/16
Y3 1 0 0 0 0 1 1 0 0 1 0 0 -
Y4 40/3 12 0 12 0 8 0 0 0 0 1 0 10/9
X22 15/16 0 7/8 0 1 0 7/8 0 0 0 0 1/16 -
z 111/4+131/3M -12+12M 1/2 -10+12M 0 -20+8M 1/2 0 0 0 0 3/4-M
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты. Пересчет симплекс-таблицы.
Базис B x11 X12 X21 X22 X31 X32 Y1 Y2 Y3 Y4 Y5 min
Y1 1 1 1 0 0 0 0 1 0 0 0 0 1
X21 1/16 0 -7/8 1 0 0 -7/8 0 1 0 0 -1/16 -
Y3 1 0 0 0 0 1 1 0 0 1 0 0 -
Y4 151/12 12 21/2 0 0 8 21/2 0 -12 0 1 3/4 151/144
X22 15/16 0 7/8 0 1 0 7/8 0 0 0 0 1/16 -
z 117/8+127/12M -12+12M -81/4+101/2M 0 0 -20+8M -81/4+101/2M 0 10-12M 0 0 1/8-M
Текущий опорный план неоптимален
Базис B x11 X12 X21 X22 X31 X32 Y1 Y2 Y3 Y4 Y5 min
X11 1 1 1 0 0 0 0 1 0 0 0 0 -
X21 1/16 0 -7/8 1 0 0 -7/8 0 1 0 0 -1/16 -
Y3 1 0 0 0 0 1 1 0 0 1 0 0 1
Y4 7/12 0 -3/2 0 0 8 21/2 -12 -12 0 1 3/4 1/18
X22 15/16 0 7/8 0 1 0 7/8 0 0 0 0 1/16 15/14
z 237/8+7/12M 0 33/4-11/2M 0 0 -20+8M -81/4+101/2M 12-12M 10-12M 0 0 1/8-M
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты
Задать вопрос
на новый заказ в Автор24.
