Экономико - математические методы и модели

   15 × х₂ + 5 × х₄  ³ 3 × z – количество заготовок В

    8 × х₃ + 4 × х₄ + 4 × х₅ ³ 2 × z – количество заготовок С,

х₁, …, х₅,  z  ³ 0.

 

 

 

 

МОДЕЛИ  ОПТИМАЛЬНОГО  СОСТАВЛЕНИЯ 

СМЕСИ (СПЛАВА)

 

Готовая продукция должна удовлетворять условиям качества. Задача состоит в выборе набора компонента с целью получения минимальных затрат: модель о смесях, сплавах, оптимальном рационе питания.

Постановка  задачи: Пусть готовая продукция должна содержать m-элементов, количество которых лимитировано конкретным числом   е_i,   i = .

1, 2,…, k – элементы ухудшающего качества;

k +1,…, m – элементы улудшающего качества.

Эта продукция может  быть получена в результате участия  каких-то  n  компонентов.

b_j,  j = – количество  j-того  компонента;

a_ij – количество i-того компонента в одной единице j-того компонента;

с_j – цена  j-того компонента;

М – количество готовой продукции;

х_j – количество  j-того  компонента.

Модель 1:  z = ® min      (1)

,     i =            (2)

,     i =     (3)

                                         (4)

x_j  £  b_j                                                (5)   – ограничение на объем имеющихся ресурсов

x_j  ³ 0.

Количество ограничений (m + n + 1),   переменных   n   штук.

Модель 2:  готовая продукция должна удовлетворять качеству. Все элементы только улучшают качество, е_i – минимальное количество i-того элемента в единице продукции. Эта продукция получается в результате   n   компонентов.

Задача: определить оптимальный  состав смеси (сплава) и целью минимизации  затрат.

 ® min                (1)

,  i =       (2)

,

x_j  £  b_j,    j =

x_j ³ 0

n-переменных

 

ПРИМЕР:

Бензин А – 76,  октановое число  не ниже 76,  сера не более 0,3 %

Показатели	Компоненты
	1	2	3	4
Октановое число Сера, % Ресурсы, т Себестоимость, руб.	68 0,35 700 40	72 0,35 600 45	80 0,3 500 60	90 0,2 300 90

Определить сколько  тонн каждого компонента требуется  для получения 1000 т бензина А  – 76, при этом себестоимость должна быть минимальной.

х₁,  х₂,  х₃,  х₄ – количество соответствующих компонентов.

z = 40 × х₁ + 45 × х₂ + 60 × х₃ + 90 × х₄   ® min

    68 × х₁ + 72 × х₂ + 80 × х₃ + 90 × х₄ ³  76 × 1000,

    0,35 × х₁ + 0,35 × х₂ + 0,3 × х₃ + 0,2 × х₄  £  0,3 × 1000,

    х₁ + х₂ + х₃ + х₄ = 1000,

    х₁ £ 700,  x₂ £ 600,  x₃ £ 500,  x₄ £ 300,

х₁,  х₂,  х₃,  х₄  ³  0

Ответ:   х₁ = 571 т,   х₂ = 0,   х₃ = 143,   х₄ = 286

х₅ = 0,  х₆ = 0, х₇ = 129,  х₈ = 600,  х₉ = 357,  х₁₀ = 14 – дополнительные переменные.

 

ПРИМЕР:

Требуется получить некую  единицу сплава, для его изготовления требуется 5 видов исходных сплавов (компонентов). Готовая продукция должна содержать 15% олова, 55 % цинка, 30 % свинца.

Показатели	Исходные сплавы (компоненты)
	1	2	3	4	5
Олово, % Цинк, % Свинец, % Стоимость ед., руб.	20 40 40 5	10 60 30 4	30 45 25 7	20 65 15 5	5 60 35 3

х₁,  х₂,  х₃,  х₄,  х₅ – структура готового сплава, количество исходных сплавов в единице готовой продукции (удельный вес).

Цель: минимум затрат.

z = 5 × х₁ + 4 × х₂ + 7 × х₃ + 5 × х₄ + 3 × х₅  ®  min

    20 × х₁ + 10 × х₂ + 30 × х₃ + 20 × х₄ +  5 × х₅ = 15,

    40 × х₁ + 60 × х₂ + 45 × х₃ + 65 × х₄ + 60 × х₅ = 55,

    40 × х₁ + 30 × х₂ + 25 × х₃ + 15 × х₄ + 35 × х₅ = 30,

     х₁ + х₂ + х₃ + х₄ + х₅ = 1

х₁,  х₂,  х₃,  х₄,  х₅  ³  0  

5 – переменных, 4 - уравнения 

 

 

 

 

 

МОДЕЛИ  ТРАНСПОРТНОЙ  ЗАДАЧИ

 

1. Закрытая модель  перевозки однородных грузов.

2. Открытая модель  перевозки однородных грузов.

3. Модель перевозки  взаимозаменяемых грузов.

4. Задача оптимального  назначения.

 

