УРАЛЬСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ ВЕТЕРИНАРНОЙ МЕДИЦИНЫ

Кафедра математики и информатики

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

Троицк, 2007

Математическое программирование: Методические рекомендации по изучению дисциплины и задания для организации самостоятельной работы студентов. Предназначены для студентов 3 курса, факультета товароведения.

Составитель: О. П. Белоусова, и.о. доцента кафедры математики и информатики ТФ ГОУВПО «Уральской Государственной академии ветеринарной медицины».

УДК

Рецензенты:

С. В Нужнова, канд. пед. наук, зав. каф. математики и информатики ТФ ГОУВПО «Челябинского Государственного университета»;

В. П. Салимбаева, зав. каф. математики и информатики ТФ ГОУВПО «Уральской Государственной академии ветеринарной медицины».

Рассмотрена на заседании кафедры математики и информатики ТФ ГОУВПО УГАВМ

(протокол № от ).

Утверждена методической комиссией факультета товароведения ТФ ГОУВПО УГАВМ

(протокол № от ).

Введение

Основная задача темы «Математическое программирование» - овладение студентами конкретными математическими знаниями и умениями решения оптимизационных задач, необходимыми для применения в профессиональной деятельности.

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

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

Тема № 1. Теоретичес­кие основы методов линейного программирования.

Математическое программирование, линейное про­граммирование, общая постановка задачи линейного программирования, экономико-математическую модель задачи, оптимальное решение или оптимальный план. .

Содержание основных понятий темы

Математическое программирование - это прикладная отрасль математики, которая является теоретической основой решения задач оптимального планирования.

Существуют следующие разделы математического программирова­ния: линейное, параметрическое, нелинейное и динамическое про­граммирование.

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

Прежде чем применять математические методы для решения задач экономики, нужно выразить экономическое содержание задачи через определенные математические зависимости, т. е. составить экономико-математическую модель задачи.

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

дана линейная функция , которая называется линейной формой или целевой функцией;

система ограничений и неравенств

дополнительные условия

Экономико-математическая модель задачи: найти такое решение , удовлетворяющее системе ограничений и дополнительным условиям, при котором, линейная функция принимает оптимальное (т.е. максимальное или минимальное) значение.

Алгоритм составления экономико-математической модели задачи нахождения максимума целевой функции.

Составить экономико-математическую модель задачи об использовании ресурсов. Для изготовления n видов продукции используют m видов ресурсов. Запасы ресурсов b_i, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, a_ij, и прибыль, получаемая от единицы продукции, c_i, известны. Необходимо составить такой план производства продукции, при котором прибыль от её реализации будет максимальной.

Алгоритм решения:

1. Написать общую задачу линейного программирования вида:

2. Записать число видов продукции n.

3. Записать число видов ресурсов m.

4. Записать величины a_ij.

5. Записать величины b_i.

6. Записать величины c_i.

7. Записать экономико-математическую задачу об использовании ресурсов.

Задача 1.

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

Вид сырья	Нормы расхода сырья на 1 изделие, кг		Общее количество сырья, кг
	А	В
1	12	4	300
2	4	4	120
3	3	12	252
Прибыль от реализации 1 изделия, кг	30	40

Решение.

1. Написать общую задачу линейного программирования вида

2. Записать число видов изделий n.

n=2.

3. Записать число видов сырья m.

m=3.

4. Записать величины a_ij.

a₁₁=12; a₁₂=4; a₂₁=4; a₂₂=4; a₃₁=3; a₃₂=12.

5. Записать величины b_i.

b₁=300; b₂=120; b₃=252.

6. Записать величины c_i.

c₁=30; c₂=40.

7. Записать поставленную экономико-математическую задачу об использовании ресурсов.

Составить такой план производства , где х₁, х₂ число изделий видов А и В соответственно, удовлетворяющий системе ограничений и дополнительным условиям, при котором, линейная функция F, обозначающая прибыль производства, принимает максимальное значение.

Алгоритм составления экономико-математической модели задачи нахождения минимума целевой функции.

