41

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

«Хабаровская государственная академия экономики и права»

Кафедра математики и математических методов в экономике

Математическое программирование

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

для студентов первого курса дневного отделения всех специальностей

Хабаровск 2005

ББК В11

Х12

Математическое программирование: методические указания к практическим занятиям для студентов первого курса дневного отделения всех специальностей / сост. Т. Н. Беспрозванная, Л. А. Дойхен, Е. О. Старкова, С. В. Тонконог. – Хабаровск : РИЦ ХГАЭП, 2005. – 44 с.

В методических указаниях приведены решения типовых задач курса «Линейное программирование», сформулированы алгоритмы основных методов решения, а также осуществлен подбор практических заданий для самостоятельной работы.

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

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

Рецензент к.ф-м.н., доцент кафедры прикладной математики ДВГУПС

Е.Н. Ломакина

Утверждено издательско-библиотечным советом академии в качестве методических указаний

Беспрозванная Татьяна Николаевна

Дойхен Людмила Архиповна

Старкова Елена Олеговна

Тонконог Светлана Владимировна

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

Редактор Г.С. Одинцова

Подписано в печать 2005г. Формат 60 x 84 / 16. Бумага писчая.

Печать офсетная. Усл.п.л. 2,55 . Уч.-изд.л. 1,83 . Тираж 550 экз.

Заказ №

__________________________________________________________________________

680042, Хабаровск, ул. Тихоокеанская, 134, ХГАЭП, РИЦ

© Хабаровская государственная академия экономики и права, 2005

Введение

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

При огромном разнообразии задач оптимизации только математика может дать общие методы их решения.

В методических указаниях подобраны примеры по всем разделам курса «Линейное программирование»: составление математической модели задач; решение задач линейного программирования графическим и симплексным методами, методом искусственного базиса; решение двойственных задач; транспортные задачи. Подробно разобрано решение типовых задач, что позволит студентам освоить данный курс.

Рекомендуемая литература

1. Дойхен Л. А. Математическое программирование : учеб. пособ. – Хабаровск : РИЦ ХГАЭП, 2001.

2. Кузнецов Ю. А. , Кузубов В. И. , Волощенко А. Б. Математическое программирование. – М. : Высшая школа, 1980.

3. Красс М. С. , Чупрынов Б. П. Математика для экономистов. – СПб. : Питер, 2004.

4. Сборник задач по высшей математике для экономистов : учеб. пособ./ под ред. В. И. Ермакова. – М. : ИНФРА-М, 2002.

5. Тиунчик М. Ф. Руководство к решению задач по линейной алгебре и аналитической геометрии : учеб. пособ. Ч. 1. – Хабаровск : ХГАЭП, 2001.

1. Составление модели задачи линейного программирования

Для изготовления четырех видов продукции (А, Б, В, Г) используются три вида сырья .

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

Сырье	Нормы расхода				Ресурсы
	А	Б	В	Г
	8 7 2	4 1 8	3 4 2	0 1 6	7 500 2 800 5 000
Прибыль	12	11	8	6

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

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

Обозначим через выпуск продукции А, – продукции Б, – продукции В и – продукции Г. Следовательно, – план выпуска продукции.

Сырья потребуется в количестве

.

Это количество не должно превышать ресурсы сырья , т. е.

.

Аналогично по другим видам сырья получим ограничения

,

.

Подсчитаем прибыль .

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

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

достигает максимума.

Составить математические модели следующих задач:

Задача 1. Откорм животных выгоден тогда, когда каждое животное будет получать в дневном рационе не менее 6 единиц питательного вещества А, не менее 12 единиц вещества В и не менее 4 единиц вещества С. Для кормления используются два вида кормов. В таблице указано, сколько единиц каждого питательного вещества содержит 1 кг каждого вида корма.

Питательные вещества	Корм 1	Корм 2
А В С	2 2 0	1 4 4

Цена корма первого вида 5 рублей за 1 кг, второго – 7 рублей. Какое количество корма каждого вида необходимо расходовать ежедневно, чтобы затраты на рацион были минимальными?

Задача 2. При производстве двух видов продукции используются три вида сырья. Необходимо произвести не более 20 единиц продукции первого вида и не более 30 единиц продукции второго вида. Составить план выпуска продукции, обеспечивающий максимальную прибыль. Исходные данные приведены в таблице.

Запасы сырья	Расход сырья на единицу продукции
	1 вид	2 вид
20 12 30	2 1 1	1 1 3
Прибыль	40	50

Задача 3. Для выпуска определенного вида продукции могут применяться два технологических способа с различным соотношением ручного и механизированного труда. Ресурсы труда составляют 240 чел.-ч, машинного времени – 120 ч. Их затраты на выпуск единицы продукции первым способом составляют 5 чел.-ч и 2 часа машинного времени. На выпуск единицы продукции вторым способом затрачивается 8 часов рабочего времени и 3 часа машинного времени. Определить такое соотношение технологических способов, которое обеспечит производство максимального количества продукции.

Задача 4. Предприятие может выпускать продукцию трех видов: А, Б, В. Уровень выпуска лимитируется ограниченностью ресурсов – сырья, материалов и оборудования. Затраты на единицу изделия и объем ресурсов указаны в таблице.

Виды ресурсов	Объем ресурсов	Нормы затрат ресурсов на единицу продукции
		А	Б	В
Сырье, кг Материалы, кг Оборудование, 1 гр Оборудование, 2 гр	240 800 100 60	5 10 5 2	7 5 2 1	4 20 1 1
Прибыль от единицы продукции		18	12	8

