Тестовые примеры векторных задач линейного программирования
Задание 1. Решить геометрически векторную задачу линейного программирования (построить на плоскости область решения системы линейных неравенств, определить точки оптимума по каждому критерию, вычислить относительные оценки и определить точки оптимума ВЗЛП).
1). opt F(X) = {max f(X)=(12x1 +15x2), max f(X)=(5x1 + 3x2)},
x1 + x2£ 6, x2£ 4, 2x1 + x2£10, x1³0, x2³0.
2). opt F(X) = {max f(X)=(3x1 +3x2), max f(X)=(8x1 + 3x2)},
3x1 + 4x2£ 12, 5x1 + 3x2£ 15, x1 - 2x2£ 2, x1³0, x2³0.
3). opt F(X) = {max f(X)=(10x1 +6x2), max f(X)=(4x1 + 6x2)},
3x1 + 5x2£ 30, 4x1 + 3x2£ 24, x1 £ 4, x1³0, x2³0.
4). opt F(X) = {max f(X)=(24x1 +30x2), max f(X)=(28x1 + 15x2)},
x1 + x2£ 12, 3x2£ 25, 2x1 + x2£ 20, x1³0, x2³0.
5). opt F(X) = max f(X)=(30x1 +18x2), max f(X)=(8x1 + 12x2)},
3x1 + 6x2£ 22, 5x1 + 3x2£ 35, 2x2£ 19, x1³0, x2³0.
6). opt F(X) = {max f(X)=(7x1 +7x2), max f(X)=(16x1 + 7x2)},
3x1 + 12x2£ 28, 15x1 + 9x2£ 32, 2x2£ 5, x1³0, x2³0.
7). opt F(X) = {max f(X)=(12x1 +13x2), max f(X)=(8x1 + 3x2)},
13x1 + 14x2£ 36, 15x1 + 13x2£ 45, x2£ 3, x1³0, x2³0.
8). opt F(X) = {max f(X)=(15x1 +162), max f(X)=(24x1 + 9x2)},
4.5x1 + 6x2£ 25, 7.5x1 + 4.3x2£ 32, x2£ 4, x1³0, x2³0.
9). opt F(X) = {max f(X)=(21x1 +23x2), max f(X)=(25x1 + 11x2)},
12x1 + 16x2£ 37, 20x1 + 12x2£ 47, x2£ 2, x1³0, x2³0.
10). opt F(X) = {max f(X)=(27x1 +28x2), max f(X)=(50x1 + 27x2)},
4.5x1 + 6x2£ 24, 7.5x1 + 4.5x2£ 28, x2£ 3, x1³0, x2³0.
Задание 2. Решить векторную задачу линейного программирования, используя при каждом расчете симплекс метод.
1). opt F(X)={ 2). opt F(X)={
max f1(X)=(7x1+8x2+6x3+9x4), max f1(X)=(10x1+7x2+6x3+8x4),
max f2(X)=(10x1+5x2+11x3+7x4)}, max f2(X)=(60x1+36x2+28x3+54x4)},
3x1 +4.5x2 + 6x3 + 2x4 £ 42, x1 + 3x2 + 2x3+ x4 £ 19.5,
4.5x1 +1.5x2 + 3x3 + x4£ 31, 3x1 + 2x2 + x3 - 2x4 £ 6,
1.5x1 + 3x2 +1.5x3- x4£ 11, 2x1 + x2 + 3x3 - x4 £ 9.5,
x1, x2, x3, x4³0, x1, x2, x3, x4 ³0,
3). opt F(X)={ 4). opt F(X)={
max f1(X)=(17x1+18x2+16x3+19x4), max f1(X)=(20x1+27x2+26x3+22x4),
max f2(X)=(14x1+28x2+6x3+24x4)}, max f2(X)=(10x1+7x2+16x3+8x4)},
3x1 + 5x2 + 3x3 + 2x4£ 35, 2x1 + 2x2 + 4x3 + 2x4 £ 22,
4x1 + x2 + 2x3 + x4£ 21, 2x1 + 3x2 + 3x3 + 3x4£ 29,
5x1 + 3x2 + x3 + 2x4£ 29, x1 + 5x2 - 2x3 + 2x4£ 24,
x1, x2, x3, x4³0, x1, x2, x3, x4 ³0,
5). opt F(X)={ 6). opt F(X)={
max f1(X)=(27x1+28x2+26x3+22x4), max f1(X)=(25x1+32x2+31x3+27x4),
max f2(X)=(7x1+8x2+6x3+9x4)}, max f2(X)=(100x1+77x2+36x3+58x4)},
6x1 + 4.5x2 + 6x3 + 2x4£ 27, 2x1 + 3x2 + 2x3 + 2x4£ 26,
9x1 +1.5x2 + 3x3 - x4 £ 15, 6x1 + 2x2 + x3 - 2x4£ 14,
3x1 + 3x2 + 1.5x3 + 4x4£ 28.5, 4x1 + x2 + 3x3 + x4£ 25,
x1, x2, x3, x4³0, x1, x2, x3, x4 ³0,
7). opt F(X)={ 8). opt F(X)={
max f1(X)=(20x1+21x2+23x3+22x4), max f1(X)=(30x1+37x2+36x3+32x4),
max f2(X)=(37x1+28x2+16x3+19x4)}, max f2(X)=(20x1+47x2+16x3+38x4)},
4x1 + 5x2 - 3x3 + x4£ 18, 3x1 +2x2 + 4x3 +2x4 £ 19,
5x1 + x2 + 2x3 - 2x4£ 13, 3x1 + 3x2 + 3x3 -2x4£ 17,
6x1 + 3x2 + 2x3 - 3x4£ 15, 2x1 + 5x2 - 2x3 + 3x4£ 22,
x1, x2, x3, x4³0, x1, x2, x3, x4 ³0,
9). opt F(X)={ 10). opt F(X)={
max f1(X)=(47x1+48x2+46x3+52x4), max f1(X)=(50x1+77x2+66x3+52x4),
max f2(X)=(27x1+18x2+26x3+9x4)}, max f2(X)=(21x1+18x2+7x3+18x4)},
2x1 + 6x2 + 4x3 - 2x4£ 22, 4x1 + 2x2 + 4x3 - x4£ 25,
4x1 + 2x2 + x3 + 3x4£ 38, 2x1 - 3x2 + 6x3 + 4x4£ 41,
5x1 +4.5x2 + 2x3 - 4x4£ 15, 4x1 + 6x2 - 2x3 + 2x4£ 25,
x1, x2, x3, x4³0, x1, x2, x3, x4 ³0,
Задание 3. Решить векторные задачи линейного программирования в системе Matlab.
Задание 3.1. opt F(X)={
max f1(X)=199x1+143.8x2+133.8x3, max f2(x)= 346x1+360x2+482.8x3,
max f3(X)=121.2x1+122.9x2+124.2x3, max f4(X)=199x1+131.4x2+119.4x3,
min f5(x) = 5x1 + 5x2 + 5x3, min f6(x)=19.9x1+13.14x2+11.94x3}.
при ограничениях: 5x1 + 5x2 + 5x3 £ 2047,
19.9x1 + 13.14x2 + 11.94x3 £ 9400,
1.12x2 + 1.28 x3 £ 502,
199x1 + 143.8x2 + 133.8x3 ³ 40000,
346x1 + 360x2 + 487.8x3 ³ 90000 , x1, x2, x3 > 0.
Задание 3.2. (Модель рынка 2*2)
opt F(X)={max f1(X) = p1x1 + p3x3, max f2 (X) = p2x2 + p4x4,
min f3 (X) = c1x1 + c2x2 , min f4 (X) = c3x3 + c4x4},
при ограничениях b ≤ c1x1 + c2x2 ≤ b , b ≤ c3x3 + c4x4 ≤ b ,
a1x1+ a3x3 ≤ b1, a2x2 + a4x4 ≤ b2,
x1, x2, x3, x4 ³ 0.
Решить векторную задачу линейного программирования в системе Matlab, подставляя данные из табл. 5.5.
Таблица 5.5
| Параметры задачи | Варианты | |||||||||
| c1 | ||||||||||
| c2 | ||||||||||
| c3 | ||||||||||
| c4 | ||||||||||
| a1 | ||||||||||
| a2 | ||||||||||
| a3 | ||||||||||
| a4 | ||||||||||
| p1= (c1-a1 ) | ||||||||||
| p2= (c2-a2 ) | ||||||||||
| p3= (c3-a3 ) | ||||||||||
| p4= (c4-a4 ) | ||||||||||
| b | ||||||||||
| b | ||||||||||
| b | ||||||||||
| b | ||||||||||
| b1 | ||||||||||
| b2 |
Конец дидактического материала занятия 3.
Вопросы для предварительной самостоятельной подготовки занятия 3.
1. Основные положения по формированию модели векторной оптимизации в экономике муниципального образования и региона
2. Структура Вашей интеллект – карты в приложении к муниципальному образованию (Наименование муниципального образования)
3. Сформировать модели векторной оптимизации в экономике муниципального образования и региона.
Тема 4.Экономическая, финансовая политика, планирование и бюджет региона
Занятие 4. Тема занятия. Формирование производственного плана предприятия в экономике муниципального образования и региона. (12 часов)
4.1. Формирование производственного плана предприятия
1). Построение модели производственного плана
Построение модели производственного плана предприятия представим на конкретном примере в виде векторной задачи линейного программирования вида (5.5.1)-(5.5.4).
Дано. На предприятии, выпускающем неоднородную продукцию четырех видов, N=4. При производстве изделий используются ресурсы трех видов М=3:
трудовые (различные специальности);
материальные (различные виды материалов);
мощности (оборудование: сварочное, токарное, фрезерное и пр.).
Обозначим: с — рыночная цена продукции единицы продукции j–го вида, j = , с — прибыль, получаемая фирмой от продажи единицы продукции j–го вида, j = ; aij – норма расхода ресурсов показывает, какое количество единиц i–го ресурса, необходимого при производстве единицы продукции j–го вида. В совокупности aij, i= , j= представляют технологическую матрицу производства, числовые значения которых представлены в табл. 5.6. [81]. В ней же указаны потенциальные возможности предприятия по каждому видов ресурсов bi, i= , а также доход с и прибыль с от реализации единицы изделия каждого вида.
Требуется составить производственный план предприятия, который включает показатели по номенклатуре (по видам изделий) и по объему, т. е. сколько изделий соответствующего вида следует изготовить предприятию, чтобы доход и прибыль при их реализации были как можно выше. Составить математическую модель задачи и решить ее.
Таблица 5.6
Затраты ресурсов и производственные показатели
| Вид ресурсов | Затраты ресурсов на производство одного изделия | Производственные возможности предприятия по каждому виду ресурсов | |||
| Вид 1 | Вид 2 | Вид 3 | Вид 4 | ||
| Трудовые (челов./недель) | |||||
| Материальные (в кг.) | |||||
| Мощности (в час.) | |||||
| Доход от продажи ед. продукции (руб.) c , j=1,...,4 | Максимизировать | ||||
| Прибыль c , j=1,...,4 | Максимизировать | ||||
| Объем выпускаемой продукции | x1 | x2 | x3 | x4 | Определить |
Решение. В качестве неизвестного примем x1 - единиц изделий первого вида изготовленного на предприятии, аналогично x2, x3, x4 - количество единиц второго, третьего и четвертого вида. Тогда для производства такого количества изделий потребуется затратить 1x1 + 1x2 + 1x3 + 1x4 - человеко/недель трудовых ресурсов (предполагая, что специальности взаимозаменяемы.
Так как общий фонд рабочего времени не может превышать 15 человеко/недель, то должно выполняться неравенство:
1x1 + 1x2 + 1x3 + 1x4 £ 15,
Аналогичные рассуждения относительно возможного использования материальных ресурсов и мощностей приведут к следующим неравенствам:
7x1 + 5x2 + 3x3 + 2x4 £ 120, (5.5.11)
3x1 + 5x2 +10x3+15x4 £ 100. (5.5.12)
Но так как количество изготовляемых изделий не может быть отрицательным, то
x1³0, x2 ³0, x3 ³ 0, x4 ³ 0, (5.5.13)
Далее, если будет изготовлено x1,…,x4 единиц изделий соответствующего вида, то доход от их реализации составит f1(X)= 4x1 + 5x2 + 9x3 + 11x4.
Цель производителя получить доход от продажи изделий как можно выше. Эта целенаправленность может быть выражена в следующей математической задаче:
max f1(X)= 4x1 + 5x2 + 9x3 + 11x4, (5.5.14)
при ограничениях (5.5.11)-(5.5.13).
Аналогично можно сформулировать задачу, как определение максимальной прибыли:
f2(X) = max (2x1 + 10x2 + 6x3 + 20x4),
при ограничениях (5.5.11)-(5.5.13).
Как правило, руководитель фирмы принимает решение с учетом обоих критериев f1(X) и f2(X). Отсюда целевую направленность можно выразить с помощью векторного критерия F(X), который примет вид:
opt F(X)={max f1(X) = (4x1 + 5x2 + 9x3 + 11x4), (5.5.15)
max f2(X) = (2x1 +10x2 + 6x3 + 20x4)} (5.5.16)
при ограничениях:
x1 + x2 + x3 + x4 £ 15, (5.5.17)
7x1 + 5x2 + 3x3 + 2x4 £ 120, (5.5.18)
3x1 + 5x2 +10x3 +15x4 £ 100, (5.5.19)
x1³0, x2³0, x3³0, x4³0. (5.5.20)
Такая задача называется векторной (или многокритериальной) задачей линейного программирования (ВЗЛП).
В этой задаче формулируется следующее: требуется найти неотрицательное решение x1,…,x4 в системе неравенств (5.5.17)-(5.5.20) такое, при котором функции f1(X) и f2(X) принимают возможно максимальное значение.
Линейные функции f1(X) и f2(X), максимум которых требуется определить, вместе с системой неравенств(5.5.17)-(5.5.19) и условием не отрицательности переменных образуют математическую модель исходной задачи.
Так как функции линейны, а система ограничений содержит только линейные неравенства, то получившаяся задача является векторной задачей линейного программирования.
2). Решение задачи формирование производственного плана в системе Matlab
Решение задачи линейного программирования покажем на примере (5.5.15)-(5.5.20) в системе Matlab в соответствии с алгоритмом решения ВЗЛП на основе нормализации критериев и принципа гарантированного результата.
M-файл задачи представлен в приложении 5.5.2. Сначала подготавливаются исходные данные:
Формируется векторная целевая функция в виде матрицы:
cvec = [-4.0 -5.0 -9.0 -11.0;
-2. -10. -6. -20.];
матрица линейных ограничений:
a = [1.0 1.0 1.0 1.0;
7.0 5.0 3.0 2.0;
3.0 5.0 10.0 15.0];
вектор, содержащий ограничения (bi): b=[15. 120. 100.]; ограничения равенства: Aeq=[]; Beq=[]; вектор начальных условий: X0=[0. 0. 0. 0.];
Алгоритм представим как последовательность шагов.
Шаг 1. Решение по каждому критерию.
1) Решение по первому критерию представляет обращение к функции linprog, решающей задачу линейного программирования:
[X1, f1]=Linprog(cvec(1,:),a,b,Aeq,Beq,X0),
где Х1 - вектор неизвестных переменных; f1 – величина целевой функции.
В результате решения получим:
оптимальные значения переменных: X ={x1=7.14, x2=0, x3=7.85, x4=0};
оптимальное значение целевой функции: f1=f =99.286.
Аналогично по второму критерию:
[X2,f2]=Linprog(cvec(2,:),a,b,Aeq,Beq,X0)
X = {x1 = 0, x2 = 125, x3 = 0, x4 = 25}, f2=f =175.
Шаг 2. Выполняется анализ критериев в ВЗЛП, для чего в оптимальных точках X X определяются величины целевых функций F(X*)={{fq(X ), k= }, q= } и относительных оценок l(X*)={{lq(X ), k= }, q= }.
В системе Matlab вычисление этих функций будет следующим:
f1x1=cvec(1,:)*x1, f2x1=cvec(2,:)*x1, f1x2=cvec(1,:)*x2, f2x2=cvec(2,:)*x2,
l1x1= f1x1/f1, l2x1= f2x1/f2, l1x2= f1x2/f1, l2x2= f2x2/f2.
F(X*)= = , l(X*)= = ,
где lk(X) = (fk(X) - f )/(f - f ), k= , f =fk(X ), для данного вида примера f =0, отсюда lk(X) = fk(X)/f , k= .
Шаг 3. Строится l-задача:
lo = max l,
при ограничениях: l - f1(X) /f £0, l - f2(X)/f £0, (5.5.17)-(5.5.20).
Подставляя числовые данные, получим:
lo = max l,
при ограничениях: l - (4x1 + 5x2 + 9x3 + 11x4)/f £ 0,
l - (2x1 +10x2 + 6x3 + 20x4)/f £ 0,
x1+ x2+x3+x4 £15, 7x1+5x2+3x3+2x4£120, 3x1+5x2+10x3+15x4 £100,
x1³0, x2³0, x3³0, x4³0.
Для решения этой задачи в системе Matlab задаются следующие параметры: коэффициенты целевой функции (критерий l-задачи) –
Lо = [-1. 0. 0. 0. 0.];
матрица линейных ограничений l-задачи:
Ao = [1.0 -4.0/f -5.0/ f -9.0/ f -11.0/ f ;
1.0 -2.0/ f -10.0/ f -6.0/ f -20.0/ f ;
0.0 1.0 1.0 1.0 1.0;
0.0 7.0 5.0 3.0 2.0;
0.0 3.0 5.0 10.0 15.0];
вектор ограничений (bi): bo = [0.0 0.0 15.0 120.0 100.0];
вектор начальных условий: X0 = [0.0 0.0 0.0 0.0 0.0].
Обращение к функции Linprog для решения l-задачи представлено в виде:
[Xo, Lo]=Linprog(Lо,Ao,bo,Aeq,Beq,X0).
Результаты решения l-задачи:
оптимальные значения переменных:
Xo= {x1=0.9217914,x2= 0.0, x3 =11.73964, x4=1.520722,x5=1.739639};
оптимальное значение целевой функции: lo = 0.9218
f1(Xo)=91.52, l1(Xo)=0.9218; f2(Xo)=161.3, l2(Xo)=0.9218, т. е. lo£lk(Xo), k=1,2.
Эти результаты показывают, что в точке Xo оба критерия в относительных единицах достигли уровня lo=0.92 от своих оптимальных величин. Любое увеличение одного из критериев выше этого уровня приводит к уменьшению другого критерия, т.е. точа Xo оптимальна по Парето.
4.2. Моделирование производственного плана предприятия по трем критериям
1). Построение модели производственного плана по трем критериям
Моделирование и формирование производственного плана предприятия на примере векторной задачи линейного программирования вида с тремя критериями: критериям максимизации объема продаж, прибыли и минимизации затрат представим в три этапа: постановка задачи, решение ВЗЛП при равнозначных критериях, анализ результатов и принятие окончательного решения.
Постановка задачи производственного плана в виде векторной задачи линейного программирования
Дано. Предприятие выпускает однородную продукцию двух видов, N=2. При производстве изделий используется один ресурс М=1. Числовые значения технологической матрицы производства представлены в табл. 5.7. Производственный план, представляющий сумму выпускаемых изделий, должен превышать 300 штук. Маркетинговые ограничения: u1 = 500, u2 = 400.
Требуется определить производственный план предприятия, который включает показатели по номенклатуре (по видам изделий) и по объему, т. е. сколько изделий соответствующего вида изделия следует изготовить предприятию, чтобы доход и прибыль при их реализации была как можно выше, а затраты меньше. Составить математическую модель задачи и решить ее.
Таблица 5.7
Затраты ресурсов и производственные показатели
| Вид Ресурсов | Затраты ресурсов на производство одного изделия | Производственные возможности фирмы по каждому виду ресурсов | |
| Вид 1 | Вид 2 | ||
| Трудовые a11 , a12 | |||
| Доход от продажи ед. продукции (руб.) c , j=1,2 | Максимизировать | ||
| Прибыль c , j=1,2 | Максимизировать | ||
| Стоимость единицы ресурса c | Минимизировать | ||
| Объем выпускаемой продукции | x1 | x2 | Определить |
Решение. Постановка задачи в производственной части (критерии максимизации объема продаж, прибыли и ограничения по ресурсам) аналогично 5.3. Дополнительно заметим, что производственный план должен превышать 300 изделий: x1 + x2 ³300. Затраты на изготовленные изделия f3(X)= ca11x1 + ca12x2 должны быть как можно ниже, т. е. требуется минимизировать функцию f3(X)= 1*5*x1+1*6*x2.
Цель производителя получить доход и прибыль от продажи изделий как можно выше при минимизации себестоимости выпускаемых изделий. Отсюда целевую направленность можно выразить с помощью векторного критерия F(X), который примет вид:
opt F(X)={F1(X(t))={max f1(X)=(25x1 + 25x2), (5.5.21)
max f2(X)=(5x1 +8x2)}, (5.5.22)
F2(X(t))={min f3(X)=(5x1 +6x2)}}, (5.5.23)
при ограничениях:
5 x1 + 6 x2 £ 3000, x1 £ 500, x1 £ 400, x1 + x2 ³300, x1³0, x2³0. (5.5.24)
В этой ВЗЛП формулируется следующее: требуется найти неотрицательное решение x1, x2, в системе неравенств (5.5.24) такое, при котором функции f1(X) и f2(X) принимают максимально возможное значение, а функция f3(X) минимальное значение.
Линейные функции f1(X) и f2(X) максимум и f3(X), минимум которых требуется определить, вместе с системой неравенств (5.5.24) образуют математическую модель исходной задачи.
Ограничения и результаты решения задачи (5.5.21)-(5.5.24) проиллюстрированы на рис. 5.3.