Экономико-математические модели задач о смесях

Размещено на http://www.allbest.ru/

Содержание

Введение

Глава 1. Теоретические аспекты задач о смесях

1.1 Задача о диете

1.2 Задача оптимального составления смесей при производстве бензина различных сортов

1.3 Задача формирования оптимальной шихты

1.4 Задача о смешивании волокон

Глава 2. Практическая часть

Заключение

Список литературы

Введение

Во многих отраслях промышленности (химической, нефтехимической, металлургической, пищевой и других) готовая продукция получается путём смешивания, соединения, сплава различных видов исходного сырья и материалов. При этом качество готовой продукции должно соответствовать определённым требованиям, установленным стандартами и техническими условиями. Например, на металлургических заводах определяется состав смеси для производства чугуна и стали заданного качества, нефтеперерабатывающих - состав смеси нефтепродуктов для производства бензина различных сортов, на хлебозаводах - состав исходных продуктов для выпечки определённого сорта хлеба и т. д.

Большое количество компонентов смеси, разнообразие их технико- экономических характеристик делает рассматриваемую задачу весьма сложной. В связи с этим возникает проблема оптимального сочетания исходных составляющих, при котором бы достигался максимальный экономический эффект. Оптимизация состава исходных компонентов для получения готовой продукции представляет собой экономико-математическую задачу особого рода, которая называется «задачей о смесях». Для решения такого типа задач используется линейное программирование и, в частности, симплекс-метод. С его помощью можно найти такой набор компонентов смеси, при котором продукция заданного качества получается при минимальной стоимости смеси.

Следует отметить, что данная тема недостаточно освещена в литературе. При выполнении данной курсовой работы использовались, например, работы следующих авторов, таких как Кузнецов Ю.Н., Мельник М.М., Холод Н.И. Ларионов А.И., и других.

Авторы обычно ограничиваются рассмотрением лишь задачи о диете, хотя существуют и другие виды задач данного типа. Так, например, в учебнике Кузнецова «Экономико- математические методы и модели» подробно рассмотрены модели формирования оптимальной шихты при выплавке чугуна и смешивания волокон. Модель оптимального составления смесей при производстве бензина различных сортов представлена в книге Г.С. Малика «Основы экономики и математические методы в планировании». В работе В.П.Хруцкого «Экономико-математические методы в планировании материально-технического снабжения» достаточно полно рассмотрена модель оптимизации шихты для выплавки стали с учётом всех фаз технологического процесса.

Целью данной работы является рассмотрение различных экономико-математических моделей задач о смесях. Курсовая работа состоит из двух глав. Первая глава включает четыре пункта, посвящённые теоретическим аспектам рассматриваемой проблемы.

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

Курсовая работа позволяет изучить теоретические основы предмета «Экономико - математические методы и модели», приобрести необходимые навыки в составлении математических моделей для экономических задач, освоить основные способы их решения.

Глава 1. Теоретические аспекты задач о смесях

1.1 Задача о диете

На практике нередко возникают задачи, связанные с осуществлением выбора конкретного набора продуктов, обеспечивающего необходимый рацион питания, например, для животных на животноводческих комплексах по каким-то показателям.

В ситуации, которая будет рассматриваться, требуется выбрать самый дешёвый пищевой рацион, содержащий необходимое количество указанных заранее питательных веществ [1, с. 78]. При этом допускается, что:

- известен перечень биологически необходимых питательных веществ и их минимальная норма;

- задан набор продуктов, из которых требуется составить пищевой рацион;

- имеются нормы содержания различных питательных веществ в единице соответствующего продукта, например, в килограмме;

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

Пусть в рацион должно входить m биологически необходимых веществ, обозначим их индексом i. Известно, что i-ого питательного вещества должно быть не меньше, чем b_i единиц. Предположим, что мы располагаем n различными продуктами, из которых составляется пищевой рацион. Эти продукты занумеруем индексом j. Норму содержания i-ого питательного вещества в j-ом продукте обозначим через a_ij, считая, что эти числа известны по данным диетологии для любого i и j, где i=1,..,m, j=1,..,n. Другими словами, нам известна матрица, состоящая из mЧn чисел a_ij (см. таблицу 1). Обозначим цену единицы j-ого продукта за c_j, а количество j-ого продукта, входящего в пищевой рацион, за x_j. Тогда пищевой рацион в целом можно записать в виде вектора: X=(x₁, x₂,…, x_n).