Определить уровень выпуска продукции, обеспечивающий максимальную прибыль, при условии, что продукции типа В должно быть выпущено не менее 20 изделий.

Задача 5. Консервный комбинат закупает яблоки у двух фермеров. Для производства продукции ему необходимо 100 т яблок первого сорта, 60 т яблок второго сорта и 10 т – третьего сорта. Яблоки закупаются несортированные, но известно, что у первого фермера 70% яблок первого сорта и 30% – второго, у второго фермера 60% яблок первого сорта, 30% – второго и 10% – третьего. Затраты комбината на покупку и перевозку 1 т составляют 8 тыс. руб. для первого поставщика и 6 тыс. руб. для второго. Требуется осуществить закупку и перевозку яблок так, чтобы затраты были минимальными.

Задача 6. Со станции отправляются формируемые здесь пассажирские и скорые поезда. Они отличаются по количеству вагонов разных типов. Количество вагонов каждого типа ограничено. Требуется найти такое соотношение количества пассажирских и скорых поездов, чтобы общее число мест в них было максимальным. Исходные данные по комплектации поездов даны в таблице.

	Типы вагонов
	багажные	почтовые	плацкартные	купейные	св
Количество вагонов в скором	1	-	5	6	3
Количество вагонов в пассажирском	1	1	8	4	1
Количество мест в вагоне	-	-	58	40	32
Количество вагонов на станции	12	8	84	70	21

Задача 7. Грузовая автобаза, обслуживающая пять объектов строительства, развозит песок с трех карьеров суммарной производительностью 700 т песка в сутки (соответственно 250, 300, 150 т). В таблице указано расстояние от карьеров до потребителей (км).

Карьеры (поставщики)	Объекты строительства (потребители)
	1	2	3	4	5
1-й карьер 2-й карьер 3-й карьер	11 12 18	7 6 15	20 8 20	9 12 16	15 20 19

Суточные потребности на объектах соответственно равны 140, 160, 100, 120, 180 т. Составить план перевозок песка, обеспечивающий минимум объема перевозок в тонно-километрах.

Задача 8. Для пошива 120 комплектов изделий на швейной фабрике необходимо иметь заготовки материала в 2,2 м; 1,8 м; 0,7 м. Каждый рулон материала содержит 20 метров. Найти такие способы раскроя материала, чтобы количество использованных рулонов было минимальным (при сохранении комплектности).

Задача 9. Необходимо изготовить 80 комплектов заготовок трех видов длиной в 3 м, 2,4 м и 1,8 м из стержней длиной 7,8 м. Найти способы раскроя и определить, какие из способов раскроя следует выбрать, чтобы число используемых стержней было минимальным.

Задача 10. Для изготовления столов и шкафов употребляют два вида древесины. Расход древесины каждого вида на каждое изделие задан в таблице (в куб. м).

Изделие	Древесина		Доход от изделия (в руб.)
	1 вид	2 вид
Стол Шкаф	0,15 0,3	0,2 0,1	2 200 2 500
Количество древесины	60	40

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

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

Исходный продукт	Расход исходных продуктов на 1 кг мороженого		Запас, кг
	сливочное	шоколадное
Молоко	0,8	0,5	400
Наполнитель	0,4	0,8	365

Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Отпускная цена 1 кг сливочного мороженого 16 ден. ед., шоколадного – 14 ден. ед.

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

Задача 12. В суточный рацион цыплят включают два продукта питания, П₁ и П₂, причем продукта П₁ должно войти в дневной рацион не более 200 ед. Стоимость 1 ед. продукта П₁ составляет 2 ден. ед., продукта П₂ – 4 ден. Ед. Содержание питательных веществ в 1 ед. продукта, минимальные нормы потребления указаны в таблице.

Питательное вещество	Минимальная норма потребления, ед. / день	Содержание питательных веществ в 1 ед. продукта
		П1	П2
А	120	0,2	0,2
В	160	0,4	0,2

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

Задача 13. «Металлургический завод» из металлов А₁, А₂, А₃ может выпускать сплавы В₁, В₂, В₃. В течение планируемого периода завод должен освоить не менее 640 т металла А₁ и 800 т металла А₂, при этом металла А₃ может быть израсходовано не более 860 т.

Определить минимальные затраты; данные о нормах расхода и себестоимость даны в таблице.

Вид металла	Технологическая норма расхода металла на условную единицу сплава			Наличие запаса металла у завода
	В1	В2	В3
А1	1,0	4,3	2,6	640
А2	5,0	1,5	3,0	800
А3	3,0	3,9	4,3	860
Себестоимость 1 т сплава, ден. ед.	18	15	15	-

Задача 14. Обработка деталей вида А и В может производиться на трех станках. Причем каждая деталь при ее изготовлении должна последовательно обрабатываться на каждом из станков. Прибыль от реализации детали вида А – 100 ден. ед., детали вида В – 160 ден. ед. Исходные данные приведены в таблице.

Станок	Норма времени на обработку одной детали, ч		Время работы станка, ч
	А	В
1	0,2	0,1	100
2	0,2	0,5	180
3	0,1	0,2	100

Определить производственную программу, максимизирующую прибыль при условии: спрос на деталь вида А не менее 300 шт., на деталь вида В – не более 200 шт.

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

Вид ресурса	Объем ресурсов	Норма расхода
		1	2	3
Станки 1-го типа	30	20	10	25
Станки 2-го типа	45	8	20	10
Пряжа	30	120	180	210
Красители	1	10	5	8
Цена, ден. ед.	-	15	15	20

Определить оптимальный ассортимент, максимизирующий объем товарной продукции предприятия.