Тестовые примеры векторных задач линейного программирования

 

Задание 1. Решить геометрически векторную задачу линейного программирования (построить на плоскости область решения системы линейных неравенств, определить точки оптимума по каждому критерию, вычислить относительные оценки и определить точки оптимума ВЗЛП).

1). opt F(X) = {max f(X)=(12x₁ +15x₂), max f(X)=(5x₁ + 3x₂)},

x₁ + x₂£ 6, x₂£ 4, 2x₁ + x₂£10, x₁³0, x₂³0.

2). opt F(X) = {max f(X)=(3x₁ +3x₂), max f(X)=(8x₁ + 3x₂)},

3x₁ + 4x₂£ 12, 5x₁ + 3x₂£ 15, x₁ - 2x₂£ 2, x₁³0, x₂³0.

3). opt F(X) = {max f(X)=(10x₁ +6x₂), max f(X)=(4x₁ + 6x₂)},

3x₁ + 5x₂£ 30, 4x₁ + 3x₂£ 24, x₁ £ 4, x₁³0, x₂³0.

4). opt F(X) = {max f(X)=(24x₁ +30x₂), max f(X)=(28x₁ + 15x₂)},

x₁ + x₂£ 12, 3x₂£ 25, 2x₁ + x₂£ 20, x₁³0, x₂³0.

5). opt F(X) = max f(X)=(30x₁ +18x₂), max f(X)=(8x₁ + 12x₂)},

3x₁ + 6x₂£ 22, 5x₁ + 3x₂£ 35, 2x₂£ 19, x₁³0, x₂³0.

6). opt F(X) = {max f(X)=(7x₁ +7x₂), max f(X)=(16x₁ + 7x₂)},

3x₁ + 12x₂£ 28, 15x₁ + 9x₂£ 32, 2x₂£ 5, x₁³0, x₂³0.

7). opt F(X) = {max f(X)=(12x₁ +13x₂), max f(X)=(8x₁ + 3x₂)},

13x₁ + 14x₂£ 36, 15x₁ + 13x₂£ 45, x₂£ 3, x₁³0, x₂³0.

8). opt F(X) = {max f(X)=(15x₁ +16₂), max f(X)=(24x₁ + 9x₂)},

4.5x₁ + 6x₂£ 25, 7.5x₁ + 4.3x₂£ 32, x₂£ 4, x₁³0, x₂³0.

9). opt F(X) = {max f(X)=(21x₁ +23x₂), max f(X)=(25x₁ + 11x₂)},

12x₁ + 16x₂£ 37, 20x₁ + 12x₂£ 47, x₂£ 2, x₁³0, x₂³0.

10). opt F(X) = {max f(X)=(27x₁ +28x₂), max f(X)=(50x₁ + 27x₂)},

4.5x₁ + 6x₂£ 24, 7.5x₁ + 4.5x₂£ 28, x₂£ 3, x₁³0, x₂³0.

Задание 2. Решить векторную задачу линейного программирования, используя при каждом расчете симплекс метод.

1). opt F(X)={ 2). opt F(X)={

max f₁(X)=(7x₁+8x₂+6x₃+9x₄), max f₁(X)=(10x₁+7x₂+6x₃+8x₄),

max f₂(X)=(10x₁+5x₂+11x₃+7x₄)}, max f₂(X)=(60x₁+36x₂+28x₃+54x₄)},

3x₁ +4.5x₂ + 6x₃ + 2x₄ £ 42, x₁ + 3x₂ + 2x₃+ x₄ £ 19.5,

4.5x₁ +1.5x₂ + 3x₃ + x₄£ 31, 3x₁ + 2x₂ + x₃ - 2x₄ £ 6,

1.5x₁ + 3x₂ +1.5x₃- x₄£ 11, 2x₁ + x₂ + 3x₃ - x₄ £ 9.5,

x₁, x₂, x₃, x₄³0, x₁, x₂, x₃, x₄ ³0,

3). opt F(X)={ 4). opt F(X)={

max f₁(X)=(17x₁+18x₂+16x₃+19x₄), max f₁(X)=(20x₁+27x₂+26x₃+22x₄),

max f₂(X)=(14x₁+28x₂+6x₃+24x₄)}, max f₂(X)=(10x₁+7x₂+16x₃+8x₄)},

3x₁ + 5x₂ + 3x₃ + 2x₄£ 35, 2x₁ + 2x₂ + 4x₃ + 2x₄ £ 22,

4x₁ + x₂ + 2x₃ + x₄£ 21, 2x₁ + 3x₂ + 3x₃ + 3x₄£ 29,