В этих обозначениях выбор самого дешёвого рациона, удовлетворяющего перечисленным выше требованиям, сводится к решению следующей задачи найти вектор X=(x₁, x₂,…, x_n), удовлетворяющий системе ограничений:

, i=1,…,m (1)

x_j ? 0 , j=1,..,n (2)

и доставляющей целевой функции минимальное значение.

F(x)= (3)

Таблица 1

Питат. в-ва	Продукты
	1	2	…	n
1	a11	a12	…	a1n
2	a21	a22	…	a2n
…	…	…	…	…
m	am1	am2	…	am n

Ограничение (1) для каждого i означает, что в выбираемом рационе i-ого питательного вещества должно содержаться не менее, чем b_i единиц. Ограничение (2) формализует тот факт, что j-ый продукт может либо входить в рацион (x_j>0), либо не входить (x_j=0). Иногда рассматривается несколько видоизменённая система, в которой целевая функция оценивает вес выбранного набора. Другими словами рассматривается следующая задача: найти вектор-план, удовлетворяющий ограничениям (1) и (2) и доставляющий минимальное значение целевой функции:

F(x)=(4)

Здесь с_j вес единицы j-ого продукта питания. Если некоторые продукты измеряются в весовых единицах, то соответствующие с_j равны 1, если в штуках, то соответствующие с_j положительные числа. К этой задаче приводят ситуации, в которых необходимо обеспечить достаточное количество питательных веществ, при минимальном весе пищевого набора, например при комплектовании рюкзака. Отсюда и название задачи - задача о рюкзаке.

Следует отметить, что рассматриваемая модель обладает существенным недостатком: в ней не учитываются пищевые качества продуктов, что делает её очень условной и малопригодной для составления в нормальных условиях пищевого рациона человека. Но при моделировании ситуаций, в которых вкусовые качества пищи не играют значительной роли, модель (1) - (3) используется достаточно эффективно: например, при выборе рациона для откорма животных.

В связи с этим она получила ещё одно название: задача о кормах или задача о смесях.

1.2 Задача оптимального составления смесей при производстве бензина различных сортов

Для получения r сортов бензина используется n различных исходных материалов. Химический состав каждого сорта бензина определяется содержанием в нём m химических элементов.

Известны также следующие величины:

A_j -количество j-ого исходного материала (j=1,.., n);

B_k -количество бензина k-ого сорта по плану (k=1,.., n);

h_ij -содержание i-ого химического элемента в единице j-ого исходного материла (i=1,.., m; j=1,.., n);

H_ik -содержание i-ого химического элемента в бензине k-ого сорта (i=1,.., m; k=1,.., r);

s_k - отпускная цена бензина k-ого сорта (k=1,..r);

c_j -цена единицы j-ого исходного материала (j=1,..,n).

Требуется определить, в каких количествах должны смешиваться исходные материалы, чтобы данные сорта бензина выпускались в соответствии с планом и заданным химическим составом при условии получения максимальной прибыли от реализации бензина [4, с. 102].

Обозначим через x_jk (j=1,..,n; k=1,..r) количество j-ого исходного материала, расходуемое на бензин k-ого сорта.

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

>мах (5)

(j=1,..n), (6)

(k=1,..r), (7)

(i=1,..,m; k=1,..,r), (8)

x_jk ?0

Данная модель имеет три группы ограничений:

1) по количеству поступающих исходных материалов (нефтепродуктов);

2) по плановому выпуску бензинов;

3) по химическому составу бензинов;

Максимизируется в данной задаче разность между отпускной ценой и ценой исходных материалов, затрачиваемых на их производство.

1.3 Задача формирования оптимальной шихты

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

Процесс производства металла рассматривается не как выплавка его из смеси разных шихтовых материалов, а как смешивание металлов разного химического состава, каждый из которых как бы выплавлен из разных видов шихтовых материалов. Переменными в такой модели являются доли гипотетических металлов. Этим переменным придаётся оценка, равная цене шихтового материала, из которого они получены, с учётом нормы расхода на 1-й тонны качественного металла плюс издержки по переработке в таком же исчислении.

Построение конкретной модели подбора шихты для доменной плавки чугуна было применено в 1956 г. на металлургическом заводе в США.

Подбор шихты проводился из 11 видов шихтовых материалов, в состав которых входили руды разных сортов и марок. Техническая характеристика и химический состав этих материалов известны. Известна так же их цена за 1 т. Задача состояла в том, чтобы подобрать из указанных 11 видов материалов такой состав шихты, который [3, с. 124]:

