Контрольная работа по "Линейное программирование"
Автор: Nastya16101997 • Июнь 5, 2018 • Контрольная работа • 4,367 Слов (18 Страниц) • 1,039 Просмотры
Линейное программирование
Задание 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 единицы каждого вида продукции. Составить производственный план, обеспечивающий максимальный доход фирмы, при выпуске продукции из имеющегося на складе сырья.
Виды сырья | Виды продукции | Количество сырья на складе, ед. | |
P1 | P2 | ||
S1 | 0 | 3 | 24 |
S2 | 1 | 2 | 20 |
S3 | 2 | 2 | 30 |
S4 | 1 | 3 | 30 |
Стоимость единицы продукции | 7 | 8 |
Построить область допустимых решений и найти графически оптимальное решение задачи.
РЕШЕНИЕ
Составим математическую модель задачи.
Пусть производится:
- 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Н .
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
...