5x₁ + 3x₂ + x₃ + 2x₄£ 29, x₁ + 5x₂ - 2x₃ + 2x₄£ 24,

x₁, x₂, x₃, x₄³0, x₁, x₂, x₃, x₄ ³0,

5). opt F(X)={ 6). opt F(X)={

max f₁(X)=(27x₁+28x₂+26x₃+22x₄), max f₁(X)=(25x₁+32x₂+31x₃+27x₄),

max f₂(X)=(7x₁+8x₂+6x₃+9x₄)}, max f₂(X)=(100x₁+77x₂+36x₃+58x₄)},

6x₁ + 4.5x₂ + 6x₃ + 2x₄£ 27, 2x₁ + 3x₂ + 2x₃ + 2x₄£ 26,

9x₁ +1.5x₂ + 3x₃ - x₄ £ 15, 6x₁ + 2x₂ + x₃ - 2x₄£ 14,

3x₁ + 3x₂ + 1.5x₃ + 4x₄£ 28.5, 4x₁ + x₂ + 3x₃ + x₄£ 25,

x₁, x₂, x₃, x₄³0, x₁, x₂, x₃, x₄ ³0,

7). opt F(X)={ 8). opt F(X)={

max f₁(X)=(20x₁+21x₂+23x₃+22x₄), max f₁(X)=(30x₁+37x₂+36x₃+32x₄),

max f₂(X)=(37x₁+28x₂+16x₃+19x₄)}, max f₂(X)=(20x₁+47x₂+16x₃+38x₄)},

4x₁ + 5x₂ - 3x₃ + x₄£ 18, 3x₁ +2x₂ + 4x₃ +2x₄ £ 19,

5x₁ + x₂ + 2x₃ - 2x₄£ 13, 3x₁ + 3x₂ + 3x₃ -2x₄£ 17,

6x₁ + 3x₂ + 2x₃ - 3x₄£ 15, 2x₁ + 5x₂ - 2x₃ + 3x₄£ 22,

x₁, x₂, x₃, x₄³0, x₁, x₂, x₃, x₄ ³0,

9). opt F(X)={ 10). opt F(X)={

max f₁(X)=(47x₁+48x₂+46x₃+52x₄), max f₁(X)=(50x₁+77x₂+66x₃+52x₄),

max f₂(X)=(27x₁+18x₂+26x₃+9x₄)}, max f₂(X)=(21x₁+18x₂+7x₃+18x₄)},

2x₁ + 6x₂ + 4x₃ - 2x₄£ 22, 4x₁ + 2x₂ + 4x₃ - x₄£ 25,

4x₁ + 2x₂ + x₃ + 3x₄£ 38, 2x₁ - 3x₂ + 6x₃ + 4x₄£ 41,

5x₁ +4.5x₂ + 2x₃ - 4x₄£ 15, 4x₁ + 6x₂ - 2x₃ + 2x₄£ 25,

x₁, x₂, x₃, x₄³0, x₁, x₂, x₃, x₄ ³0,

Задание 3. Решить векторные задачи линейного программирования в системе Matlab.

Задание 3.1. opt F(X)={

max f₁(X)=199x₁+143.8x₂+133.8x₃, max f₂(x)= 346x₁+360x₂+482.8x₃,

max f₃(X)=121.2x₁+122.9x₂+124.2x₃, max f₄(X)=199x₁+131.4x₂+119.4x₃,

min f₅(x) = 5x₁ + 5x₂ + 5x₃, min f₆(x)=19.9x₁+13.14x₂+11.94x₃}.

при ограничениях: 5x₁ + 5x₂ + 5x₃ £ 2047,

19.9x₁ + 13.14x₂ + 11.94x₃ £ 9400,

1.12x₂ + 1.28 x₃ £ 502,

199x₁ + 143.8x₂ + 133.8x₃ ³ 40000,

346x₁ + 360x₂ + 487.8x₃ ³ 90000 , x₁, x₂, x₃ > 0.

Задание 3.2. (Модель рынка 2*2)

opt F(X)={max f₁(X) = p₁x₁ + p₃x₃, max f₂ (X) = p₂x₂ + p₄x₄,

min f₃ (X) = c₁x₁ + c₂x₂ , min f₄ (X) = c₃x₃ + c₄x₄},

при ограничениях b ≤ c₁x₁ + c₂x₂ ≤ b , b ≤ c₃x₃ + c₄x₄ ≤ b ,

a₁x₁+ a₃x₃ ≤ b₁, a₂x₂ + a₄x₄ ≤ b₂,