а) обеспечивал бы заданный химический состав выплавленного чугуна;

б) позволял бы нормально вести процесс плавки;

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

Основные ограничения в данной задаче определяются химическим составом чугуна. Они установлены по трём элементам: марганцу (= a %), сере (? b %), и фосфору (? c %). Искомыми переменными в данной задаче являются доли чугуна из разных шихтовых материалов в общей выплавке, а это означает, что сумма всех переменных должна быть равна единице (=1).

Математически данная задача формулируется следующим образом: необходимо найти минимальное значение целевой функции

f = (9)

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

,(10)

,(11)

, (12)

, (13)

x_j ? D_j и x_j ? 0, где (j=1,..,11), (14)

где, j-разные сорта шихтовых материалов;

x_j- искомые переменные - доли чугуна из различных шихтовых материалов в общей выплавке; M_j, S_j, P_j- соответственно процент марганца, серы, фосфора в чугуне, получаемом из материала j- ого сорта;

D_j- дополнительные ограничения доли переменных x_j d в общей выплавке;

c_j- издержки на одну тонну чугуна гипотетически выплавляемого из материала j-ого сорта;

f- общие издержки на 1 тонны чугуна, выплавляемого из материала j-ого сорта.

Рассмотрим теперь задачу на построение экономико-математической модели на оптимизацию шихты для выплавки стали.

При построении этой модели необходимо иметь ввиду следующее: шихтовые материалы вводятся в печь не сразу, а по фазам процесса (между тем различные варианты распределения компонентов шихты по фазам существенно влияют на издержки производства стали); расход шихтовых материалов в значительной мере зависит от параметров технологического процесса. Для упрощения данной задачи используют различные приёмы, в числе которых можно отметить следующие:

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

б) число фаз процесса ввода шихтовых материалов принимается равным трём: основная садка, восстановление и доводка;

в) для каждого варианта технологического процесса методами линейного программирования рассчитывается оптимальная шихта;

г) окончательный вариант выбора технологического процесса и, следовательно, состав шихты по фазам требует дополнительного экономического анализа.

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

Примем следующие обозначения:

i - фазы технологического процесса (i=1,2,3);

j - компоненты шихты (j=1,..,n);

s - химические элементы, содержащиеся в стали (s=1,..,r);

a^(s) - допустимый процент s-ого элемента в стали;

a_i^(s) , a_i^-(s) - нижний и верхний пределы процентного содержания s-ого элемента на i-ой фазе технологического процесса;

a_ij^(s) - процент s-ого элемента, содержащегося в стали, которая отвечает j - ой составляющей шихты и i-ой фазе технологического процесса;

c_ij - издержки производства 1 тонны стали, которая гипотетически могла бы быть получена из j-ой компоненты шихты, введённой в печь на i-ой фазе технологического процесса;

d_j - определяемая технологическими требованиями и ресурсами максимальная доля стали, приходящаяся на j-ую компоненту шихты;

x_ij - доля гипотетической стали, выплавляемой из j-ого шихтового материала на i-ой фазе технологического процесса.

Целевая функция заключается в минимизации издержек производства стали, что в соответствии с принятыми допущениями означает сведение к минимуму суммарных затрат на производство 1 тонны стали как смеси из металла, выплавленного из отдельных видов шихтовых материалов на разных фазах технологического процесса:

min z=. (15)

Ограничения, которые выражают технологические условия, связанные с химическим составом плавки на отдельных её фазах можно записать в виде соотношения:

a_i^(s) ?? a_i^-(s) (i=1,2,3; s=1,..r). (16)

Ограничения по химическому составу стали записываются в виде неравенства:

? a^(s) (s =1,..,r). (17)

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

(j=1,..,n) (18)

Кроме того, должны соблюдаться следующие условия:

и x_ij ?0, (i=1,2,3; j=1,..,n).(19)

1.4 Задача о смешивании волокон

Рациональное смешивание волокон имеет важное значение, так как от выбранной смеси во многом зависит ход всего технологического процесса, и соответственно качество и себестоимость выпускаемой продукции.