Составить экономико-математическую модель задачи составления рациона питания. Имеется n видов кормов, содержащих m питательных веществ. Содержание числа единиц питательных веществ в 1 кг каждого вида корма a_ij, необходимый минимум питательных веществ b_i, а также стоимость 1 кг корма c_i известны. Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела.

Алгоритм решения:

1. Написать общую задачу линейного программирования вида:

2. Записать число кормов каждого вида n.

3. Записать число питательных веществ m.

4. Записать величины a_ij.

5. Записать величины b_i.

6. Записать величины c_i.

7. Записать экономико-математическую задачу составления рациона.

Задача 2.

Рацион для питания животных на ферме состоит из двух видов кормов I и II. Килограмм корма I стоит 80 руб. и содержит: 1 ед. жиров, 3 ед. белков, 1 ед. углеводов. Килограмм корма 2 стоит 10 руб. И содержит: 3ед. жиров, 1 ед. белков и 8 ед. углеводов. Составить наиболее дешевый рацион питания, обеспечивающий жирами не менее 6 ед., белками не менее 9 ед., углеводами не менее 8 ед.

Представим данные в таблице.

Питательное вещество (витамин)	Число единиц питательных веществ в 1 кг корма		Необходимый минимум питательных веществ
	I	II
Жир	1	3	6
Белок	3	1	9
Углевод	1	8	8
Стоимость 1 кг корма, руб.	80	10

Требуется составить экономико-математическую модель.

Решение.

1. Написать общую задачу линейного программирования.

2. Записать число кормов каждого вида n.

n=2.

3. Записать число питательных веществ m.

m=3.

4. Записать величины a_ij.

a₁₁=1; a₁₂=3; a₂₁=3; a₂₂=1; a₃₁=1; a₃₂=8.

5. Записать величины b_i.

b₁=6; b₂=9; b₃=8.

6. Записать величины c_i.

c₁=80; c₂=10.

7. Записать поставленную экономико-математическую задачу составленного рациона.

Составить рацион питания животных, где х₁ и х₂ число килограмм кормов I и II соответственно, удовлетворяющий системе ограничений и дополнительным условиям, при котором, линейная функция F обозначающая его стоимость принимает минимальное значение.

Самостоятельно решите следующие задачи:

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

Вид сырья	Нормы расхода сырья на 1 изделие, кг				Запасы сырья, кг
	А	Б	В	Г
1	1	2	1	0	18
2	1	1	2	1	30
3	1	3	3	2	40
Прибыль от реализации 1 изделия, руб.	12	7	18	10

Составить экономико-математическую модель на максимум общей стоимости выпускаемой продукции.

1.2. Совхоз закупает удобрения двух видов. В единице массы удобрения I вида содержатся 3 усл. ед. химического вещества а, 2- вещества b и 1 - веще­ства с; в единице массы удобрения II вида - 1 усл. ед., вещества а, 1 - вещест­ва b и 1- вещества с. На 1 га почвы необходимо внести не менее 9 усл. ед. веще­ства а, 8 - вещества b, 6 - вещества c. Составить наиболее экономичный план закупки удобрений (в расчете на 1 га), если цены удобрений (на 1 ед. массы) та­ковы: I вида - 3 ден. ед., II вида - 2 ден, ед.

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

Вид сырья	Нормы расхода сырья на 1 изделие, кг			Запасы сырья, кг
	1-й вид	2-й вид	3-й вид
1	1	2	1	430
2	3	0	2	460
3	1	4	0	420
Прибыль от реализации 1 изделия, руб.	3	2	5

Составить экономико-математическую модель на максимум общей стоимости выпускаемой продукции.

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

Сырье	Содержание (%)
Компоненты	1	2	3	4	5
Свинец	10	10	40	60	70
Цинк	10	30	50	30	20
Олово	80	60	10	10	10
Стоимость (у.е.)	4	4,5	5,8	6	7,5

Составьте математическую модель задачи определения количества сы­рья каждого вида, чтобы изготовить с минимальной себестоимостью сплав, содержащий олова не более 30%, цинка не менее 10%, свинца не более 40%

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

Ресурсы	Нормы затрат ресурсов на единицу продукции			Запасы
	1-й вид	2-й вид	3-й вид
