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

 

Задача об оптимальном распределении ресурсов при выпуске продукции на предприятии (об ассортименте)

 

Предположим, что предприятие выпускает n различных изделий. Для их производства требуются m различных видов ресурсов (сырья, вспомогательных материалов, рабочего и машинного времени и т.д.). Эти ресурсы ограничены и составляют в планируемый период b₁, b₂,..., b_m условных единиц.

Известны также технологические коэффициенты a_ij, которые указывают, сколько единиц i-го ресурса требуется для производства изделия j-го вида (i= j= ).

Пусть прибыль, получаемая предприятием при реализации единицы изделия j-го вида, равна c_j.

В планируемый период все показатели b_i, a_ij и c_j предполагаются постоянными.

Требуется составить такой план выпуска продукции, при реализации которого прибыль предприятия была бы наибольшей.

 

Сведем данные условия задачи в таблицу:

Виды	Вид изделия	Запасы
ресурсов			...	j	...	n	ресурсов
	a11	a12	...	a1j	...	a1n	b1
	a21	a22	...	a2j	...	a2n	b2
...	...	...	...	...	...	...	...
i	ai1	ai2	...	aij	...	ain	bi
...	...	...	...	...	...	...	...
m	am1	am2	...	am2	...	amn	bm
Прибыль	c1	c2	...	cj		cn

Допустим, что предприятие будет выпускать x_i изделий вида i. Требуется составить оптимальный план работы предприятия X={x_j}, j= , т.е. найти такие значения переменных x₁, x₂,..., x_n (объем выпуска продукции каждого вида), чтобы обеспечить предприятию получение максимальной прибыли от реализации всей продукции и чтобы на ее производство хватило имеющихся в распоряжении ресурсов.

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

® max.

Целевая функция (ЦФ) представляет суммарную прибыль.

Ограничения имеют вид:

, i= ,

X_j³ 0, j= .

Уравнения ограничений модели представляют собой ограничения задачи по объему соответствующего ресурса, в ходе выполнения плана можно использовать либо весь запас этого ресурса либо часть его.

 

Задача о смесях (рационе, диете)

 

К группе задач о смесях относят задачи по отысканию наиболее дешевого набора из определенных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Иными словами, получаемые смеси должны иметь в своем составе n различных компонентов в определенных количествах, а сами компоненты являются составными частями m исходных материалов.

 

 

Обобщенная таблица задачи о смесях выглядит следующим образом.

Компоненты, входящие в состав	Виды материалов	Необходимое количество компонентов в смеси
материалов			...	j	...	n
	a11	a12	...	a1j	...	a1n	b1
	a21	a22	...	a2j	...	a2n	b2
...	...	...	...	...	...	...	...
i	ai1	ai2	...	aij	...	ain	bi
...	...	...	...	...	...	...	...
m	am1	am2	...	am2	...	amn	bm
Цена единицы материала	c1	c2	...	cj	...	cn

Коэффициенты a_ij показывают удельный вес i-го компонента в единице j-го материала.

Обозначим через x_j количество материала j-го вида, входящего в смесь.

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

® min.

ЦФ представляет суммарную стоимость смеси.

Ограничения имеют вид:

, i= , (1)

где b_i- минимально необходимое содержание i-й компоненты в смеси.

x_j³ 0, j= .

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

 

Транспортная задача

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

Исходная информация:

a_i- количество единиц груза в i- м пункте отправления(i= );

b_j- потребность в j- м пункте назначения (j= .) в единицах груза;

c_ij- стоимость перевозки единицы груза из i- го пункта в j- й.

Обозначим через x_ij планируемое количество единиц груза для перевозки из i-го пункта в j- й.

В принятых обозначениях:

- общая (суммарная) стоимость перевозок;

=a_i - количество груза, вывозимого из i- го пункта;

=b_j - количество груза, доставляемого в j- й пункт.

В простейшем случае должны выполняться следующие условия:

, i= ,

=b_j, j= ,

.

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

® min.

ЦФ представляет суммарную стоимость перевозок.

Ограничения имеют вид:

, i= ,

, j= ,

x_ij³ 0, i= , j= .

Согласно уравнениям ограничений модели количество вывезенного груза должно быть равно количеству принятого.