За критерий эффективности может быть принята стоимость смеси или суммарная стоимость пряжи, а также прядильная способность смеси или выход пряжи из смеси волокон. Могут быть выбраны и другие иные критерии. Рассмотрим задачу минимизации стоимости смеси хлопка - волокна так, чтобы средние технологические показатели и выход пряжи были бы не хуже плановых. Для формализации данной задачи введём следующие обозначения: x_i - доля i-ого компонента в смеси (i=1,..,m);

c_i - стоимость весовой единицы i-ого компонента;

w_i - процент выхода пряжи из i-ого компонента;

l_i - средняя длина волокон i-ого компонента;

P_i - средняя прочность одиночного волокна i-ого компонента;

N_i - средний номер волокна i-ого компонента смеси;

w - планируемый процент выхода пряжи из смеси;

l' - верхний допускаемый предел средней длины волокна в смеси;

l” - нижний допускаемый предел средней длины волокна в смеси;

P - планируемая средняя прочность волокна в смеси;

N - планируемый средний номер волокна в смеси;

bi - ограничение ввода в смесь i-ого компонента.

Математически задача формулируется так: найти вектор X=(x₁, x₂,..,x_m),- смесь волокон, минимизирующий целевую функцию - стоимость смеси:

F(x)= (20)

ограничительных условиях:

, (21)

, (22)

, (23)

l”?? l', (24)

, (25)

0 ? x_i ? b_i . (i=1,..,m) (26)

Качество смеси может быть улучшено, если после нахождения вектора X₁=(x₁, x₂,..,x_m), минимизирующего стоимость смеси, осуществляется вторичное решение задачи на отыскание вектора X₂=(x₁, x₂,..,x_m), максимзирующего среднюю прочность волокна в смеси или среднюю разрывную длину волокна в смеси. В этом случае экономико-математическая модель задачи будет состоять из двух частей: задачи (20)- (26) и задачи

F(x)=>max (27)

при ограничениях (21),(23) - (26) и

, (28)

где c-величина, численно равная найденному минимуму стоимости смеси F(x) при заданных условиях (20) - (26).

Глава 2. Практическая часть

Max z = x₁+2x₂+х₃

x_j ? 0, j = 1,2,3

Канонический вид задачи

Max z = x₁+2x₂+х₃+0х₄+0х₅

x_j ? 0, j =1,2,3,4,5

Таблица 2

Базис	СjБ	bj	1	2	1	0	0	?
			х1	х2	х3	х4	х5
X4 X5	0 0	14 12	3 6	4 0	0 4	1 0	0 1	14/3 ---
Zj-cj	0	-1	-2	-1	0	0
X2 X5	2 0	14/4 12	3/4 6	1 0	0 4	1/4 0	0 1	--- 3
Zj-cj	7	0,5	0	-1	0,5	0
X2 X3	2 1	14/4 3	3/4 6/4	1 0	0 1	1/4 0	0 1/4
Zj-cj	10	2	0	0	0,5	0,25

Т.к. в индексной строке нет отрицательных элементов,

то план х₁ = 0; х₂ = ; х₃ = 3 оптимален.

Z_max= 10.

Ответ: х₁ = 0, х₂ = 3,5, х₃ = 3. Z_max= 10.

Min z = 8x₁ + 18x₂ + 6х₃

x_j ? 0, j = 1,2,3.

Составим двойственную задачу:

Mах z = 12у₁ + 4у₂ + 8у₃

у_j ? 0, j = 1,2,3.

Канонический вид задачи:

Mах z = 12у₁ + 4у₂ + 8у₃+0у₄+0у₅+0у₆.

у_j ? 0, j = 1,2,3,4,5,6

Решим задачу симплекс-методом (см. табл. 3):

Таблица 3

Базис	Сj	bj	12	4	8	0	0	0	?
			х1	х2	х3	х4	х5	х6
У4 У5 У6	0 0 0	8 18 6	2 3 3	1 1 1	2 3 1	1 0 0	0 1 0	0 0 1	8/2=4 18/3=6 6/3=2
Zj-cj	0	-12	-4	-8	0	0	0
У4 У5 У1	0 0 12	4 12 2	0 0 1	1/3 0 1/3	4/3 2 1/3	1 0 0	0 1 0	-2/3 -1 1/3	4:4/3=3 12:2=6 2:1/3=6
Zj-cj	24	0	0	-4	0	0	4
У3 У5 У1	8 0 12	3 6 1	0 0 1	0,25 -0,5 0,25	1 0 0	0,75 -1,5 -0,25	0 1 0	-0,5 0 0,5
Zj-cj	36	0	1	0	3	0	2

