Контрольная работа по "Линейное программирование"

Линейное программирование

Задание 1. Найти минимум и максимум целевой функции f(x1,x2) графическим методом.

f=6x1-4x2

-x1+5x2≥0x1+5x2≤14x1≤6x1+x2≥2-3x1+2x2≤6x1≥0,  x2≥0

РЕШЕНИЕ

Построим область допустимых решений задачи.

На одном графике построим прямые:

-x1+5x2=0,  точки 5;1 и (0;0)x1+5x2=14,  точки -1;3 и (4;2)x1=6                                                            x1+x2=2,  точки 1;1 и (2;0)-3x1+2x2=6,  точки 0;3 и (-2;0)x1=0,  x2=0                                              

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

[pic 1]

Для нахождения минимального значения целевой функции f=6x1-4x2 построим одну из ее линий уровня 0=6x1-4x2 (чёрным цветом) и вектор градиента n=(6,-4). Двигаем линию уровня параллельно самой себе против направления градиента (направления убывания функции), пока не достигнем крайней точки области. Как видно из рисунка, крайняя точка области – это точка пересечения прямой x1+5x2=14 и оси ординат, т.е. точка (14/5;0). Минимальное значение целевой функции fmin=6*145-4*0=16.8.

Для нахождения максимального значения целевой функции f=6x1-4x2 двигаем линию уровня параллельно самой себе по направлению градиента (направлению возрастания функции), пока не достигнем крайней точки области. Как видно из рисунка, крайняя точка области – это точка пересечения прямых -x1+5x2=0 и x1=6, т.е. точка (6;6/5). Максимальное значение целевой функции fmax=6*6-4*65=31.2.

ОТВЕТ: fmin(145;0)=16.8, fmax(6;65)=31.2.

Задание 2.

Фирма выпускает два вида продукции P1 и Р2 и использует при этом 4 вида сырья S1, S2, S3, S4. Количество сырья aij, идущего на каждый вид продукции, известно и дано в таблице. Известно и количество сырья на складе bi, а так же стоимость cj единицы каждого вида продукции. Составить производственный план, обеспечивающий максимальный доход фирмы, при выпуске продукции из имеющегося на складе сырья.

Построить область допустимых решений и найти графически оптимальное решение задачи.

РЕШЕНИЕ

Составим математическую модель задачи.

Пусть производится:

• x1 продукции вида P1,
• x2 продукции вида P2.
• По смыслу задачи эти переменные неотрицательны, т.е. xi≥0, i=1,2.
• Теперь составим ограничения задачи. Для производства x1,x2 штук соответствующей продукции потребуется:

• 0x1+3x2 сырья S1, запас которого составляет 24 ед., поэтому 3x2≤24,
• 1x1+2x2 сырья S2, запас которого составляет 20 ед., поэтому x1+2x2≤20,
• 2x1+2x2 сырья S3, запас которого составляет 30 ед., поэтому 2x1+2x2≤30,
• 1x1+3x2 сырья S4, запас которого составляет 30 ед., поэтому x1+3x2≤30.
• Прибыль от реализации x1 продукции P1, x2 продукции P2 составит L=7x1+8x2 тыс.руб., ее нужно максимизировать.
• Таким образом, математическая модель задачи будет иметь вид: найти такой план (x1*,x2*) выпуска продукции, удовлетворяющий системе:
• 3x2≤24x1+2x2≤202x1+2x2≤30x1+3x2≤30xi≥0,  i=1,2
• при котором функция L=7x1+8x2 принимает максимальное значение.
• Решим данную задачу графическим методом.
• Построим область допустимых решений задачи.
• На одном графике построим прямые:
• 3x2=24,                                                         x1+2x2=20,  точки 0;10 и (10;5)2x1+2x2=30,  точки 5;10 и (10;5)x1+3x2=30,  точки 0;10 и (3;9)x1=0,  x2=0                                              
• Направления полуплоскостей, являющихся решением неравенств из системы ограничений задачи, обозначены серыми полосами. Серым цветом закрашена область решений исходной задачи.
• [pic 2]
• Для нахождения максимального значения целевой функции L=7x1+8x2 построим одну из ее линий уровня 0=7x1+8x2 (чёрным цветом) и вектор градиента n=(7,8). Двигаем линию уровня параллельно самой себе по направлению градиента (направлению возрастания функции), пока не достигнем крайней точки области. Как видно из рисунка, крайняя точка области – это точка пересечения прямых x1+2x2=20 и 2x1+2x2=30. Найдем ее координаты:
• 20-2x2=15-x2
• x2=5
• x1=20-2*5=10
• Максимальное значение целевой функции fmax=7*10+8*5=100 достигается в точке (10;5).
• Таким образом, получили, что производственный план, обеспечивающий максимальный доход фирмы в 100 тыс.руб. состоит в том, чтобы выпускать 10 единиц продукции P1 и 5 единиц продукции P2.
• ОТВЕТ: производственный план, обеспечивающий максимальный доход фирмы в 100 тыс.руб. состоит в том, чтобы выпускать 10 единиц продукции P1 и 5 единиц продукции P2.

