На практическое занятие № 3
ФАКУЛЬТЕТ ЭКОНОМИКИ И УПРАВЛЕНИЯ
КАФЕДРА ФИНАНСОВ
Учебно-методический комплекс дисциплины: ГСЭ.В.01 «Математические методы в экономике»
|
Заведующего кафедрой финансов
к.э.н., доцент Ю.Ю. ЛИТВИН
___.09.2008
ЗАДАНИЕ
на практическое занятие № 3
на тему «Решение экономических задач методом линейного программирования»
I.Учебная цель:Исследовать способы оптимизации экономической задачи методом линейного программирования.
Воспитательная цель: Сформировать у студентов системность знаний при количественном обосновании управленческих решений методом линейного программирования.
II.Перечень отрабатываемых вопросов:
1. Решение задачи линейного программирования графическим способом.
III.Рекомендации студентам по подготовке к лабораторной работе с указанием перечня руководств и пособий, подлежащих изучению перед занятием:
В период подготовки к лабораторной работе необходимо к каждой задаче разработать форму таблицы для внесения исходных данных и результатов расчета. Для выполнения лабораторной работы необходимо изучить следующую литературу по данной теме:
Основная литература:
1. КРЕМЕР Н.Ш, ПУТКО Б.А., ФРИДМАН М.Н., Исследование операций в экономике: учебное пособие. – Москва: ЮНИТИ, 2006.
2. ХЭМДИ А. ТАХА, Введение в исследование операций. - Москва: ВИЛЬЯМС, 2001г.
3. ФОМИН Г.П., Математические методы и модели в коммерческой деятельности: учебное пособие. - Москва: Финансы и статистика, 2001.
4. БЕРЕЖНАЯ Е.В, БЕРЕЖНОЙ В.И., Математические методы моделирования экономических систем: учебное пособие. - Москва: Финансы и кредит, 2001.
Дополнительная литература:
5. САЛМАНОВ О.Н., Математическая экономика с применением MathCAD и Microsoft Excel: руководство. - Санкт-Петербург: БХВ-Петербург, 2003.
6. Эффективная работа с Microsoft Excel: руководство. - Санкт-Петербург: ПИТЕР, 2000.
7. MathCAD 6.0 PLUS (Финансовые, инженерные и научные расчеты в среде Windows): руководство. - Москва: ФИЛИНЪ, 1996.
IV.Краткое содержание лабораторной работы:
Исследование способов решения задачи линейного программирования осуществляется применением графического метода с последующей проверкой результатов решения с использованием прикладной математической программы «MathCAD»:
Задача № 1
Лакокрасочный цех судостроительного завода производит краску для внутренних и наружных работ из сырья двух типов А и В, которая поступает как на покраску судов, так и в оптовую продажу. Нормативный расход сырья для производства краски и получаемый доход от ее продажи представлены в таблице №1.
Из-за отсутствия надлежащего спроса отдел маркетинга ограничил ежедневное производство краски для внутренних работ до 2 т. и поставил условие, чтобы ежедневное производство краски для наружных работ не превышало более чем на тонну аналогичный показатель краски для внутренних работ. Максимально-возможный ежедневный расход сырья определяется его возрастающим спросом и возможностями складского хранения.
Определите, с учетом максимизации дохода какое количество каждого вида краски необходимо произвести с учетом заданных условий?
Задача № 2
Для доставки горюче-смазочных материалов в порт нефтеперерабатывающий завод располагает тремя типами транспортных средств. Количество транспортных средств различных типов и их производительность по числу заправок, перевозимых в единицу времени, отражены в исходных данных.
Найти план использования транспортных средств, обеспечивающий доставку максимального количества горюче-смазочных материалов по числу заправок с учетом комплектности их доставки в течение суток?
Задача № 3
Фирма «ПОЛЮСТРОВО» производит два безалкогольных широко популярных напитка «Колокольчик» и «Буратино». Для производства одного литра «Колокольчика» требуется времени работы оборудования t1, а для «Буратино» - t2. Расход специальных ингредиентов для производства напитков составляет a1 и a2 на один литр соответственно с учетом ежедневного расхода ингредиента b при d сменной работы оборудования. Доход от продажи одного литра напитка составляет d1 и d2 соответственно.
Определите ежедневный план производства напитков каждого вида, обеспечивающий максимальный доход от их продажи?
Задача № 4
Для связи с судами, находящимися в трех районах зоны ответственности диспетчером порта могут быть использованы два радио центра. На каждом из радиоцентров может быть открыто не более a приемных радиовахт. Все радиовахты несутся на различных частотах, при этом для судов одного района могут быть использованным не более b частот. Вероятности приема донесений на всех частотах от судов одного и того же района одинаковы для данного радиоцентра.
Составить эффективный план использования приемных радиовахт радиоцентров для обеспечения связи с судами в различных районах с учетом их независимой работы?
Задача № 5
Некая транспортная компания, располагая флотилией из двух типов пассажирских судов, в летний сезон обслуживает в среднем h туристов. В месяц выделяется j т. топлива. Потребность в рабочей силе не превышает k человек.
Определить эффективное количество судов первого и второго типа для обеспечения максимального дохода, который составляет от эксплуатации судов первого типа a1 млн. руб., а судов второго типа – a2 млн. руб.?
Задача № 6
С Московского вокзала Санкт-Петербурга ежедневно на Москву отправляются скорые и пассажирские поезда. Количество различных типов вагонов железнодорожного депо станции отправления и их пассажировместимость указаны в таблице № 6.
Определить количество пассажирских и скорых поездов, обеспечивающих перевозку максимального количества пассажиров.
Задача № 7
Предприятие производит 2 вида продукции X и Y. Один килограмм продукции Х, приносящий прибыль в 5 рублей, требует на его производство два килограмма ресурса А и три килограмма ресурса В. Один килограмм продукции Y, приносящий прибыль в 10 рублей, требует на его производство семь килограммов ресурса А и девять килограммов ресурса В. Суммарный запас ресурсов составляет 70 кг. ресурса А и 50 кг. Ресурса В. При каком объеме производства прибыль будет максимальной?
V.Краткие теоретические или справочно-информационные материалы:
Общая задача линейного программирования записывается в стандартной или канонической форме, предполагая выполнение следующих требований:
- все линейные ограничения преобразуются с неотрицательной правой частью;
- все переменные неотрицательны;
- целевую функцию следует минимизировать или максимизировать.
Выполняя эти требования, задача линейного программирования ставиться следующим образом - стандартная форма записи:
Найти неотрицательные значения неизвестных переменных х1, х2, х3, … , хn обращающих линейную форму ЦФ в максимум
, при 
(8.1.1)
удовлетворяющих системе линейных ограничений:
неравенств, задающих условия решения задачи
(8.1.2)
и ограничений на переменные
(8.1.3)
где аij – заданные постоянные величины;
bi – численные значения ограничений;
cj – условная стоимость;
; 
- индексы.
Задача линейного программирования в канонической форме ставиться следующим образом:
Найти неотрицательные значения неизвестных переменных х1, х2, х3, … , хn обращающих линейную форму ЦФ в минимум
, при (8.1.4)
удовлетворяющих системе линейных ограничений:
уравнений, задающих условия решения задачи
(8.1.5)
и ограничений на переменные
(8.1.6)
Преобразование задачи максимизации в задачу минимизации. Если в ЗЛП требуется найти не минимум, а максимум ЦФ, то сведение ЗЛП к каноническому виду состоит в замене ЦФ величиной с обратным знаком:
(8.1.7)
В этом случае 
, т.е. задача максимизации функции у эквивалентна задачи минимизации функции у*, поскольку при решении обеих задач предоставляется один и тот же набор значений переменных.
Преобразование неравенств в равенства. Если по условиям задачи линейные ограничения выражаются в виде неравенств (³,£), то сведение ЗЛП к каноническому виду заключается во введении дополнительных неизвестных. В первом случае они вычитаются из первой части неравенства, а во втором случае прибавляются. Добавляемая переменная называется остаточной переменной, а вычитаемая переменная – избыточной. Так, например, неравенства типа
(8.1.8)
(8.1.9)
заменяются соответственно на уравнения
(8.1.10)
(8.1.11)
где 
Правую часть неравенства всегда можно сделать неотрицательной путем умножения всего неравенства на (-1).
Преобразование равенств в неравенства осуществляется с помощью одного дополнительного ограничения. Система линейных уравнений-ограничений
(8.1.12)
в этом случае записывается в виде системы неравенств-ограничений:
(8.1.13)
Графический метод – характеризуется тем, что позволяет наглядно показать основные свойства решений задач ЛП и применяется в простейшем случае и когда число неизвестных превосходит число ограничений на две единицы ( 
). Графический метод решения ЗЛП состоит из трех этапов:
1. Первый этап - построение области допустимых решений.
2. Второй этап - нахождение оптимального решения среди всех точек области допустимых решений.
3. Третий этап - анализ модели на чувствительность.
Для построения области допустимых решений необходимо:
• Привести ОЗЛП к стандартной форме одним из описанных способов.
• Произвести выбор координатных переменных: определяются две неизвестные переменные, которые были бы линейно-независимые ( 
. Неизвестные переменные считаются линейно-независимыми, когда определители, составленные из коэффициентов при них отличны от нуля.
• Построение многогранника решений: строятся прямые, соответствующие линейным ограничениям, предварительно выраженные через координатные переменные. Далее находят полуплоскость, удовлетворяемую данному ограничению. Штриховкой показывают ту полуплоскость, где условия не удовлетворяются. Так как система линейных ограничений совместна, то прямые, соответствующие ограничениям, пересекаясь, образуют замкнутую область (выпуклый многогранник), который является областью допустимых решений.
Для нахождения оптимального решения необходимо построение начальной прямой. Для построения начальной прямой, соответствующей целевой функции, предварительно ее преобразовывают через координатные переменные и приравнивают к некоторому значению z (обычно z = 0).
(8.1.14)
Далее вычисляют координаты двух точек удовлетворяющие данному уравнению. И через эти две точки проводят НП пунктирной линией.
Для определения направления возрастания (убывания) целевой функции строят вектор-градиент Ñ, координаты которого являются частными производными преобразованной целевой функции:
(8.1.15)
 |
Чтобы построить этот вектор нужно соединить точку (c1, c2) с началом координат. При максимизации ЦФ необходимо двигаться в направлении вектора-градиента, а при минимизации – в противоположном направлении. Осуществляя параллельный сдвиг начальной прямой, перпендикулярной вектору-градиенту в направлении данного вектора до крайней угловой точки многогранника решений до тех пор, пока НП не покинет пределов многоугольной области, в результате находят точку (см. рис. 8.1.1), в которой ЦФ принимает максимальное значение. Осуществляя параллельный сдвиг начальной прямой в противоположном направлении вектора-градиента до крайней угловой точки многоугольника решений, в результате находят точку, в которой ЦФ принимает минимальное значение. Определив координаты данной точки (по условию задачи) вычисляют значение ЦФ.
Рисунок 8.1.1 – Графический метод решения ЗЛП
VI.Порядок проведения лабораторной работы:
Лабораторная работа проводиться последовательным решением задач с выдачей каждому студенту индивидуального варианта задания.
Лабораторная работа выполняется в соответствии с методическими указаниями (см. раздел 1, п. 1.2) с окончательным ее оформлением в часы самостоятельной работы.
VII.Исходные данные для лабораторной работы:
Таблица № 1 – Исходные данные к задаче № 1.
| Вариант | Расход сырья на тонну краски, т | Максимально возможный ежедневный расход сырья, т | |||
| для наружных работ | для внутренних работ | ||||
| Сырье | А | ||||
| В | |||||
| Оптовые цены, ед. продукции за тонну (в $ 1000) | |||||
| Сырье | А | ||||
| В | |||||
| Оптовые цены, ед. продукции за тонну (в $ 1000) | |||||
| Сырье | А | ||||
| В | |||||
| Оптовые цены, ед. продукции за тонну (в $ 1000) |
Таблица № 2 – Исходные данные к задаче № 2
| Вариант | Тип транспортных средств | Число транспортных средств | Производительность транспортных средств | |
| по топливу | по маслу | |||
Таблица № 3 – Исходные данные к задаче № 3
| Вариант | Время работы оборудования для производства одного литра напитка, ч | Расход специальных ингредиентов, кг | Ежедневный расход ингредиента b , кг | Ежедневное количество смен работы оборудования d, ед. | Доход от продажи одного литра напитка, руб. | |||
| t1 | t2 | a1 | a2 | d1 | d2 | |||
| 0.02 | 0.04 | 0.01 | 0.03 | |||||
| 0.01 | 0.04 | 0.02 | 0.05 | 2,5 | 3,5 | |||
| 0.01 | 0.03 | 0.02 | 0.05 |
Таблица № 4 – Исходные данные к задаче № 4
| Вариант | Вероятности приема донесений | Приемные радиовахты a | Частоты приемных радиовахт, используемые для одного района b | |||
| Радио центры | Районы | |||||
| 0.4 | 0.5 | 0.1 | ||||
| 0.3 | 0.4 | 0.3 | ||||
| 0.5 | 0.1 | 0.4 | ||||
| 0.4 | 0.3 | 0.3 |
Таблица № 5 – Исходные данные к задаче № 5
| Вариант | Показатели | Тип судна | |
| I | II | ||
| Пассажировместимость (чел) | 2 000 | 1 000 | |
| Горючее (т) | 12 000 | 7 000 | |
| Экипаж (чел) | |||
| Доход (млн. руб) | |||
| Количество обслуживаемых туристов за сезон h (чел) | 7 500 | ||
| Количество топлива выделяемого в месяц j (т) | 60 000 | ||
| Потребность в раб. силе k (чел) | |||
| Пассажировместимость (чел) | 2 500 | 1 500 | |
| Горючее (т) | 14 000 | 9 000 | |
| Экипаж (чел) | |||
| Доход (млн. руб) | |||
| Количество обслуживаемых туристов за сезон h (чел) | 8 500 | ||
| Количество топлива выделяемого в месяц j (т) | 80 000 | ||
| Потребность в раб. силе k (чел) |
| Пассажировместимость (чел) | 3 000 | 2 000 | |
| Горючее (т) | 15 000 | 10 000 | |
| Экипаж (чел) | |||
| Доход (млн. руб) | |||
| Количество обслуживаемых туристов за сезон h (чел) | 9 500 | ||
| Количество топлива выделяемого в месяц j (т) | 90 000 | ||
| Потребность в раб. силе k (чел) |
Таблица № 6 – Исходные данные к задаче № 6
| Вариант | Показатели | Тип вагона | Общий | Купейный | Мягкий |
| Количество вагонов в поезде | скорый | ||||
| пассажирский | |||||
| Пассажировместимость | |||||
| Парк вагонов в депо | |||||
| Количество вагонов в поезде | скорый | ||||
| пассажирский | |||||
| Пассажировместимость | |||||
| Парк вагонов в депо | |||||
| Количество вагонов в поезде | скорый | ||||
| пассажирский | |||||
| Пассажировместимость | |||||
| Парк вагонов в депо |
VIII.Порядок оформления отчета по лабораторной работе и его защита:
Отчет по лабораторной работе оформляется в соответствии с требованиями раздела 1, п. 1.3 в одном из текстовых редакторов.
Разработал доцент кафедры, к.в.н., доцент А.А. БУРЫКИН
__.09.08