Т.к. в индексной строке нет отрицательных элементов, то план у₁ = 1, у₂ = 0, у₃ = 3 оптимален.

f _max = 36.

Используя теорему двойственности имеем решение исходной задачи (из индексной строки): х₁ = 3; х₂ = 0; х₃= 2. Z_min= 36.

Ответ: х₁ = 3; х₂ = 0; х₃= 2. Z_min= 36.

Max z = 7x₁+2x₂

x_j ? 0, j = 1,2.

Канонический вид задачи

Max z =7x₁+2x₂+0x₃+0x₄+0x₅+0x₆

х_j ? 0, j = 1,2,3,4…6

Составим М - задачу

Max z =7x₁+2x₂+0x₃+0x₄+0x₅+0x₆ -М(х₇+х₈)

х_j ? 0, j = 1,2,3,4…8

Решим задачу симплекс-методом (см. табл. 4):

Таблица 4

Базис	Сj	bj	7	2	0	0	0	0	-М	-М
			х1	х2	х3	х4	х5	х6	х7	х8
Х3 Х4 Х7 Х8	0 0 -М -М	20 38 4 8	5 8 1 2	2 4 2 3	1 0 0 0	0 1 0 0	0 0 -1 0	0 0 0 -1	0 0 1 0	0 0 0 1
Zj-cj	0 -12М	-7 -3М	-2 -5М	0 0	0 0	0 М	0 М	0 0	0 0
Х3 Х4 Х2 Х8	0 0 2 -М	16 30 2 2	4 6 0,5 0,5	0 0 1 0	1 0 0 0	0 1 0 0	1 2 -05 1,5	0 0 0 -1	-1 -2 0,5 -1,5	0 0 0 1
Zj-cj	4 -2М	-6 -0,5М	0 0	0 0	0 0	-1 -1,5М	0 М	1 2,5М	0 0
Х3 Х4 Х2 Х5	0 0 2 0	220/15 410/15 40/15 20/15	155/15 80/15 10/15 5/15	0 0 1 0	1 0 0 0	0 1 0 0	0 0 0 1	10/15 20/15 -5/15 -10/15
Zj-cj	80/15	-85/15	0	0	0	0	-10/15
Х1 Х4 Х2 Х5	7 0 2 0	4 6 0 0	1 0 0 0	0 0 1 0	15/55 -80/55 -10/55 -5/55	0 1 0 0	0 0 0 1	10/55 20/55 -25/55 -40/55
Zj-cj	28	0	0	85/55	0	0	20/55

Т.к. в индексной строке нет отрицательных элементов, то план х₁ = 4, х₂ = 0 оптимален.

Z_mах= 28.

Ответ: х₁= 4, х₂= 0; Z_mах= 28.

Min z = x₁+2x₂+ x₃+х₄

x_j ? 0, j = 1,2,3,4 Канонический вид задачи

Min z = x₁+2x₂+ x₃+х₄+0х₅+0х₆

x_j ? 0, j = 1,2,3,4,5,6. Составим М-задачу

Min z = x₁+2x₂+ x₃+х₄+0х₅+0х₆+Мx₇.

x_j?0, j=1,2,…7.

Таблица 5

Базис	Сj	bj	1	5	1	0	0	0	М	?
			х1	х2	х3	х4	х5	х6	х7
Х5 Х7	0 М	28 28	7 1	4 2	2 4	0 7	1 0	0 -1	0 1	--- 1/7
Zj-cj	0 28М	-1 М	-2 2М	-1 4М	-1 7М	0 0	0 -28М	0 0
Х5 Х4	0 1	28 4	7 1/7	4 2/7	2 4/7	0 1	1 0	0 -1/7
Zj-cj	4	-6/7	-12/7	-3/7	0	0	-1/7

По мере вывода М-переменных из базиса М-столбцы не считаем.

Т.к. в индексной строке нет положительных элементов,

то полученный план х₁= 0, х₂ = 0; х₃= 0, х₄ = 4 оптимален, Z_min= 4.

Ответ: х₁= 0, х₂= 0, х₃= 0, х₄ = 4. Z_min= 4.

Для изготовления изделий А, В, С и Д имеется 16 единиц ресурса первого вида, 110 единиц ресурса второго вида и 104 единицы ресурса третьего вида. Стоимость единицы изделия А - 60 рублей, изделия В - 70 рублей, изделия С - 120 рублей, а изделия Д - 130 рублей. Определить максимальный выпуск продукции, если затраты ресурсов на единицу каждого вида следующие:

Таблица 6

Вид ресурса	Затраты ресурсов на единицу изделия
	А	В	С	Д
1	1	1	1	1
2	6	5	4	3
3	4	6	10	13

Пусть х₁ единиц изделия А, х₂ единиц изделий В, х₃ единиц изделий С и х₄ единиц изделий Д необходимо выпускать. Т.к. стоимость единицы изделия А - 60 рублей, то стоимость х₁ единицы изделия А - 60х₁ рублей, стоимость х₂ единицы изделия В - 70х₂, стоимость х₃ единицы изделия С - 120х₃, стоимость х₄ единицы изделия Д - 130х₄. Общая стоимость изделий: max Z = 60х₁+70х₂+120х₃+130х₄.

Так как на единицу изделия А расходуется одна единица 1-го ресурса, то х₁ - расход 1-го ресурса на х₁ изделия А.

Так как на единицу изделия В расходуется одна единица 1-го ресурса, то х₂ - расход 1-го ресурса на х₂ изделия В, и т.д.

Имеем ограничения на ресурсы:

х₁+х₂+х₃+х₄?16

6х₁+5х₂+4х₃+3х₄?110

4х₁+6х₂+10х₃+13х₄?104

По смыслу переменные х_j неотрицательны, то имеем модель в развернутом виде:

max Z = 60х₁+70х₂+120х₃+130х₄

х₁+х₂+х₃+х₄?16

6х₁+5х₂+4х₃+3х₄?110

4х₁+6х₂+10х₃+13х₄?104

x_j ? 0, j = 1,2,3,4.

Модель задачи в общем виде:

Mах z =

х_j ? 0, j =1,2,3,4; i=1,2,3.

Здесь, b_i - запас ресурсов i-го типа;

с_j - стоимость единицы изделия j-го вида;

a_ij - затраты ресурса i-го вида на изготовление единицы изделия j-го вида;

z - общая стоимость изделий;

х_j - количество единиц изделий, изготавливаемых j-м способом;

Для изготовления определенного изделия требуется три планки - одна размером 1,2 м и две по 1,5 м каждая. Для этой цели можно использовать имеющийся запас реек - 400 штук длиной по 6,5 м каждая. Определить, как разрезать все эти рейки, чтобы получить наибольшее количество вышеуказанных изделий.

Длина рейки - 6,5 метров. Составим варианты раскроя рейки.

Варианты раскроя рейки, для этого составим расчетную таблицу 7:

Таблица 7

Размер планки	Номер варианта раскроя
	1	2	3	4	5
Планка 1,2	1	2	4	-	5
Планка 1,5	3	2	1	4	-
Отходы	0,8	1,1	0,2	0,5	0,5

Пусть х_j - число реек, раскроенных j-м способом, j=1,2,3,4,5. Тогда планок размером 1,2 будет х₁+2х₂+4х₃+5х₅, а планок размером 1,5 будет 3х₁+2х₂+х₃+4х₄

Так как для изготовления определенного изделия требуется три планки - одна размером 1,2 м и две каждая по 1,5 метра, то имеем условие комплектности:

2(х₁+2х₂+4х₃+5х₅)=3х₁+2х₂+х₃+4х₄.

Количество изделий определим количеством реек размера 1,2 метра, т.е.

Max Z = х₁+2х₂+4х₃+5х₅.

Всего реек 400 штук, значит, х₁+ х₂+ х₃+ х₄ ? 400

По смыслу переменные х_j неотрицательны, т.е. х_j ? 0. Имеем модель в развернутом виде:

Max Z = х₁+2х₂+4х₃+5х₅

2(х₁+2х₂+4х₃+5х₅)= 3х₁+2х₂+х₃+4х₄

х₁+ х₂+ х₃+ х₄ ? 400

х_j ? 0; j=1,2,3,4,5

Модель задачи в общем виде:

где, с_j - количество планок размером 1,2 метра при j-м варианте раскроя;

d_j - число планок размера 1,5 метра при j-м варианте раскроя;

Пусть конфеты «Грильяж» поступают в торговую сеть фирменных магазинов в коробках с трех кондитерских фабрик А1, А2, А3. Возможности выпуска за смену для каждой фабрики составляют 740, 690, 310 коробок. Торговая сеть представлена 5 магазинами в городе. Эти магазины нуждаются в продаже этого сорта конфет в количестве 390, 310, 440, 260, 340 коробок соответственно. Затраты на перевозку одной коробки конфет заданы матрицей

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