• Задание 3.
• Найти решения прямой и двойственной  задач линейного программирования симплекс-методом.
• F=3x1+4x2-x3→max
• x1+4x2-2x3≤7-3x1-x2+6x3≤2xi≥0,   i=1,2
• РЕШЕНИЕ
• Построение двойственной задачи
• Т.к. прямая задача является задачей максимизации, двойственная задача будет задачей минимизации. Система ограничений прямой задачи состоит из двух ограничений. Следовательно, в двойственной задаче будут две переменные y1,  y2 . Коэффициентами в целевой функции двойственной задачи будут свободные члены в системе ограничений прямой задачи, т.е.
• F=7y1+2y2→min.
• Составляем ограничения для двойственной задачи. Матрица коэффициентов при неизвестных в ограничениях двойственной задачи получается транспонированием матрицы коэффициентов прямой задачи, а свободные члены совпадают с коэффициентами целевой функции прямой задачи.
• Если переменная прямой задачи xi ≥ 0, то i-е условие системы ограничений двойственной задачи является неравенством, если xi – любое число, то i-е условие двойственной задачи представляет собой уравнение.
• Если j-е соотношение прямой задачи является неравенством, то соответствующая оценка j-го ресурса – переменная yj≥0, если j-е соотношение представляет собой уравнение, то переменная двойственной задачи yj – любое число.
• Двойственная задача имеет вид:
• F=3y1+8y2→min.
• 1y1-3y2≤34y1-1y2≤4-2y1+6y2=-1yj≥0,  j=1,2
• Приведем задачу к канонической форме, вводя в каждое основное неравенство свою дополнительную неотрицательную переменную yi (i=3,4):
• 1y1-3y2+y3=34y1-1y2+y4=4-2y1+6y2=-1yj≥0,  j=1,2,3,4
• В качестве базисных переменных выбираем y3,y4,y1. Разделим последнее ограничение на -2:
• 1y1-3y2+y3=34y1-1y2+y4=4y1-3y2=1/2yj≥0,  j=1,2,3,4
• Выразим базисные переменные через остальные:
• y3=-3y2-1/2+3y2+3y4=-4(3y2+1/2)+1y2+4y1=3y2+1/2yj≥0,  j=1,2,3,4
• Подставим их в целевую функцию:
• F=3(3y2+1/2)+8y2=17y2+1/2
• Исходную расширенную систему заносим в первую симплексную таблицу:

• В последней строке отсутствуют положительные коэффициенты, следовательно, найденное базисное решение является оптимальным: y*=(12,0,52, 2). Целевая функция принимает минимальное значение F=3*1/2+8*0=3/2.
• Нахождение решения исходной задачи
• Согласно второй теореме двойственности планы X и Y оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задач I и II соответственно хотя бы одно из любой пары сопряженных неравенств обращается в равенство.
• Рассмотрим выполнение неравенств двойственной задачи. Подставим оптимальное решение в ограничения двойственной задачи:
• 1/2-0≤34/2-0≤4-2/2+0=-1yj≥0,  j=1,2
• 1/2≤32≤4-1=-1yj≥0,  j=1,2
• Первое и второе ограничения выполняются как строгие неравенства, следовательно, x1=0,  x2=0.
• x3 найдём из ограничений исходной задачи:
• 0+4*0-2x3≤7-3*0-0+6x3≤2xi≥0,   i=1,2
• y2=0, следовательно, второе ограничение может быть строгим неравенством. y1≠0, следовательно, первое ограничение должно быть равенством:  x3=-7/2
• Найдено оптимальное решение прямой задачи: x*=(0,0,-72). Целевая функция принимает максимальное значение F=3*0+4*0+72=7/2.
• ОТВЕТ: оптимальное решение прямой задачи: x*=(0,0,-72), при котором функция достигает максимального значения 7/2.
• оптимальное решение двойственной задачи: y*=(12,0), при котором функция достигает минимального значения 3/2.

