МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«ЧЕРЕПОВЕЦКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

_________________________________________________________

Институт информационных технологий

Кафедра автоматизации и управления

Методические указания по выполнению лабораторных работ

по дисциплине «Математические методы оптимизации» для студентов специальностей 22.03.01, 22.02.01

Череповец

2008

Содержание

1	Введение ………………………………………………………………….	4
2	Создание экономико-математических моделей для задач линейного программирования …………………………………………………………	5
3	Графический метод решения задач линейного программирования…….	10
4	Нахождение опорного решения ЗЛП методами Гаусса и М-базиса…….	14
5	Решение задач линейного программирования симплекс-методом	24
6	Решение двойственных задач линейного программирования …………	33
7	Решение транспортных задач…………………………………………….	42
8	Литература	49

Введение

Данные методические указания предназначены для выполнения лабораторных работ по дисциплине «Математические методы оптимизации» для студентов специальностей 22.03.01, 22.02.01 при самостоятельном изучении и закреплении материала по следующим темам:

• графический метод решения задач линейного программирования;

• решение двойственных задач линейного программирования;

• нахождение опорного решения ЗЛП методами Гаусса и М-базиса;

• создание экономико-математических моделей для задач линейного программирования;

• решение транспортных задач.

Методические указания содержат теоретические сведения, необходимые для выполнения заданий, примеры решения подобных задач, а также варианты заданий по рассмотренным темам. Работа оформляется в соответствии с ГОСТ 2.105-95 и требованиями, принятыми в учреждениях высшего образования РФ.

Тема: Создание экономико-математических моделей для задач линейного программирования

1. Цель работы

1.1 Построение плана задачи линейного программирования, ее целевой функции и условия-ограничений

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

2. Теоретические сведения

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

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

Найти max F(x₁,x_2,…x_n) =max(c₁x₁ + c₂x₂ +…c_nx_n)(1)

при условии, что точка, определяемая вектором Х=(x₁,x_2,…x_n), принадлежит некоторому допустимому множествуD, которое определяется системой неравенств:

a₁₁x₁ + a₁₂x₂ +…+ a_1nx_n ≤ b₁;

a₂₁x₁ + a₂₂x₂ +…+ a_2nx_n ≤ b₂;

…………………………. (2)

a_m1x₁ + a_m2x₂ +…+ a_mnx_n ≤ b_m;

где х₁ ≥ 0, х₂ ≥ 0,…, х_n ≥ 0

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

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

Пример.

Кондитерская фабрика производит несколько сортов конфет. Назовем их условно "A", "B" и "C". Известно, что реализация десяти килограмм конфет "А" дает прибыль 90 рублей, "В" - 100 рублей и "С" - 160 рублей. Конфеты можно производить в любых количествах (сбыт обеспечен), но запасы сырья ограничены. Необходимо определить, каких конфет и сколько десятков килограмм необходимо произвести, чтобы общая прибыль от реализации была максимальной. Нормы расхода сырья на производство 10 кг конфет каждого вида приведены в таблице 1.

Таблица 1 – Нормы расходов сырья на производство

Сырье	Нормы расхода сырья			Запас сырья
	А	В	С
Какао	18	15	12	360
Сахар	6	4	8	192
Наполнитель	5	3	3	180
Прибыль	90	100	160	максимум
Объем выпуска	Х1	Х2	Х3

Экономико-математическая формулировка задачи имеет вид

Найти такие значения переменных Х=(х1, х2, х3), чтобы

целевая функция F(x_1,x_2,x₃)= 90*x₁+100*x₂ +160*x₃→max

при условиях-ограничениях:

18•x₁+15•x₂ + 12•x₃≤ 360

6• x₁+4•x₂ + 8•x₃≤ 192

5• x₁+3•x₂ + 3•x₃≤ 180

x₁ ≥ 0,x₂ ≥ 0,x₃≥ 0

3. Задание

Для каждой задачи записать план, целевую функцию и условия-ограничения, т.е. записать экономико-математическую модель для задач линейного программирования.

Задача 1.

Предприниматель арендовал технологическую линию де­ревообрабатывающих станков для изготовления обрезной доски. Магазин «Стройматериалы» заказал комплекты из трех элементов: две обрезные доски длиной 2 м и одной обрезной доски длиной 1,25 м. Поставщик за­возит на грузовом автомобиле доски толщиной 20 мм, шириной 100 мм и длиной по 6,5 м — 200 штук и длиной по 4 м — 50 штук.

Рассчитайте, как распилить доски, чтобы продать максималь­ное количество комплектов?

Задача 2.