Занесем данные в таблицу 8:

Таблица 8

Поставщики	Потребители-магазины	Мощности поставщиков
	1	2	3	4	5
1	1	2	40	35	30	А1 =740
2	3	2	35	90	25	А2 =690
3	9	6	65	120	55	А3 =310
Спрос потребителей	B1 =390	B2 =310	B3 =440	B4 =260	B5 =340

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

Пусть х_ij продукцию надо перевезти от i-й фабрики в j-ый магазин, тогда общие затраты на перевозки составят:

Min z = х₁₁ + 2х₁₂ + 4х₁₃+12х₁₄+17х₁₅+3х₂₁+2х₂₂+5х₂₃+6х₂₄+9х₂₅+ +9х₃₁+6х₃₂+9х₃₃+10х₃₄+12х₄₄

Т.к. известны возможности фабрик-поставщиков продукции, то

Т.к. известны потребности магазинов в продукции фабрик, то

По смыслу переменные х_ij неотрицательны х_ij

(1) - (4) - модель задачи в развернутом виде.

Построим начальный план методом северо-западного угла. В свободную левую верхнюю клетку записываем наименьшее из значений А₁ и В₁ (min (А_{1 ,} В₁). В нашем примере это 390. Остальные клетки в столбце будут нулевыми перевозками, т.к. потребности 1-го магазина-потребителя удовлетворены. Далее необходимо выбрать соседнюю горизонтальную и вертикальную клетку. Выбираем клетку (1,2), записываем в нее 310. Потребности 2-го потребителя удовлетворены и т.д.

Таблица 9

Фабрики-Поставщики	Потребители	Мощности поставщиков
	1	2	3	4	5
1	1 390	2 310	4 40	12	17	А1 =740
2	3	2	5 400	6 260	9 30	А2 =690
3	9	6	9	10	12 310	А3 =310
Спрос магазинов- потребителей	B1 =390	B2 =310	B3 =440	B4 =260	B5 =340

Заполненных клеток должно быть n+m-1=5+3-1=7. Это условие выполнено, т.е он базисный. Начальный план составлен.

Затраты при данном плане перевозок составят z₀=390*1+310*2+40*4+400*5+260*6+30*9+310*12=8720 денежных единиц.

Проверим план на оптимальность. Вычислим потенциалы для заполненных клеток.

U₁+V₁=1 U₂+V₃ =5

U₁+V₂=2 U₂+V₄=6

U₁+V₃=4. U₂+V₅=9

U₃+V₅=12

Положим U₁=0, тогда V₁=1, V₂=2, V₃=4, U₂=5-V₃=5-4=1,V_4-=6-U₂ =6-1=5, V₅ =9-U₂=9-1=8, U₃=12-V₅=12-8=4

Потенциалы вычислены.Для незаполненных клеток вычислим косвенные потенциалы c_ij = U_i+V_j .

c₁₄ =U₁+V₄=0+5=5?12

c_i5= U₁+V₅=0+8=817

c₂₁ = U₂+V₁= 1+1=2?3

c₂₂ =U₂ +V₂ =1+2=3 2

c₃₁ =U₃ +V₁ =4+1=5 9

c₃₂ =U₃ +V₂ =4+2=6 6

c₃₃ =U₃ +V₃ =4+4=8 9

c₃₄ =U₃ +V₄ =4+5=9 10

План не оптимален, т.к. есть c₂₂ c₂₂

Строим цикл для клетки х₂₂: х₂₂ х₂₃ х₁₃ х₁₂. min{310;400}=310; х₂₂=310, х₁₃=40+310=350, х₁₂=310-310=0; х₂₃=400-310 = 90

Фабрики-Поставщики	Потребители	Мощности поставщиков
	1	2	3	4	5
1	1 390	2 ---	4 350	12	17	А1 =740
2	3	2 310	5 90	6 260	9 30	А2 =690
3	9	6	9	10	12 310	А3 =310
Спрос магазинов потребителей	B1 =390	B2 =310	B3 =440	B4 =260	B5 =340

Проверим план на оптимальность:

смесь математический программирование линейный

U₁+V₁=1 U₂+V₃ =5

U₂+V₂=2 U₂+V₄=6

U₁+V₃=4. U₂+V₅=9

U₃+V₅=12

Пусть U₁=0, тогда V₁=1- U₁=1, V₃=4; U₂=5-4=1, V₂=2-U₂=2-1=1, V_4-=6-U₂ =6-1=5, V₅ =9-U₂=9-1=8, U₃=12-V₅=12-8=4

Проверим косвенные потенциалы:

c₁₂ =U₁+V₂=0+1=1?2

c₁₄ =U₁+V₄=0+5=5?12

c_i5= U₁+V₅=0+8=817

c₂₁ = U₂+V₁= 1+1=2?3

c₃₁ =U₃ +V₁ =4+1=5 9

c₃₂ =U₃ +V₂ =4+1=5 6

c₃₃ =U₃ +V₃ =4+4=8 9

c₃₄ =U₃ +V₄ =4+5=9 10

Т.к. для всех c_ij c_ij, то план доставки продукции фабрик оптимален

Х_опт= оптимален

При таком плане перевозок затраты будут наименьшими и составят z_min= 390*1+350*4+310*2+90*5+260*6+30*9+310*12 = 8410 денежных единиц.

Заключение

Задача о смесях находит самое широкое применении в различных отраслях промышленности. Её применение особенно актуально в ситуациях, когда необходимо получить оптимальный состав смеси, обеспечивающий необходимый уровень качества продукции, в сочетании с минимальной стоимостью сырья. Так, очень часто возникает проблема составления рациона питания, обеспечивающего необходимое количество питательных веществ, в сочетании с минимальной стоимостью продуктов. В металлургической промышленности решается задача о составлении оптимальной шихты при производстве чугуна и стали. Причём в данном случае различные шихтовые материалы представляют собой не просто компоненты смеси, но одновременно как бы факторы выплавки металла, от которых зависит сам технологический процесс плавки. Задача составления смесей при производстве бензина различных сортов с заданным химическим составом при максимизации прибыли актуальна для нефтехимической промышленности. Часто возникает задача смешивания волокон. Поскольку удельный вес стоимости сырья в стоимости пряжи составляет в среднем 80-90 %, поэтому оптимизация смешивания волокон позволит значительно повысить эффективность производства как за счёт технологических характеристик смешиваемых волокон, так и за счёт их стоимости.

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

Вторая часть курсовой работы - практическая. Здесь содержится решение 4-х задач линейного программирования с помощью различных приемов. Для решения этих задач используется основной метод математического программирования - симплекс-метод. Для двух экономических задач построены математические модели, в общем и развернутых видах, даны определения используемым переменным. Также здесь самостоятельно составлена задача транспортного типа. Решение этой задачи начинается с построения экономико-математической модели, затем строится начальный план задачи методом северо-западного угла. Далее приводится решение задачи методом потенциалов. Решения задач помещены в таблицы, что делает их более наглядными.

Курсовая работа способствует усвоению теоретического материала по курсу “Экономико-математические методы и модели”, и позволяет приобрести навыки в решении задач и составлении экономико-математических моделей.

Литература

1. Кузнецов А.В., Холод Н.И. Математическое программирование: Учеб. пособие для экономических спец. Вузов. - Мн.: Вышэйшая шк., 1984.

2. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию. Учеб. пособие, 2-е изд. - Мн.: Вышэйшая шк., 2001.

3. Малик Г.С. Основы экономики и математические методы в планировании. - М.: Высшая шк., 1988.

4. Холод Н.И., Кузнецов А.В., Жихар Я.Н. и др. Под общей редакцией А.В.Кузнецова. Экономико-математические методы и модели. - Мн.: БГУ, 1999.

5. Математические методы в планировании отраслей и предприятий: Учеб. Пособие для экономических вузов и факультетов / Под ред. Попова И.Г. - 2-е изд., перераб. и доп. - М.: Экономика, 1981.

6. Мельник М.М. Экономико-математические методы и модели в планировании и управлении материально-технического снабжения: Учебник для экон. спец. Вузов. - М.: Высшая школа, 1990.

7. Пахабов В.И. Экономико-математические методы и модели: Учебное пособие для студентов экономических специальностей / В.И. Пахабов, Д.Г.Антипенко, М.Н.Гриневич. - Мн.: БНТУ, 2003.

8. Ларионов А.И., Юрченко Т.И. Новоселов А.Л. Экономико-математические методы в планировании. - М.: Высшая шк., 1991.

Размещено на Allbest.ru