1775
.pdfФедеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования «Воронежская государственная лесотехническая академия»
МЕТОДЫ ОПТИМИЗАЦИИ В РАСЧЕТАХ НА ЭВМ
Методические указания и контрольные задания для студентов 3 курса заочного обучения специальности 150200 (190601) – Автомобили и автомобильное хозяйство
Воронеж 2007
2
УДК 519.85
Методы оптимизации в расчетах на ЭВМ [Текст] : методические указания и контрольные задания для студентов 3 курса заочного обучения специальности 150200 (190601) – Автомобили и автомобильное хозяйство / М. И. Ковалева, И. И. Зашихина, Т. М. Кравец, М. Я. Грабовская. – Воронеж, 2007. – 16 с.
Печатается по решению редакционно-издательского совета ГОУ ВПО «ВГЛТА»
Рецензент д-р физ.-мат. наук, проф. кафедры математического моделирования ВГУ Ю.И. Сапронов
3
При выполнении контрольной работы необходимо соблюдать следующие требования:
1)в заголовке работы написать разборчиво свою фамилию, инициалы, шифр, номер контрольной работы и дату отправления работы в институт;
2)работу следует выполнять в отдельной тетради чернилами любого цвета (кроме красного), оставляя поля для замечаний рецензента;
3)в случае если работа не зачтена, следует исправить ошибки, указанные рецензентом. Исправленные решения, помещенные в ту же тетрадь, необходимо выслать на повторную проверку, прилагая первую рецензию.
Контрольные работы, выполненные не по своему варианту, не
рецензируются |
и высылают обратно студенту. До экзамена студенту |
|
необходимо защитить проверенную работу на кафедре математики. |
||
Каждая |
группа однотипных задач, помещенных |
в настоящих |
методических указаниях, содержат одну задачу, номер которой заканчивается знаком * вместо цифры. Эта задача приводится с кратким решением и может являться образцом при выполнении контрольной работы.
Контрольная работа №1 (математическое программирование).
№№ задач: 0-9; 10-19; 20-29. Варианты определяются по последней цифре Например, если шифр 84532, то решить необходимо задачи 2, 12, 22. 1. МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 0-9 Решить систему линейных уравнений методом Жордана-Гаусса.
0.x1+2x2+3x3+3x4=-1 2x1-x2-x3-x4=0 3x1+x2+x3 -x4=-2 -x1+2x2+x3+3x4=3
1.-x1+x2+2x3+x4=0 3x1+2x2-x3-x4=-2 4x1+ x3+3x4=3 x1+x2+x3-x4=2
2.x1+2x2+x3+x4=2 2x1+x2+2x3+x4=4 3x1+2x2-x3-x4=2 -x1+x2+3x3+3x4=3
3.x1+x2+x3+x4=1 2x1-4x2+2x4=0 2x2+2x3-x4=4 4x1-2x2+x3+x4=4
4
4.x1+2x2+3x3+4x4=5 2x1+3x2+x3+2x4=3 x1+x2+ x3-x4=2 x1-2x2-3x4=1
5.x1+x2+x3+x4=-2 -2x1-2x2 +x3 +2x4=-3 -x1+x2-x3 +3x4=0 7x1+4x2+6x3-x4=-3
6.x1+x2+x3-2x4=4
2x1+x2 +x3 +x4=3 x1+2x2+x3 +x4=3 x1+3x2 -x4=-3
7.x1+2x2+x3-3x4=2 2x1+2x2+3x3+x4=1
-x1-x2+5x3=-7 3x1-x2-x3-x4=3
8.x1+x2+x3+2x4=1 2x1-x2+x3-3x4=-2 x2+3x3 +2x4=5 -2x1-x2+x3+x4=0
9.x1+x2+x3+2x4=1 2x1-x2+x3-3x4=-2
x2+3x3 +2x4=5 -2x1-2x2+x3+x4=-6
0*. x1+x2-2x3+x4=1 3x1-x2+6x3+2x4=-1
2x1+x2-4x3 -x4=5 x1+x2+x3+2x4=1 2x1-x2+x3-3x4=-2
Решение задачи 0*.
1) Выпишем расширенную матрицу системы:
1 |
1 |
-2 |
1 |
1 |
3 |
-1 |
6 |
2 |
-1 |
2 |
1 |
-4 |
-1 |
5 |
|
|
|
|
5 |
5 |
0 |
2 |
3 |
0 |
Возьмем 1-ую строку и какой-либо её элемент, отличный от нуля, пусть будет это первый, назовем ключевым. Умножим первую строку последовательно на (-3), (-2), (-5) и сложим соответственно со 2-ой, 3-ей и 4- ой строками, получим:
1 |
1 |
-2 |
1 |
1 |
0 |
-4 |
12 |
-1 |
-4 |
0 |
-1 |
0 |
-3 |
3 |
0 |
-5 |
12 |
-2 |
-5 |
Разделим 2-ую строку на(-4), а затем, умножая ее последовательно на (-1), (1) и (5) и складывая соответственно с 1-ой, 3-ей и 4-ой строками, получаем:
1 |
0 |
1 |
3/4 |
0 |
0 |
1 |
-3 |
1/4 |
1 |
0 |
0 |
-3 |
-11/4 |
4 |
0 |
0 |
-3 |
-3/4 |
0 |
Аналогично разделим 3-ю строку на (-3) и получим нули в 3-ем столбце:
1 |
0 |
0 |
-1/6 |
4/3 |
0 |
1 |
0 |
3 |
-3 |
0 |
0 |
1 |
11/12 |
-4/3 |
0 |
0 |
0 |
2 |
-4 |
Наконец, разделив 4-ую строку на 2 и умножая её на (1/6), (-3) и (-11/12), при этом складывая соответственно с 1-ой, 2-ой и 3-ей строками, получим :
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
3 |
0 |
0 |
1 |
0 |
1/2 |
0 |
0 |
0 |
1 |
-2 |
Восстановленная по последней матрице система имеет вид:
x1=1 x2=3 x3 =1/2 x4=-2
Таким образом, получен ответ: x1=1, x2=3, x3 =1/2, x4=-2.
10-19. Решить задачу линейного программирования графическим методом. 10. Для сохранения здоровья и работоспособности человек должен употреблять в сутки некоторое количество белков, жиров, углеводов и витаминов. Имеются два вида пищи 1 и 2. Содержание питательных веществ в 1 кг пищи каждого вида даны в таблице.
6
Питательные |
Вид пищи |
Вид пищи |
Суточная норма |
|
вещества |
1 |
|
2 |
|
Жиры |
1 |
|
10/3 |
10 |
Белки |
4 |
|
2 |
12 |
Углеводы |
2 |
|
2/8 |
14 |
витамины |
0 |
|
1 |
1 |
Стоимость 1 кг |
20 |
коп. |
24 коп. |
- |
Как нужно организовать питание, чтобы пища содержала необходимое количество питательных веществ, а стоимость ее была минимальной?
11. Для производства двух видов продукции А и В завод использует четыре группы оборудования (1, 2, 3, 4). Наличие оборудования и количество единиц каждого оборудования, необходимое для производства единицы продукции каждого вида указаны в таблице:
Вид |
|
Группы оборудования |
|
|
||
продукции |
1 |
|
2 |
|
3 |
4 |
А |
1 |
|
0 |
|
5 |
2 |
В |
1 |
|
1 |
|
0 |
2 |
Наличие |
18 |
|
12 |
|
24 |
18 |
оборудования |
|
|
|
|
|
|
Предприятие получает от одной единицы продукции А 4 рубля прибыли, а от одной единицы продукции В- 6 рублей прибыли. Сколько единиц продукции каждого вида дожжен производить завод, чтобы получить наибольшую прибыль?
12. Из четырёх видов сырья производится продукция двух наименований П1 и П2. Количество сырья, необходимое для производства единицы продукций, запасы и прибыль от реализации единицы продукции приведены в таблице:
Вид сырья |
|
Продукция |
Запасы |
|
|
П1 |
|
П2 |
|
S1 |
2 |
|
3 |
19 |
S2 |
2 |
|
1 |
13 |
S3 |
0 |
|
3 |
15 |
S4 |
3 |
|
0 |
18 |
Прибыль от |
7 |
|
5 |
- |
реализации |
|
|
|
|
Сколько единиц продукции каждого вида нужно произвести из имеющегося сырья, чтобы обеспечить максимальную прибыль?
7
13. Для откорма животных в их суточный рацион нужно включить не менее 33 единиц питательного вещества А, не менее 23 единиц питательного вещества В и не менее 12 едини питательного вещества С.В совхозе имеется два вида кормов. Количество единиц питательного вещества в 1 кг корма и стоимость 1 кг корма указаны в таблице.
Питательные вещества |
Корм 1 |
Корм 2 |
А |
3 |
2 |
В |
2 |
1 |
С |
1 |
2 |
Стоимость 1 кг |
21 коп. |
15 коп. |
Установить, какое количество корма каждого вида необходимо расходовать ежедневно, чтобы затраты на него были минимальными, а животные получали необходимое количество питательных веществ.
14.В процессе производства два изделия А и В должны пройти обработку на станках 1, 2 и 3. Время обработки каждого изделия на каждом из этих станков задано таблицей:
Станки |
1 |
2 |
3 |
Изделия |
|
|
|
А |
1 |
4 |
1 |
В |
1/4 |
2 |
4 |
Станки можно использовать соответственно в течение 45, 100 и 50 часов. Продажная цена изделия А-6 рублей, а изделия В-4 рубля. В каком соотношении следует производить изделия А и В, чтобы получить максимальную прибыль?
15. Для повышения урожайности нужно внести на 1 га почвы не менее 8 единиц химического вещества А, 21 единицы химического вещества В и 16 единиц химического вещества С. Совхоз закупает комбинированные удобрения двух видов 1 и 2. В таблице указано содержание химических веществ и цена 1 т каждого вида удобрений.
Химические вещества |
Содержание вещества в 1 т. удобрения |
|
|
1 |
2 |
А |
1 |
5 |
В |
12 |
3 |
С |
4 |
4 |
Цена 1 т.(ден.ед) |
5 |
2 |
8
Какое количество удобрений каждого вида должен закупить совхоз, чтобы расходы по закупке были минимальными?
16. Мебельная фабрика выпускает шкафы для посуды и книжные шкафы. При изготовлении товаров используется два различных типа досок. В наличии имеется 1250 м досок первого типа и 1260 м досок второго типа. Фабрика располагает трудовыми ресурсами в количестве 750 человек-часов. Затраты каждого вида ресурсов на изготовление одного изделия и прибыль от реализации одного изделия заданы таблицей.
Вид ресурса |
Затраты на одно изделие |
|
|
Шкаф для посуды |
Книжный шкаф |
Доски 1-го типа (м) |
6 |
5 |
Доски 2-го типа (м) |
7 |
3 |
Трудовые ресурсы(чел.- |
1 |
5 |
час) |
|
|
Прибыль (руб.) |
15 |
10 |
Составить производственный план, обеспечивающий получение максимальной прибыли.
17. Подопытное животное должно получать ежедневно по меньшей мере 15 единиц элемента А1 и столько же элемента А2. Содержание единиц элементов А1 и А2 в 1 кг химических веществ В1 и В2 и стоимость одного кг каждого химического вещества заданы таблицей.
Химические |
А1 |
А2 |
|
Стоимость 1 кг |
|
вещества |
|
|
|
|
|
В1 |
1 |
5 |
|
1 |
коп. |
В2 |
5 |
1 |
|
3 |
коп. |
Определить, какое количество каждого вещества В1 и В2 |
должно |
потреблять |
животное, чтобы получить необходимое количество элементов А1 и А2 по минимальной общей стоимости.
18. Эффективность возделывания пшеницы и картофеля характеризуется следующими показателями:
Показатели |
Пшеница |
Картофель |
Урожайность (ц) |
20 |
100 |
Затраты труда (чел-дни) |
0.6 |
4.6 |
Закупочная цена 1ц. |
10 |
8 |
(руб) |
|
|
9
Объем производственных ресурсов: пашня7000 га, затраты труда -4500 человекодней. Определить размеры пашни под картофель и под пшеницу для обеспечения максимальной прибыли.
19. Для производства двух видов продукции А и В завод использует четыре вида оборудования (1,2,3 и 4). Наличие оборудования, количество оборудования, необходимого для производства единицы продукции каждого вида, указаны в таблице.
Вид |
Группы оборудования |
|
|
|
продукции |
1 |
2 |
3 |
4 |
А |
2 |
0 |
3 |
1 |
В |
2 |
2 |
0 |
2 |
Наличие |
18 |
12 |
21 |
18 |
оборудования |
|
|
|
|
Предприятие получает от одной единицы продукции А 4 рубля прибыли, а от одной единицы продукции В- 6 рублей прибыли. Сколько единиц продукции каждого вида должно производить предприятие, чтобы получить наибольшую прибыль?
1*. Фабрика выпускает два вида зделий А и В. Составить ежедневный план выпуска изделий, дающий наибольшую прибыль. Необходимые данные заданы таблицей.
Вид операции |
А |
В |
Запас времени по |
|
|
|
каждой операции (час) |
Обработка станка (час) |
2 |
0 |
90 |
Штамповка (час) |
0 |
2 |
80 |
Полировка (час) |
8 |
5 |
390 |
Окраска (час) |
5 |
5 |
300 |
Прибыль от изделия (руб.) |
3 |
1 |
- |
Решение задачи 1*. Обозначим через x1 – количество изделий вида А, а через x2 – количество изделий В, выпускаемые фабрикой ежедневно. Тогда от реализации изготовленной продукции фабрика получит прибыль F(x)=3x1+x2. Из условия задачи на переменные x1 и x2 налагаются следующие ограничения:
2x1 ≤90,
2x2≤80,
8x1+5x2≤390,
5x1+5x2≤300.
10
Итак, мы получаем стандартную задачу линейного программирования
F(x)=3x1+x2 –max,
2x1 ≤90,
2x2≤80,
8x1+5x2≤390,
5x1+5x2≤300, x1≥0, x2≥0.
Решим эту задачу графическим методом. Сначала строим область допустимых решений системы неравенств (многоугольник ОАВСДЕ). Затем в этой же системе координат строим вектор С (3,1), где3 и 1 коэффициенты при соответствующих переменных в целевой функции. Строим линию уровня, перпендикулярную вектору С ,(3x1+x2 =0) и перемещаем её в направлении вектора С параллельно самой себе.
Вектор С показывает направление роста функции F(x), поэтому в точке Д функция F(x), принимает наибольшее значение в найденной области системы ограничений.
Найдем координаты точки Д как точки пересечения прямых x1=45 и bx1+5x2=390; Д(45;6). Получаем ответ: фабрика должна выпускать ежедневно 45 изделий вида А и 6 изделий вида В. При этом фабрика получает наибольшую прибыль, равную
Fmax=3*45+6=141 рубль