• Задание 4.
• На четырех складах готовой продукции имеется однотипный груз в количествах a1, a2, a3, a4. Его требуется развести в четыре магазина в количествах b1, b2, b3, b4. Стоимости перевозок со склада i в магазин j даны матрицей тарифов С. Составить план перевозок, обеспечивающий минимум транспортных затрат на перевозку всего груза, и определить эти минимальные затраты.
• a=125225270100
• b=100150300170
• C=58116812477133511854
• РЕШЕНИЕ
• Запишем данные в виде таблицы:

• Суммарные потребности магазинов равны суммарным запасам на складах (100+150+300+170=125+225+270+100=720), следовательно, транспортная задача является закрытой.
• Построим первый опорный план методом северо-западного угла.
• Удовлетворим потребности первого магазина, доставив в него продукцию из первого склада, стоимость перевозок С11=5. После этого на складе 1 останется 125-100=25 единиц продукции.

• Оставшуюся на первом складе продукцию доставим второму магазину по цене С12=8. Потребности магазина 2 не полностью удовлетворены. Довезем к нему продукцию из второго склада по цене С22=12. Во втором складе после этого останется 100 единиц продукции.

• Оставшуюся на втором складе продукцию отправим в третий магазин по цене С23=4. Потребности магазина 3 не полностью удовлетворены. Довезем к нему продукцию из третьего склада по цене С33=3. В третьем складе после этого останется 70 единиц продукции.

• Оставшуюся на третьем складе продукцию отправим в четвертый магазин по цене С34=5. Потребности магазина 4 не полностью удовлетворены. Довезем к нему продукцию из четвертого склада по цене С44=4.

• Таким образом, развезена вся продукция со складов и потребности всех магазинов удовлетворены. Вычислим транспортные затраты:
• 5*100+8*25+12*125+4*100+3*200+5*70+4*100=3950
• Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj по занятым клеткам таблицы, в которых ui+vj=cij.
• u1+v1=5
• u1+v2=8
• u2+v2=12
• u2+v3=4
• u3+v3=3
• u3+v4=5
• u4+v4=4
• Полагаем, что u1=0 и решаем полученную систему уравнений:
• u1=0,  v1=5,  v2=8,  u2=12-8=4,  v3=0,
• u3=3,  v4=5-3=2,     u4=4-2=2
• Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+vj>cij. Запишем разницу в таблицу:

• Выбираем максимальную положительную оценку (2). Строим цикл, ставим знак  + в перспективной ячейке С42, далее знаки чередуем:

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

• Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj по занятым клеткам таблицы, в которых ui+vj=cij.
• u1+v1=5
• u1+v2=8
• u2+v2=12
• u4+v2=8
• u2+v3=4
• u3+v3=3
• u3+v4=5
• Полагаем, что u1=0 и решаем полученную систему уравнений:
• u1=0,  v1=5,  v2=8,  u2=12-8=4,  u4=8-8=0,  v3=4-4=0,  u3=3,  v4=5-3=2    
• Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+vj>cij. Запишем разницу в таблицу:

• Выбираем максимальную положительную оценку (1). Строим цикл, ставим знак + в перспективной ячейке С21, далее знаки чередуем:

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

• Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj по занятым клеткам таблицы, в которых ui+vj=cij.
• u1+v1=5
• u1+v2=8
• u2+v1=8
• u4+v2=8
• u2+v3=4
• u3+v3=3
• u3+v4=5
• Полагаем, что u1=0 и решаем полученную систему уравнений:
• u1=0,  v1=5,  v2=8,  u2=8-5=3,  u4=8-8=0,  v3=4-3=1,  u3=3-1=2,  v4=5-2=3    
• Запишем разницу ui+vj-cij в таблицу:

• Опорный план является оптимальным, т.к. все оценки неположительны.
• Оптимальный план перевозки продукции состоит в том, что:

• из склада 1 нужно перевести 75 единиц продукции в магазин 1 и 50 единиц в магазин 2;
• из склада 2 нужно перевести 25 единиц продукции в магазин 1 и 200 единиц в магазин 3;
• из склада 3 нужно перевести 100 единиц продукции в магазин 3 и 170 единиц в магазин 4;
• из склада 4 нужно перевести 100 единиц продукции в магазин 2.