Составьте дешевый вариант 1 т кормовой смеси в соответ­ствии с требованиями, представленными в таблице2.

Содержание питательных веществ в кормовой смеси. Таблица 2

Питательные вещества	Требования % от веса	Содержание питательных веществ в кормах, %
		Люцерновая мука	Сухая барда	Рыбная мука	Соевый шрот
Белок	Не менее 35	17	25	60	45
Жиры	Не менее 1,5	2	5	7	0,5
Клетчатка	Не более 8	25	3	1	6,5
Вес	1 т	1	1	1	1
Стоимость руб. за 1 т	?	70	90	150	100

Задача 3

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

Содержание питательных веществ в 1 кг фруктов. Таблица 3

Вещества	Содержание питательных веществ в 1 кг фруктов			Нормы потребления, г
	клубника	яблоки	смородина
Р1	3	2	1	30
Р2	1	3	4	70
Р3	0	0	5	40
Р4	1	0	1	50
Цена, руб. за 1 кг	1,0	0,5	0,8

Задача 4.

Сформируйте вариант образования бензина АИ-80 и АИ-95, который обеспечивает максимальный доход от продажи, если имеется 5 т смеси 1-го сорта и 30 т смеси 2-го сорта. На изго­товление бензина АИ-80 идет 60% смеси 1-го сорта и 40% смеси 2-го сорта, на изготовление бензина АИ-95 идет 80% смеси 1-го сор­та и 20% смеси 2-го сорта. Реализуется 1 т бензина АИ-80 за 5000 рублей, а 1 т АИ-95 - за 6000 рублей.

Задача 5.

Фирма производит два безалкогольных широко популяр­ных напитка «Колокольчик» и «Буратино». Для производства 1 л «Ко­локольчика» требуется 0,02 ч работы оборудования, а для «Бурати­но» - 0,04 ч, а расход специального ингредиента на них составляет 0,01 кг и 0,04 кг на 1 л соответственно. Ежедневно в распоряжении фирмы 16 кг специального ингредиента и 24 ч работы оборудования. Доход от продажи 1 л «Колокольчика» составляет 0,25 руб., а «Бура­тино» - 0,35 руб.

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

Задача 6.

Фирма производит для автомобилей запасные части типа А и В. Фонд рабочего времени составляет 5000 чел.-ч в неделю. Для производства одной детали типа А требуется 1 чел.-ч, а для произ­водства одной детали типа В — 2 чел.-ч. Производственная мощ­ность позволяет выпускать максимум 2500 деталей типа А и 2000 деталей типа В в неделю. Для производства детали типа А уходит 2 кг полимерного материала и 5 кг листового материала, а для про­изводства одной детали типа В — 4 кг полимерного материала и 3 кг листового металла. Еженедельные запасы каждого вида материала на предприятии составляют 10 000 кг. Общее число производимых деталей в течение одной недели должно составлять не менее 1500 штук.

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

Задача 7.

Брокеру биржи клиент поручил разместить 100 000 долларов США на фондовом рынке, сформировать портфель с ценными бумагами, чтобы получить максимальные годовые проценты с вло­женного капитала. Выбор ограничен четырьмя возможными объ­ектами инвестиций - акций А, В, С, Д, которые позволяют получить доход в размерах соответственно 6%, 8%, 10% и 9% годовых от вло­женной суммы. При этом клиент поручил не менее половины ин­вестиций вложить в акции А и В. С целью обеспечения ликвидно­сти не менее 25% общей суммы капитала нужно поместить в акции Д. Учитывая прогноз на изменение ситуации в будущем, в акции С можно вложить не более 20% капитала. Специфика налогообложе­ния указывает на необходимость вложения в акции А не менее 30% капитала.

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

Задача 8.

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

Характеристики судов. Таблица 4

	Судно
	1	2
Пассажировместимость, чел.	2000	1000
Горючее, т	12000	7000
Экипаж, чел.	250	100

В месяц выделяется 60 000 т горючего. Потребность в рабочей силе не превышает 700 человек.

Определите количество судов I и II типа, чтобы обеспечить максимальный доход, который составляет от эксплуатации судов I типа 20 млн. рублей, а II типа - 10 млн. рублей в месяц.

Задача 9.

Фирма производит и продает столы и шкафы из древеси­ны хвойных и лиственных пород. Расход каждого вида в кубомет­рах на каждое изделие задан в таблице 5.

Расход древесины. Таблица 5

	Расход древесины, м^3		Цена изделия, тыс. руб.
	Хвойные	Лиственные
Стол	0,15	0,2	0,8
Шкаф	0,3	0,1	1,5
Запасы древесины	80	40

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