x₁, x₂, x₃, x₄ ³ 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 = ; a_ij – норма расхода ресурсов показывает, какое количество единиц i–го ресурса, необходимого при производстве едини­цы продукции j–го вида. В совокупности a_ij, i= , j= представляют технологическую матрицу производства, числовые значения которых представлены в табл. 5.6. [81]. В ней же указаны потенциальные возможности предприятия по каждому видов ресурсов b_i, i= , а также доход с и прибыль с от реализации единицы изделия каждого вида.

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

Таблица 5.6

Затраты ресурсов и производственные показатели

Вид ресурсов	Затраты ресурсов на производство одного изделия	Производственные возможности предприятия по каждому виду ресурсов
Вид 1	Вид 2	Вид 3	Вид 4
Трудовые (челов./недель)
Материальные (в кг.)
Мощности (в час.)
Доход от продажи ед. продукции (руб.) c , j=1,...,4					Максимизировать
Прибыль c , j=1,...,4					Максимизировать
Объем выпускаемой продукции	x1	x2	x3	x4	Определить

Решение. В качестве неизвестного примем x₁ - единиц изделий первого вида изготовленного на предприятии, аналогично x₂, x₃, x₄ - количество единиц второго, третьего и четвертого вида. Тогда для производства такого количества изделий потребуется затра­тить 1x₁ + 1x₂ + 1x₃ + 1x₄ - человеко/недель трудовых ресурсов (предполагая, что специальности взаимозаменяемы.

Так как общий фонд рабочего времени не может превышать 15 человеко/недель, то должно выполняться неравенство:

1x₁ + 1x₂ + 1x₃ + 1x₄ £ 15,

Аналогичные рассуждения относительно возможного исполь­зования материальных ресурсов и мощностей приведут к следующим неравенствам:

7x₁ + 5x₂ + 3x₃ + 2x₄ £ 120, (5.5.11)

3x₁ + 5x₂ +10x₃+15x₄ £ 100. (5.5.12)

Но так как количество изготовляемых изделий не может быть отрицательным, то

x₁³0, x₂ ³0, x₃ ³ 0, x₄ ³ 0, (5.5.13)

Далее, если будет изготовлено x₁,…,x₄ единиц изделий соответствующего вида, то доход от их реализации составит f₁(X)= 4x₁ + 5x₂ + 9x₃ + 11x₄.

Цель производителя получить доход от продажи изделий как можно выше. Эта целенаправленность может быть выражена в следующей математической за­даче:

max f₁(X)= 4x₁ + 5x₂ + 9x₃ + 11x₄, (5.5.14)

при ограничениях (5.5.11)-(5.5.13).

Аналогично можно сформулировать задачу, как определение максимальной прибыли:

f₂(X) = max (2x₁ + 10x₂ + 6x₃ + 20x₄),

при ограничениях (5.5.11)-(5.5.13).

Как правило, руководитель фирмы принимает решение с учетом обоих критериев f₁(X) и f₂(X). Отсюда целевую направленность можно выразить с помощью векторного критерия F(X), который примет вид:

opt F(X)={max f₁(X) = (4x₁ + 5x₂ + 9x₃ + 11x₄), (5.5.15)

max f₂(X) = (2x₁ +10x₂ + 6x₃ + 20x₄)} (5.5.16)

при ограничениях:

x₁ + x₂ + x₃ + x₄ £ 15, (5.5.17)

7x₁ + 5x₂ + 3x₃ + 2x₄ £ 120, (5.5.18)

3x₁ + 5x₂ +10x₃ +15x₄ £ 100, (5.5.19)

x₁³0, x₂³0, x₃³0, x₄³0. (5.5.20)

Такая задача называется векторной (или многокритериальной) задачей линейного программирования (ВЗЛП).

В этой за­даче формулируется следующее: требуется найти неотрицательное решение x₁,…,x₄ в системе неравенств (5.5.17)-(5.5.20) такое, при котором функции f₁(X) и f₂(X) принимают возможно мак­симальное значение.

Линейные функции f₁(X) и f₂(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];

вектор, содержащий ограничения (b_i): 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 ={x₁=7.14, x₂=0, x₃=7.85, x₄=0};

оптимальное значение целевой функции: f1=f =99.286.

Аналогично по второму критерию:

[X2,f2]=Linprog(cvec(2,:),a,b,Aeq,Beq,X0)

X = {x₁ = 0, x₂ = 125, x₃ = 0, x₄ = 25}, f2=f =175.

Шаг 2. Выполняется анализ критериев в ВЗЛП, для чего в оптимальных точках X X определяются величины целевых функций F(X^*)={{f_q(X ), k= }, q= } и относительных оценок l(X^*)={{l_q(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^*)= = ,

где l_k(X) = (f_k(X) - f )/(f - f ), k= , f =f_k(X ), для данного вида примера f =0, отсюда l_k(X) = f_k(X)/f , k= .

Шаг 3. Строится l-задача:

l^o = max l,

при ограничениях: l - f₁(X) /f £0, l - f₂(X)/f £0, (5.5.17)-(5.5.20).

Подставляя числовые данные, получим:

l^o = max l,

при ограничениях: l - (4x₁ + 5x₂ + 9x₃ + 11x₄)/f £ 0,

l - (2x₁ +10x₂ + 6x₃ + 20x₄)/f £ 0,

x₁+ x₂+x₃+x₄ £15, 7x₁+5x₂+3x₃+2x₄£120, 3x₁+5x₂+10x₃+15x₄ £100,

x₁³0, x₂³0, x₃³0, x₄³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];

вектор ограничений (b_i): 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= {x₁=0.9217914,x₂= 0.0, x₃ =11.73964, x₄=1.520722,x₅=1.739639};

оптимальное значение целевой функции: l^o = 0.9218

f₁(X^o)=91.52, l₁(X^o)=0.9218; f₂(X^o)=161.3, l₂(X^o)=0.9218, т. е. l^o£l_k(X^o), k=1,2.

Эти результаты показывают, что в точке X^o оба критерия в относительных единицах достигли уровня l^o=0.92 от своих оптимальных величин. Любое увеличение одного из критериев выше этого уровня приводит к уменьшению другого критерия, т.е. точа X^o оптимальна по Парето.

 

4.2. Моделирование производственного плана предприятия по трем критериям

1). Построение модели производственного плана по трем критериям

Моделирование и формирование производственного плана предприятия на примере векторной задачи линейного программирования вида с тремя критериями: критериям максимизации объема продаж, прибыли и минимизации затрат представим в три этапа: постановка задачи, решение ВЗЛП при равнозначных критериях, анализ результатов и принятие окончательного решения.

Постановка задачи производственного плана в виде векторной задачи линейного программирования

Дано. Предприятие выпускает однородную продукцию двух видов, N=2. При производстве изделий используется один ресурс М=1. Числовые значения технологической матрицы производства представлены в табл. 5.7. Производственный план, представляющий сумму выпускаемых изделий, должен превышать 300 штук. Маркетинговые ограничения: u₁ = 500, u₂ = 400.

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

Таблица 5.7

Затраты ресурсов и производственные показатели

Вид Ресурсов	Затраты ресурсов на производство одного изделия	Производственные возможности фирмы по каждому виду ресурсов
Вид 1	Вид 2
Трудовые a11 , a12
Доход от продажи ед. продукции (руб.) c , j=1,2			Максимизировать
Прибыль c , j=1,2			Максимизировать
Стоимость единицы ресурса c			Минимизировать
Объем выпускаемой продукции	x1	x2	Определить

Решение. Постановка задачи в производственной части (критерии максимизации объема продаж, прибыли и ограничения по ресурсам) аналогично 5.3. Дополнительно заметим, что производственный план должен превышать 300 изделий: x₁ + x₂ ³300. Затраты на изготовленные изделия f₃(X)= ca₁₁x₁ + ca₁₂x₂ должны быть как можно ниже, т. е. требуется минимизировать функцию f₃(X)= 1*5*x₁+1*6*x₂.

Цель производителя получить доход и прибыль от продажи изделий как можно выше при минимизации себестоимости выпускаемых изделий. Отсюда целевую направленность можно выразить с помощью векторного критерия F(X), который примет вид:

opt F(X)={F₁(X(t))={max f₁(X)=(25x₁ + 25x₂), (5.5.21)

max f₂(X)=(5x₁ +8x₂)}, (5.5.22)

F₂(X(t))={min f₃(X)=(5x₁ +6x₂)}}, (5.5.23)

при ограничениях:

5 x₁ + 6 x₂ £ 3000, x₁ £ 500, x₁ £ 400, x₁ + x₂ ³300, x₁³0, x₂³0. (5.5.24)

В этой ВЗЛП формулируется следующее: требуется найти неотрицательное решение x₁, x₂, в системе неравенств (5.5.24) такое, при котором функции f₁(X) и f₂(X) принимают мак­симально возможное значение, а функция f₃(X) минимальное значение.

Линейные функции f₁(X) и f₂(X) максимум и f₃(X), минимум которых требуется опре­делить, вместе с системой неравенств (5.5.24) образуют математическую модель ис­ходной задачи.

Ограничения и результаты решения задачи (5.5.21)-(5.5.24) проиллюстрированы на рис. 5.3.