• При этом затраты на перевозку будут минимальными и составят:
• 5*75+8*50+8*25+4*200+3*100+5*170+8*100=3725
• ОТВЕТ: получен оптимальный план перевозки продукции, при котором затраты составят 3725.

• Задание 5.
• На основании данных истекшего года, используя линейную балансовую модель, составить план выпуска валового продукта по заданному новому ассортиментному вектору YН .

• Xij -- поставки i-ой отрасли для j-ой отрасли, Y - ассортиментный вектор истекшего года, X - вектор валового продукта за истекший год.
• РЕШЕНИЕ
• Найдём матрицу технологических коэффициентов:
• A=x11X1x12X2x13X3x21X1x22X2x23X3x31X1x31X2x33X3=1004608034070420604608034050420704609034060420=5234171632341754274693417≈0.2170.2350.1660.130.2350.120.150.2650.14
• Найдём сумму элементов в каждой строке матрицы А:
• 523+417+16≈0.619≤1
• 323+417+542≈0.484≤1
• 746+934+17≈0.559≤1
• Все суммы меньше или равны 1, следовательно, матрица А продуктивна.
• Построим балансовую модель:
• 523X1+417X2+16X3+200=X1323X1+417X2+542X3+160=X2746X1+934X2+17X3+180=X3
• Т.к. матрица А продуктивна, то существует единственное неотрицательное решение системы балансовых уравнений, которое найдём методом обратной матрицы X=SY.
• Рассчитаем матрицу полных затрат S=(E-A)-1.
• А=E-A=1-523417163231-4175427469341-17=182341716323131754274693467≈0.780.2350.1660.130.760.120.150.2650.86
• Найдём определитель полученной матрицы:
• det182341716323131754274693467=1823*1317*67+417*542*746+323*934*16-
• -746*1317*16-417*323*67-542*934*1823=743316422≈0.45≠0
• Определитель отличен от нуля, следовательно, обратная матрица существует.
• Для нахождения обратной матрицы построим матрицу из алгебраических дополнений к элементам матрицы А и транспонируем ее.
• A11=(-1)1+1det131754293467=1317*67-542*934=297476≈0.62
• A12=(-1)1+2det32354274667=-323*67+542*746=-1811932≈-0.09
• A13=(-1)1+3det3231317746934=323*934-1317*746=-32391≈-0.08
• A21=(-1)1+2det4171693467=-417*67+934*16=-75476≈-0.158
• A22=(-1)2+2det18231674667=1823*67-16*746=12471932≈0.646
• A23=(-1)2+3det1823417746934=-1823*934+746*417=-67391≈-0.17
• A31=(-1)3+1det417161317542=417*542-1317*16=-71714≈-0.1
• A32=(-1)2+3det182316323542=-1823*542+16*323=-114≈-0.07
• A33=(-1)3+3det18234173231317=1317*1823-417*323=222391≈0.56
• Получили матрицу из алгебраических дополнений к матрице А:
• A=297476-1811932-32391-7547612471932-67391-71714-114222391≈0.62-0.09-0.08-0.1580.646-0.17-0.1-0.070.56
• S=1detE-AAT=164227433297476-75476-71714-181193212471932-114-32391-67391222391=
• =2049314866-517514866-16337433-3077148662119914866-11737433-13447433-2814743393247433≈1.37-0.35-0.22-0.21.435-0.155-0.177-0.3771.244
• Найдём решение системы балансовых уравнений:
• X=SY=2049314866-517514866-16337433-3077148662119914866-11737433-13447433-281474339247433200160180=2049314866*200-517514866*160-16337433*180-307714866*200+2119914866*160-11737433*180-13447433*200-28147433*160+93247433*180=13413607433117708074339592807433≈180.46158.36129.06
• Рассчитаем плановые межотраслевые поставки Xij для нового ассортиментного вектора Aij Xj:
• 523*13413607433417*1177080743316*9592807433323*13413607433417*11770807433542*9592807433746*13413607433934*1177080743317*9592807433=
• =291600743327696074331598807433174960743327696074331142007433204120743331158074331370407433=
• ≈39.2337.2621.5123.5437.2615.3627.4641.9218.44
• ОТВЕТ: план выпуска валового продукта по заданному новому ассортиментному вектору YН .