Труд	3	6	4	2000
Сырьё 1	20	15	20	15000
Сырьё 2	10	15	20	7400
Оборудование	0	3	5	1500
Цена	6	10	9

Составить экономико-математическую модель на максимум общей стоимости выпускаемой продукции.

1.6. Кирпичный завод выпускает кирпичи двух марок (I и II). Для производства кирпича применяется глина трёх видов (А, В и С). По месячному плану завод должен выпустить 10 усл. ед. кирпича марки 1 и 15 усл. ед. кирпича марки II. В таблице указаны расход различных видов глины для производства 1 усл. ед. кирпича каждой марки и месячный запас глины. Какова наибольшая прибыль, если известно, что от реализации 1 усл. ед. кирпича марки I завод получает прибыль, равную 4 ден. ед., а марки II – 7 ден. ед.?

Марка кирпича	Количество глины, необходимое для производства 1 усл. ед. кирпича
	А	В	С
I	1	0	1
II	0	2	2
Запасы глины, усл. ед	15	36	47

Составить экономико-математическую модель задачи.

1.7. Для производства стали определенной марки, в которую в качестве легирующих веществ должны входить химические элементы К, L, Р, можно заку­пать шихту двух видов (I и II). В табл. 15.5 указано, сколько требуется каждого из этих элементов, для производства 100 т стали (по технологии можно немного больше, но меньше - нельзя). Содержание этих элементов в каждой тонне шихты, а также стоимость 1 т шихты каждого вида также приведены в таблице.

Вид шихты	Стоимость 1 т шихта	Легирующие вещества
		K	L	P
I	3	3	2	1
II	2	1	1	1
Необходимое количество легирующих веществ		9	8	6

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

8. Требуется составить смесь, содержащую три химических вещества А, В, С. Известно, что составленная смесь должна содержать вещества А не менее 6 ед., вещества В не менее 8 ед., вещества С не менее 12 ед. Вещества А, В, С содержатся в трех видах продуктов – I, II, III в концентрации, указанной в таблице.

Химические вещества	Продукты			Необходимый минимум химических веществ
	I	II	III
А	2	1	3	6
В	1	2	1,5	8
С	3	4	2	12
Цена 1 ед. продукта.	2	3	2,5

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

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

Ингредиенты	Виды зерна, кг			Необходимый минимум химических веществ
	I	II	III
А	2	3	7	1250
В	1	1	0	250
С	5	3	0	900
D	0,6	0,25	1	232,5
Цена 1 ед. продукта.	41	35	96

1.10. Для производства комплектной продукции требуется изго­товить два вида изделий. Их изготовление может быть поста­влено на каждом из пяти типов предприятий; производственная мощность предприятий и количество предприятий каждого типа указаны в таблице:

Тип предприятия	Число предприятий	Производственная мощность одного предприятия в тысячах
		по изделию 1	по изделию 2
1	5	100	15
2	3	400	200
3	40	20	25
4	9	200	20
5	2	600	250

Определить, сколько предприятий каждого типа надо поста­вить на производство первого и сколько на производство вто­рого изделий, чтобы обеспечить максимум выпуска комплектов, если в каждый комплект должно входить два изделия 1-го вида и одно второго. Составить математи­ческую модель задачи.

1.11. Продукцией городского молочного завода являются мо­локо, кефир и сметана, расфасованные в бутылки. На производ­ство 1 т молока, кефира и сметаны требуется соответственно 1010, 1010 и 9450 кг молока. При этом затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 машино/ч. На расфасовке 1 т сметаны заняты специальные авто­маты в течение 3,25 ч. Всего для производства цельномолочной продукции завод может использовать 136 000 кг молока. Основ­ное оборудование может быть занято в течение 21,4 машино/ч, а автоматы по расфасовке сметаны — в течение 16,25 ч. Прибыль от реализации 1 т молока, кефира и сметаны соответственно рав­на 30, 22 и 136 руб. Завод должен ежедневно производить не менее 100 т молока, расфасованного в бутылки. На производство другой продукции не имеется никаких ограничений.

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