1. Закрытая модель перевозки однородных грузов:

В транспортных моделях речь идет об однородных грузах. Позволяет спланировать перевозку груза, оптимально закрепить поставщиков за потребителями.

Постановка  задачи: Предположим, что есть m пунктов отправления (m поставщиков) и n пунктов потребления.

a_i - запас груза (количество продукта  i-того поставщика);

b_j - потребность в грузе j-тому  потребителя j = ;

Поставщики и потребители  связаны транспортными сетями, для  каждого маршрута задана величина:

t_ij  -  коэффициент эффективности перевозки груза от  i-того  поставщика к j-тому  потребителю. Требуется определить оптимальный план перевозки однородного продукта, обеспечивающий максимальную эффективность при обязательном удовлетворении спроса.

t_ij  может быть:  

-   время доставки  груза, тогда цель – минимизация затрат; 

- расстояние по соответствующему  маршруту, цель – минимизация  пробега (в тонно/километрах);  

- стоимостным показателем  – тариф перевозки единицы  груза в соответствующем маршруте.

Цель – выбрать наилучший маршрут перевозки и количество перевозимого по нему груза с целью минимума суммарных затрат. Закрытая модель перевозки  S а_i = S b_j  характеризуется тем, что сумма запасов равна сумме потребностей.

Модель 1:     ®  min     (1)

,      j =                                  (2)

,      i =                 (3)

x_ij  ³  0                                         (4)

переменных  m ´ n, ограничений   m + n

Условие закрытости модели:              (5)

В системе ограничений  коэффициенты при переменных равны  единице. Если  b_j и a_i – целые числа, то переменные тоже будут целыми числами.

Ранг  r £ m + n - 1   количество линейно не зависимых ограничений на 1 меньше, чем общее количество ограничений.   Количество не нулевых значений переменных х_ij > 0,  равно рангу

 х_ij > 0 = r.

4 поставщика, 5 потребителей:  20 переменных;  реальных поставок  будет 8. Также в эту модель  можно включать затраты  на  производство единицы продукции с_ij = t_ij + s_i,  где – суммарные затраты, с учетом минимальных затрат на транспортировку (t_ij) и производство (s_i).

Для закрытой модели решение  будет такое же (см. выше).

Целевая функция изменится 

 

2.  Открытая модель перевозки однородных грузов:

          

Модель  2:    

 ®  min         (1)

,       j =              (2)

,     i =               (3)

x_ij ³ 0

Дополнительный поставщик (m +1): а_m+1 = S b_j - S a_i, стоимость перевозки от условного поставщика равна нулю.

Потребность запасы	b1	b2	…	bn	Условие: bn+1
a1 a2 … аm  условие: аm+1	t11     x11 t21     x21 … tm1     xm1   0     xm+1, 1	t12     x12 t22     x22 … tm2    x m2     0    xm+1, 2	… … … … …	t1n       x1n t2n        x2n … tmn       xmn      0     xm+1, n	0       x1,  n+1    0       x2,  n+1 …            0       xm,  n+1

В пунктире столбец –  для второго условия

х_{m+1, 1}, x_{m+1, 2}, …, x_{m+1, n}  – дополнительные переменные, обозначающие недоставку груза соот-ветствующему потребителю.

Модель 3:    

Целевая функция  (1), ограничение   (2),    (3)  со знаком ³

условный потребитель (n +1):    b_n+1 = S а_i  - S b_j

x₁, …, x_{2, n+1}, … x_{m, n+1}  – недовостребованное количество груза

если   t_ij  Þ   c_ij  – оптимальный план изменится.

 

3. Модель перевозки взаимозаменяемых грузов.

Если груз полностью  взаимозаменяемый, то его переводят  к условным однородным единицам – коэффициентам:

B₁,  В₂ …, В_m – количество груза,  m-видов груза;

k₁,  k₂ …,  k_m – коэффициенты перевода груза в условные единицы;

k₁ × B₁,  k₂ × B₂, … k_m × B_m – условные единицы.

Если продукты не взаимозаменяемые, то в таблице каждому грузу соответствует строка и столбец. В каждой клетке, где перевозы не желательны проставляются большие транспортные тарифы, таким образом блокируется соответствующий маршрут.

 

ПРИМЕР:

Допустим   А₁, А₂ – поставщики;   B₁,  В₂,  В₃  - потребители.

Запасы груза:

Поставщики	Марка	Количество
А1	М 300 М 500	200 100
А2	М 300 М 500	300 400

Спрос:   

Потребители	Марка	Количество
B1	М 300 М 500	300 250
B2	М 300 М 500	200 100
B3	М 500	150

Транспортные затраты:

	B1	B2	B3
А1
А2

Модель транспортной задачи: 

                                                          B₁                            B₂                         B₃

Потребители Запас			М 300 300	М 500 250	М 300 200	М 500 100	М 500 150
А1	М 300 М 500	200	4	М	5	М	М
		100	М	4	М	5	6
А2	М 300 М 500	300	7	М	8	М	М
		400	М	7	М	8	9