ТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ В УПРАВЛЕНИИ Методические указания для самостоятельной работы с
Работа добавлена на сайт samzan.net:
Министерство образования Российской Федерации
Ивановский государственный энергетический университет
Кафедра менеджмента и маркетинга
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ
В УПРАВЛЕНИИ
Методические указания для самостоятельной работы
студентов заочной формы обучения
Иваново 2003
Составитель И.Г. ШЕЛЕПИНА
Редактор Ю.Ф. БИТЕРЯКОВ
Методические указания предназначены для студентов факультета экономики и управления заочной формы обучения и бакалавриата, изучающих курсы «Математические методы и модели в управлении» и «Математические методы и модели в экономике».
В методических указаниях представлено содержание курса, список рекомендуемой литературы, задания для контрольной работы и краткие указания по ее выполнению.
Утверждены цикловой методической комиссией ФЭУ.
Рецензент
Кафедра экономики и организации предприятия Ивановского
государственного энергетического университета
СОДЕРЖАНИЕ КУРСА
ТЕМА 1. Основные вопросы применения математических методов в экономике и управлении.
Основные понятия и этапы экономико-математического моделирования. Классификация экономико-математических методов и моделей.
ТЕМА 2. Оптимизационные методы и модели в управлении экономическими системами.
2.1. Линейное программирование.
Принцип оптимальности в планировании и управлении, общая задача оптимального программирования. Формы записи задачи линейного программирования и ее экономическая интерпретация. Геометрическая интерпретация задачи (геометрический метод решения задачи). Симплексный метод решения задач линейного программирования (с естественным и искусственным базисом). Теория двойственности в анализе оптимальных решений экономических задач.
2.2. Транспортная задача линейного программирования (закрытая). Метод потенциалов.
ТЕМА 3. Вероятностно-статистичесике методы моделирования экономических систем.
Теория массового обслуживания. Классификация систем массового обслуживания. Количественные характеристики. Показатели эффективности систем массового обслуживания.
ТЕМА 3. Балансовый метод.
Экономико-математическая модель межотраслевого баланса. Коэффициенты прямых и полных материальных затрат.
Далее в данных методических указаниях представлены варианты контрольной работы и краткие указания по ее выполнению.
Контрольная работа выполняется студентами индивидуально на основе лекционного материала. Номер варианта контрольной работы - это последняя цифра номера зачетной книжки (цифре 0 соответствует 10 вариант).
ЗАДАНИЯ ДЛЯ КОНТРОЛЬНОЙ РАБОТЫ
ВАРИАНТ №1
Задача 1.
Решить графическим методом следующую задачу линейного программирования: ,
, ,
, .
Задача 2.
Предприятие располагает 3-мя видами сырья и может выпускать одну и ту же продукцию двумя способами. При этом за 1 час работы первым способом выпускается 20 единиц продукции, а вторым способом - 30 единиц продукции. Количество сырья (кг) того или иного вида, расходуемого за 1 час при различных способах производства, и запасы сырья (кг) приведены в таблице.
|
Тип сырья |
Способ производства |
Запас сырья, кг. |
|
|
1сп. |
2сп. |
||
С1 |
10 |
20 |
100 |
С2 |
20 |
10 |
100 |
С3 |
15 |
15 |
90 |
Сформулировать экономико-математическую модель задачи и, используя симплексный метод решения задач линейного программирования, найти такое время (час) использования первого и второго способов производства, при котором будет выпущено наибольшее количество продукции.
Задача 3.
Решить следующую транспортную задачу:
А=(100; 150; 50), В=(75;80;60;85), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.
Задача 4.
На АЗС имеются 2 колонки для заправки автомоби лей. Автомобили подъезжают на АЗС в соответствии с пуассоновским распределением со средней частотой 2 авто мобиля за 5 мин. Заправка автомобиля в среднем длится 3 мин, и продолжительность заправки распределена по экс поненциальному закону. Требуется определить:
а) вероятность того, что у АЗС не окажется ни одного ав томобиля;
б) вероятность того, что обе колонки будут заняты;
в) среднюю длину очереди в ожидании заправки;
г) среднее время ожидания автомобиля в очереди.
Задача 5.
На основании данных, приведенных в таблице, рассчитать коэффициенты прямых и полных материальных затрат.
Отрасль |
Прямые межотраслевые потоки |
Конечная продукция |
|
|
1 |
2 |
||
|
1 |
50 |
80 |
70 |
|
2 |
25 |
50 |
50 |
ВАРИАНТ №2
Задача 1.
Решить графическим методом следующую задачу линейного программирования: ,
, ,
, .
Задача 2.
Фирма "Nokia" заключила контракт с администрацией города на прокладку новых телефонных линий двух видов: кабельных (x1;[км]) и оптоволоконных (x2;[км]). По условиям контракта фирме будут предоставлены льготы, если она выполнит условия контракта и охватит при этом своей сетью как можно большее пространство города (x1+x2). Необходимо определить в какой пропорции строить эти два вида линий связи.
|
Вид телефонной линии |
Условия контракта |
||
|
кабельная |
оптоволоконная |
||
Трудовые ресурсы (чел./км) |
1 |
2 |
4 |
Кол-во единиц техники (ед./км) |
4 |
3 |
8 |
Денежные затраты ($/км) |
1 |
2 |
5 |
Сформулировать экономико-математическую модель задачи и решить ее, используя симплексный метод решения задач линейного программирования.
Задача 3.
Решить следующую транспортную задачу:
А=(300; 350;150; 200), В=(400;400;200), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.
Задача 4.
В парикмахерской работают 3 мастера. Посетители приходят в парикмахерскую в соответствии с пуассоновским распределением со средней частотой 4 человека в час. Стрижка в среднем длится 0,5 часа, и продолжительность стрижки распределена по экс поненциальному закону. Требуется определить:
а) вероятность того, что в парикмахерской не окажется ни одного посетителя;
б) вероятность того, что все мастера будут заняты;
в) среднюю длину очереди в ожидании стрижки;
г) среднее время ожидания посетителя в очереди.
Задача 5.
На основании данных, приведенных в таблице, рассчитать коэффициенты прямых и полных материальных затрат.
Отрасль |
Прямые межотраслевые потоки |
Конечная продукция |
|
|
1 |
2 |
||
|
1 |
40 |
18 |
22 |
|
2 |
16 |
9 |
25 |
ВАРИАНТ №3
Задача 1.
Решить графическим методом следующую задачу линейного программирования: ,
, ,
, .
Задача 2.
При проектировании энергосистемы требуется решить, какой мощности строить гидро- и тепловые станции (x1 и x2), обеспечивающие общую (x1 + x2) максимальную установленную мощность, при условии, что известен удельный расход имеющихся ресурсов на 1МВт установленной мощности и предел по каждому ресурсу.
|
Ресурсы |
Расход ресурсов на 1МВт мощности |
Ограничения по ресурсам |
|
|
ГЭС |
ТЭС |
||
Водные ресурсы, км3 |
10 |
1 |
145 |
Топливо, тыс.т |
5 |
7 |
105 |
Кап. вложения, млн.руб. |
5 |
1 |
200 |
Сформулировать экономико-математическую модель задачи и решить ее, используя симплексный метод решения задач линейного программирования.
Задача 3.
Решить следующую транспортную задачу:
А=(20; 30;40; 10), В=(40;40;20), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.
Задача 4.
В мастерской по ремонту телевизоров работают 4 опытных мастера. В среднем в течение рабочего дня (8 часов) в соответствии с пуассоновским распределением в ремонт поступает 9 телевизоров. Каждый мастер успевает отремонтировать 3 телевизора в день, и продолжительность ремонта распределена по экс поненциальному закону. Требуется определить:
а) вероятность того, что все мастера свободны от ремонта телевизоров;
б) вероятность того, что все мастера будут заняты;
в) среднюю длину очереди в ожидании ремонта;
г) среднее время ожидания каждым неисправным телевизором начала ремонта.
Задача 5.
На основании данных, приведенных в таблице, рассчитать коэффициенты прямых и полных материальных затрат.
Отрасль |
Прямые межотраслевые потоки |
Конечная продукция |
|
|
1 |
2 |
||
|
1 |
18 |
39 |
3 |
|
2 |
45 |
90 |
65 |
ВАРИАНТ №4
Задача 1.
Решить графическим методом следующую задачу линейного программирования: ,
, ,
, .
Задача 2.
Для производства трех видов продукции требуются два вида сырья. Количество сырья ограничено. Исходные данные приведены в таблице:
|
Тип сырья |
Расход сырья на единицу продукции, кг/ед. |
Количество сырья, кг. |
||
|
П1 |
П2 |
П3 |
||
С1 |
3 |
2 |
7 |
15 |
|
С2 |
4 |
1 |
2 |
10 |
|
Прибыль, руб./ед.прод. |
4 |
2 |
5 |
Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный объем производства продукции П1, П2 и П3, используя симплексный метод решения задач линейного программирования.
Задача 3.
Решить следующую транспортную задачу:
А=(25; 25; 40), В=(15;15;30;30), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.
Задача 4.
В магазине имеются 2 продавца. Покупатели приходят в магазин в соответствии с пуассоновским распределением со средней частотой 3 человека за 5 мин. Обслуживание одного покупателя в среднем длится 3 мин, и продолжительность обслуживания распределена по экс поненциальному закону. Требуется определить:
а) вероятность того, что в магазине не окажется ни одного покупателя;
б) вероятность того, что оба продавца будут заняты;
в) среднюю длину очереди в ожидании обслуживания;
г) среднее время ожидания покупателя в очереди.
Задача 5.
На основании данных, приведенных в таблице, рассчитать коэффициенты прямых и полных материальных затрат.
Отрасль |
Прямые межотраслевые потоки |
Конечная продукция |
|
|
1 |
2 |
||
|
1 |
80 |
25 |
20 |
|
2 |
36 |
45 |
39 |
ВАРИАНТ №5
Задача 1.
Решить графическим методом следующую задачу линейного программирования: ,
, ,
.
Задача 2.
Изготавливается смесь, в которой, кроме прочего, содержание вещества В1 должно быть не более 0,1 %, вещества В2 не более 16 %. Оба вещества содержаться в трех компонентах К1, К2 и К3. Компоненты добавляются к смеси в любых пропорциях и влияют на ее качество. Содержание веществ В1 и В2 в каждом компоненте, а также показатель качества смеси на 1 г каждого компонента приведены в таблице.
Характеристики |
Вид компонента |
||
|
К1 |
К2 |
К3 |
|
|
Содержание В1 в 1грамме компонента, % |
0,03 |
0,01 |
0,01 |
|
Содержание В2 в 1грамме компонента, % |
2 |
3 |
1 |
|
Показатель качества смеси, усл.ед./г. |
3 |
2 |
1 |
Необходимо определить оптимальное количество компонентов, чтобы показатель качества смеси был максимален. Сформулировать экономико-математическую модель задачи и решить ее, используя симплексный метод решения задач линейного программирования.
Задача 3.
Решить следующую транспортную задачу:
А=(40; 50;30; 70), В=(40;70;80),
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.
Задача 4.
В обувной мастерской работают 3 мастера. В среднем в течение рабочего дня (8 часов) в соответствии с пуассоновским распределением в ремонт поступает 10 пар обуви. Каждый мастер успевает отремонтировать 5 пар обуви в день, и продолжительность ремонта распределена по экс поненциальному закону. Требуется определить:
а) вероятность того, что все мастера свободны от ремонта обуви;
б) вероятность того, что все мастера будут заняты;
в) среднюю длину очереди в ожидании ремонта;
г) среднее время ожидания каждой парой обуви начала ремонта.
Задача 5.
На основании данных, приведенных в таблице, рассчитать коэффициенты прямых и полных материальных затрат.
Отрасль |
Прямые межотраслевые потоки |
Конечная продукция |
|
|
1 |
2 |
||
|
1 |
24 |
6 |
20 |
|
2 |
35 |
35 |
0 |
ВАРИАНТ №6
Задача 1.
Решить графическим методом следующую задачу линейного программирования: ,
, ,
.
Задача 2.
Для выпуска двух видов продукции требуются за траты сырья, рабочего времени и оборудования. Количество ресурсов ограничено. Исходные данные приведены в таблице:
|
Тип ресурса |
Hормы затрат ресурсов на единицу продукции |
Наличие ресурсов, т |
|
|
П1 |
П2 |
||
Сырье, т. |
3 |
5 |
60 |
|
Рабочее время, час. |
22 |
14 |
400 |
|
Оборудование, ед. |
10 |
14 |
128 |
|
Прибыль на единицу продукции, руб. |
30 |
25 |
Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный план выпуска продукции, используя симплексный метод решения задач линейного программирования.
Задача 3.
Решить следующую транспортную задачу:
А=(30; 50; 50), В=(20;35;20;55), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.
Задача 4.
У службы доставки продуктов на дом имеется 2 автомобиля. Заказы на обслуживание поступают в соответствии с пуассоновским распределением со средней частотой 2 заказа в час. Обслуживание каждого заказа в среднем длится 45 мин, и продолжительность обслуживания распределена по экс поненциальному закону. Требуется определить:
а) вероятность того, что все автомобили свободны от работы;
б) вероятность того, что оба автомобиля будут заняты;
в) среднюю длину очереди в ожидании обслуживания;
г) среднее время ожидания каждым заказом начала обслуживания.
Задача 5.
На основании данных, приведенных в таблице, рассчитать коэффициенты полных материальных затрат и объемы валовой продукции отраслей.
Отрасль |
Коэффициенты прямых затрат |
Конечная продукция |
|
|
1 |
2 |
||
|
1 |
0,3 |
0,4 |
40 |
|
2 |
0,5 |
0,1 |
10 |
ВАРИАНТ №7
Задача 1.
Решить графическим методом следующую задачу линейного программирования: ,
, ,
,.
Задача 2.
Для производства двух видов продукции требуются три вида сырья. Количество сырья ограничено. Исходные данные приведены в таблице:
|
Тип сырья |
Расход сырья на единицу продукции, кг/ед.прод. |
Количество сырья, кг. |
|
|
П1 |
П2 |
||
С1 |
1 |
4 |
15 |
|
С2 |
2 |
3 |
25 |
|
С3 |
1 |
1 |
20 |
|
Прибыль, руб./ед.прод. |
1 |
2 |
Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный объем производства продукции П1, П2, используя симплексный метод решения задач линейного программирования.
Задача 3.
Решить следующую транспортную задачу:
А=(50; 35; 45), В=(30;65;25;10), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.
Задача 4.
В часовой мастерской работают 3 мастера. В среднем в течение рабочего дня (8 часов) в соответствии с пуассоновским распределением в ремонт поступает 3 часов. Каждый мастер успевает отремонтировать 2 часов в день, и продолжительность ремонта распределена по экс поненциальному закону. Требуется определить:
а) вероятность того, что все мастера свободны от ремонта;
б) вероятность того, что все мастера будут заняты;
в) среднюю длину очереди в ожидании ремонта;
г) среднее время ожидания каждыми неисправными часами начала ремонта.
Задача 5.
На основании данных, приведенных в таблице, рассчитать коэффициенты полных материальных затрат и объемы валовой продукции отраслей.
Отрасль |
Коэффициенты прямых затрат |
Конечная продукция |
|
|
1 |
2 |
||
|
1 |
0,6 |
0,2 |
20 |
|
2 |
0,4 |
0,3 |
45 |
ВАРИАНТ №8
Задача 1.
Решить графическим методом следующую задачу линейного программирования: ,
, ,
, .
Задача 2.
Для производства двух видов продукции требуются три вида сырья. Количество сырья ограничено. Исходные данные приведены в таблице:
Тип сырья |
Расход сырья на единицу продукции, кг/ед.прод. |
Количество сырья, кг. |
|
|
П1 |
П2 |
||
С1 |
1 |
3 |
12 |
|
С2 |
4 |
1 |
15 |
|
С3 |
1 |
1 |
10 |
|
Прибыль, руб./ед.прод. |
4 |
2 |
Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный объем производства продукции П1, П2, используя симплексный метод решения задач линейного программирования.
Задача 3.
Решить следующую транспортную задачу:
А=(45; 50; 40), В=(65;35;25;10), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.
Задача 4.
В швейном ателье работают 3 закройщика. В среднем в течение рабочего дня (8 часов) в соответствии с пуассоновским распределением поступает 5 заказов. Каждый мастер успевает выполнить 2 заказа в течение дня, и продолжительность выполнения заказа распределена по экс поненциальному закону. Требуется определить:
а) вероятность того, что все закройщики свободны от работы;
б) вероятность того, что все закройщики будут заняты;
в) среднюю длину очереди в ожидании выполнения заказа;
г) среднее время ожидания каждого заказа в очереди.
Задача 5.
На основании данных, приведенных в таблице, рассчитать коэффициенты полных материальных затрат и объемы валовой продукции отраслей.
Отрасль |
Коэффициенты прямых затрат |
Конечная продукция |
|
|
1 |
2 |
||
|
1 |
0,1 |
0,7 |
70 |
|
2 |
0,2 |
0,3 |
50 |
ВАРИАНТ №9
Задача 1.
Решить графическим методом следующую задачу линейного программирования: ,
, ,
, .
Задача 2.
Для производства двух видов продукции требуются два вида сырья. Количество сырья ограничено. Исходные данные приведены в таблице:
|
Тип сырья |
Расход сырья на единицу продукции, кг/ед.прод. |
Количество сырья, кг. |
|
|
П1 |
П2 |
||
С1 |
6 |
2 |
18 |
С2 |
1 |
6 |
20 |
С3 |
1 |
1 |
5 |
|
Прибыль, руб./ед.прод. |
3 |
6 |
Сформулировать экономико-математическую модель задачи на максимум прибыли и найти оптимальный объем производства продукции П1, П2, используя симплексный метод решения задач линейного программирования.
Задача 3.
Решить следующую транспортную задачу:
А=(10; 85; 40), В=(70;35;10;20), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.
Задача 4.
В супермаркете имеются 4 кассы. Покупатели подходят к кассам в соответствии с пуассоновским распределением со средней частотой 2 человека за 5 мин. Обслуживание одного покупателя в среднем длится 5 мин, и продолжительность обслуживания распределена по экс поненциальному закону. Требуется определить:
а) вероятность того, что у касс не окажется ни одного покупателя;
б) вероятность того, что все кассы будут заняты;
в) среднюю длину очереди в ожидании обслуживания;
г) среднее время ожидания покупателя в очереди.
Задача 5.
На основании данных, приведенных в таблице, рассчитать объемы конечной продукции каждой отрасли и коэффициенты полных материальных затрат.
Отрасль |
Коэффициенты прямых затрат |
Совокупная продукция |
|
|
1 |
2 |
||
|
1 |
0,5 |
0,2 |
120 |
|
2 |
0,3 |
0,6 |
170 |
ВАРИАНТ №10
Задача 1.
Решить графическим методом следующую задачу линейного программирования: ,
, ,
, .
Задача 2.
Сформулировать экономико-математическую модель задачи, двойственную к исходной. Решить двойственную задачу, используя симплексный метод решения задач линейного программирования.
Исходная задача. Для производства двух видов продукции требуются два вида сырья. Количество сырья ограничено. Необходимо найти оптимальный объем производства продукции П1, П2, чтобы прибыль была максимальной. Исходные данные приведены в таблице:
|
Тип сырья |
Расход сырья на единицу продукции, кг/ед.прод. |
Количество сырья, кг. |
|
|
П1 |
П2 |
||
С1 |
1 |
2 |
4 |
С2 |
3 |
1 |
6 |
|
Прибыль, руб./ед.прод. |
1 |
2 |
Задача 3.
Решить следующую транспортную задачу:
А=(20; 40; 70), В=(30;60;15;25), ,
где А - вектор мощностей поставщиков, В – вектор мощностей потребителей, С – матрица транспортных издержек на единицу груза.
Задача 4.
На ж/д вокзале имеются 4 кассы для продажи билетов. Пассажиры подходят к кассам в соответствии с пуассоновским распределением со средней частотой 3 человека за 5 мин. Продажа билетов одному пассажиру в среднем длится 5 мин, и продолжительность ее распределена по экс поненциальному закону. Требуется определить:
а) вероятность того, что у касс не окажется ни одного пассажира;
б) вероятность того, что все кассы будут заняты;
в) среднюю длину очереди в ожидании обслуживания;
г) среднее время ожидания пассажира в очереди.
Задача 5.
На основании данных, приведенных в таблице, рассчитать объемы конечной продукции отраслей и коэффициенты полных материальных затрат.
Отрасль |
Коэффициенты прямых затрат |
Совокупная продукция |
|
|
1 |
2 |
||
|
1 |
0,2 |
0,3 |
90 |
|
2 |
0,1 |
0,6 |
100 |
КРАТКИЕ МЕТОДИЧЕСКИЕ УКАЗАНИЯ
для выполнения контрольной работы
ЗАДАЧА 1. В задаче линейного программирования (ЗЛП) требуется найти экстремум (максимум или минимум) линейной целе вой функции f(). Общая задача линейного программиро вания выглядит следующим образом: найти
|
max(min) f()=c1x1+c2x2+…+ cnxn, |
(1) |
при ограничениях (условиях):
|
a11x1+a12x2+…+ a1nxn {}b1, |
|
|
a21x1+a22x2+…+ a2nxn {}b2, |
(2) |
|
……… |
|
|
am1x1+am2x2+…+ amnxn {}bm, |
|
|
xj0, j = |
(3) |
где aij, bi, cj (i=, j =)— заданные постоянные величины.
Вектор = (х1, х2, ..., xп), удовлетворяющий системе ог раничений (2), (3), называется допустимым решением, или планом ЗЛП. План (допустимое решение), который доставляет максимум или минимум целевой функции (1), называется опти мальным планом (решением) ЗЛП.
Геометрический (графический) метод решения задачи.
Если в ЗЛП ограничения заданы в виде неравенств с дву мя переменными, она может быть решена графически. Задача ЛП в стандартной форме записи при п=2 выглядит следующим образом:
|
max(min) f()=c1x1+c2x2, |
(4) |
при ограничениях (условиях):
|
a11x1+a12x2b1, |
|
|
a21x1+a22x2b2, |
|
|
……… |
|
|
am1x1+am2x2bm, |
|
|
x10, x20. |
Каждое неравенство этой системы геометрически опреде ляет полуплоскость с граничной прямой ai1x1+ai2x2=bi,, i=. Условия неотрицательности определяют полуплос кости соответственно с граничными прямыми х1= 0, х2= 0. Полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая представляет собой многоугольник решений (сово купность точек, координаты каждой из которых составляют решение данной системы).
Гра фический метод решения ЗЛП состоит из следующих этапов.
Этап 1. Сначала на координатной плоскости x1 0 x2 стро ится допустимая многоугольная область, соответствующая огра ничениям, которая является пересечением множества полуплоскостей. Далее строится вектор-градиент линейной (целевой) функ ции f() в какой-нибудь точке , принадлежащей допус тимой области:
Этап 2. Строится прямая c1x1+c2x2=f() (линия уровня: целевая функция во всех точках этой прямой равна f()), перпендикулярная век тору-градиенту. Затем прямая передвигается в направлении вектора-градиента в случае максимизации f() до тех пор, пока не покинет пределов многоугольной области. Предельная точка области при этом движении и является точкой мак симума f(). В случае минимизации f() прямую c1x1+c2x2=f() надо двигать в направлении, противоположном вектору-гра диенту.
Этап 3. Для нахождения координат точки максимума (минимума) достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума (минимума). Значение f(), найденное в получаемой точке, является максимальным (минимальным).
ЗАДАЧА 2. В данной задаче необходимо найти решение с помощью симплексного метода. Симплексный метод - это универсальный метод решения ЗЛП. Суть его заключается в следующем.
Этап 1. Вначале исходная ЗЛП записывается в канонической форме.
Канонической формой записи задачи линейного програм мирования (КЗЛП) называют задачу вида:
|
max f()= |
(5) |
при ограничениях
|
(6) |
|
|
, j =. |
(7) |
Или в матричном виде: max f()=CX при условиях AX = B, X0.
Здесь С = (c1, c2,…, cn,) — вектор-строка; А=(аij) — матри ца размерности т x п, X и B - вектор-столбцы.
Расширенная матрица этой системы будет иметь вид:
=
Приведение ЗЛП к каноническому виду осуществляется введением в левую часть соответствующего ограничения вида (2) k-ой дополнительной переменной xn+k 0 со знаком “-“ в случае ограничения типа и знаком “+” в случае ограниче ния типа .
Дальнейшее решение ведется в в симплекс-таблицах.
|
№ табл. |
Базис |
Сб |
План В |
с1 |
с2 |
… |
сj |
… |
сn |
Q |
|
A1 |
A2 |
… |
Aj |
… |
An |
|||||
|
0 |
A1 |
с1 |
b1 |
a11 |
a12 |
… |
a1j |
… |
a1n |
|
|
A2 |
с2 |
b2 |
a21 |
a22 |
… |
a2j |
… |
a2n |
||
|
… |
… |
… |
… |
… |
… |
… |
… |
… |
||
|
Ai |
сi |
bi |
ai1 |
ai2 |
… |
aij |
… |
ain |
||
|
… |
… |
… |
… |
… |
… |
… |
… |
… |
||
|
Am |
сm |
bm |
am1 |
am2 |
… |
amj |
… |
amn |
||
|
L |
… |
Δj |
… |
Рис.1. Симплексная таблица
Этап 2. Предварительно получают допустимый вариант, удовлетво ряющий всем ограничениям, но необязательно оптимальный (т.н. начальное опорное решение).
Для этого матрица системы уравнений должна содержать единичную подматрицу раз мерностью т х т. Предположим, что после выполнения этапа 1 первые т век торов матрицы системы составляют единичную матрицу. Тогда очевиден первоначальный опорный план: (b1, b2, ..., bm,0, ...,0). Т.е. основные переменные являются свободными и равными нулю, а дополнительные переменные являются базисными и равны правым частям СЛУ.
Этап 3. Полученный вариант проверяется на оптимальность с помощью критерия оптимальности. Признак оптимальности заключается в следующих двух теоремах.
Теорема 1. Если для некоторого вектора, не входящего в базис, выполняется условие
, где , j =, (т.е. - скалярное произведение векторов столбцов Сб и Aj ), то можно получить новый опорный план, для которого зна чение целевой функции будет больше исходного.
называют оценкой столбца j.
Теорема 2. Если для всех векторов выполняется условие , то полученный план является оптимальным.
Этап 3. Если решение не оптимальное, переходят к следующему опорному решению (плану) на основе применения метода Жордана-Гаусса для системы линейных уравнений; на правление перехода от одного опорного решения к другому выбирается на основе критерия оптимальности исходной задачи.
На основании признака оптимальности в базис вводится вектор Ak, давший минимальную отрицательную величину симплекс-разности:
= zk - ck = min(zj - cj), j =, (т.е. имеющий минимальную отрицательную оценку)
Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор Аr, который дает минимальное положительное отношение
Q = , aik>0, i= .
Строка Ar называется направляющей, столбец Аk и эле мент ark — направляющими (или ведущими).
Элементы вводимой строки, соответствующей направ ляющей строке, в новой симплекс-таблице вычисляются по методу Жордана-Гаусса.
Число L в симплексной таблице – это текущее значение целевой функции: , т.е. скалярное произведение векторов столбцов Сб и В.
Этап 4. Полученный опорный план снова проверяется на опти мальность и т.д. Оптимальность достигается последовательным улучшением исходного варианта за определенное число этапов (итераций), причем на последнем шаге либо выявляется нераз решимость задачи (конечного оптимума нет), либо получа ются оптимальный опорный план и соответствующее ему оптимальное значение целевой функции.
Для использования приведенной выше процедуры сим плекс-метода к минимизации линейной формы f() следует искать максимум функции f1() = - f(), затем получен ный максимум взять с противоположным знаком. Это и бу дет искомый минимум исходной ЗЛП.
С каждой ЗЛП тесно связана другая линейная задача, называемая двойственной, первоначальная задача называется исходной или прямой.
Модель двойственной задачи имеет вид:
|
g()=min , |
(8) |
|
, |
(9) |
|
, i =. |
(10) |
Двойственная задача по отношению к исходной состав ляется согласно следующим правилам:
1) целевая функция исходной задачи (5)-(7) формули руется на максимум, а целевая функция двойственной задачи (8)-(10 ) - на минимум, при этом в задаче на максимум все неравенства в функциональных ограниче ниях имеют вид , а в задаче на минимум – вид ;
2) матрица А, составленная из коэффициентов при неизвестных в сис теме ограничений (6) исходной задачи, и аналогич ная матрица
=
в двойственной задаче получаются друг из друга транс понированием;
3) число переменных в двойственной задаче равно числу функциональных ограничений (6) исходной задачи, а число ограничений в системе (9) двойственной задачи - числу переменных в исходной задаче;
4) коэффициентами при неизвестных в целевой функции (8) двойственной задачи являются свободные члены в системе (6) ограничений исходной задачи, а правыми частями в ограничениях (9) двойственной задачи - коэффициенты при неизвестных в целевой функции (5) исходной задачи;
5) каждому ограничению одной задачи соответствует пере менная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записан ному в виде неравенства , соответствует переменная, связанная условием неотрицательности.
ЗАДАЧА 3.
Транспортная задача по критерию стоимости в общем виде формули руется следующим образом. В т пунктах отправления А1, А2, …,, Аm , которые в даль нейшем будем называть поставщиками, сосредоточено опре деленное количество единиц некоторого однородного про дукта, которое обозначим ai ( i = 1, 2, ..., т). Данный про дукт потребляется в п пунктах B1, B2, …,, Bn, которые будем называть потребителями; объем потребления обозначим bj
(j = 1, 2, ..., n). Известны расходы на перевозку единицы продукта из пункта Ai в пункт Bj, которые равны cij и при ведены в матрице транспортных расходов С = (cij).
Требуется составить такой план прикрепления потреби телей к поставщикам, т.е. план перевозок, при котором весь продукт вывозится из пунктов Аi, в пункты Bj в соответ ствии с потребностью и общая величина транспортных из держек будет минимальной.
Обозначим количество продукта, перевозимого из пункта Aj в пункт Bj, через хij. Совокупность всех переменных хij для краткости обозначим .
Наиболее применяемым ме тодом решения данной задачи является метод потенциалов, при котором каждой i-й строке (i-му поставщику) устанавливается потенциал ui, который можно интерпретировать как цену продукта в пункте поставщика, а каждому столбцу j (j-му потребителю) устанавливается потенциал vj, который можно принять ус ловно за цену продукта в пункте потребителя. В простей шем случае цена продукта в пункте потребителя равна его цене в пункте поставщика плюс транспортные расходы на его доставку, т.е.
|
vj=ui+cij. |
(11) |
Следует отметить, что ранг сис темы линейных уравнений равен т + п - 1; таким образом из общего числа тп неизвестных базисных неизвестных будет т + п - 1. Вследствие этого при любом допустимом базисном распределении в матрице перевозок (таблице поставок), представленной в общем виде на рис. 2, будет занято ровно т + п - 1 клеток, которые будем назы вать базисными в отличие от остальных свободных клеток; занятые клетки будем отмечать диагональной чертой.
Рис.2. Таблица поставок
Алгоритм метода потенциалов для закрытой транспортной задачи таков.
Первым этапом является состав ление начального распределения (начального плана перевозок); для реализации этого начального этапа имеется в свою очередь ряд методов: северо-западного угла, наименьших стоимостей и др.
При каждом из этих методов при заполнении некоторой клетки, кроме последней, вычеркивается или только строка матрицы перевозок, или только столбец; лишь при заполнении последней клетки вычеркиваются и строка, и столбец.
В методе северо-западного угла всегда в первую очередь за полняется клетка (из числа невычеркнутых), стоящая в верхнем левом (северо-западном) углу матрицы перевозок. В различных модификациях метода наименьших стоимо стей заполнение клеток матрицы перевозок проводится с учетом значений величин cij. Так, в модификации «двойно го предпочтения» отмечают клетки с наименьшими стоимо стями перевозок сначала по каждой строке, а затем по каж дому столбцу. Клетки, имеющие две отметки, заполняют в первую очередь, затем заполняют клетки с одной отметкой, а данные о нераспределенном грузе записывают в неотме ченные клетки с наименьшими стоимостями.
Вторым этапом служат построение системы потенциалов на основе равенства (11) и проверка начального плана на оптимальность; в случае его неоптимальности переходят к третьему этапу.
Введем специальные показатели ui для каждой строки матрицы перевозок (каждого поставщика), где , и показатели vj для каждого столбца (каждого по требителя), где . Эти показатели называются потен циалами поставщиков и потребителей, их удобно интерпре тировать как цены продукта в соответствующих пунктах по ставщиков и потребителей. Потенциалы подбираются таким образом, чтобы для заполненной клетки (i;j) выполнялось равенство (11).
Совокупность уравнений вида (11), со ставленных для всех заполненных клеток (всех базисных неизвестных), образует систему т + п - 1 линейных урав нений с т+п неизвестными ui и vj. Эта система всегда со вместна, причем значение одного из неизвестных можно задавать произвольно (например, и1= 0), тогда значения остальных неизвестных находятся из системы однозначно.
Чтобы оценить оптимальность распределения, для всех клеток (i;j) матрицы перевозок определяются их оценки, ко торые обозначим через dij, по формуле:
|
dij=(ui+cij)- vj. |
(12) |
Используя ранее принятую интерпретацию, выражение (ui+cij) можно трактовать как сумму цены продукта у по ставщика и стоимости перевозки; эта сумма путем вычита ния сравнивается с ценой продукта у соответствующего потребителя vj. Очевидно, оценки заполненных клеток рав ны нулю. Таким образом, условием оптималь ности распределения служит условие неотрицательности оценок свободных клеток матрицы перевозок. Оценки клеток по формуле (12) удобно представить в виде матрицы оценок.
Третий этап заключается в реализации так называемых циклов перераспределения (корректировка плана прикреп ления потребителей к поставщикам), после чего переходят опять ко второму этапу. Совокупность процедур третьего и второго этапов образует одну итерацию; эти итерации повторяются, пока план перевозок не окажется оптимальным.
Чтобы улучшить неоптимальный план перевозок, выбирается клетка матрицы перевозок с от рицательной оценкой; если таких клеток несколько, то обычно выбирается клетка с наибольшей по абсо лютной величине отрицательной оценкой. Для выбранной клетки строится замкнутая линия (контур), начальная вершина которой лежит в выбранной клетке, а все остальные вершины находятся в занятых клетках; при этом направления отдельных отрезков контура могут быть толь ко горизонтальными и вертикальными. Вершиной контура, кроме первой, является занятая клетка, где отрезки контура образуют один прямой угол. Очевидно, число отрезков контура, как и его вершин, будет четным. В вершинах контура рас ставляются поочередно знаки «+» и «-», начиная со знака «+» в выбранной свободной клетке.
Величина перераспределяемой поставки определяется как наименьшая из величин поставок в вершинах контура со зна ком «-», и на эту величину увеличиваются поставки в верши нах со знаком «+» и уменьшаются поставки в вершинах со зна ком «-». Это правило гарантирует, что в вершинах контура не появится отрицательных поставок, начальная выбранная клетка окажется занятой, в то время как одна из занятых клеток при этом обязательно освободится.
Пример простого контура показан пунктиром на рис. 3.
Рис. 3. Пример таблицы поставок
ЗАДАЧА 4.
Данная задача отражает процесс моделирования систем массового обслуживания (СМО). СМО - это такие системы, в кото рых, с одной стороны, возникают массовые запросы (требо вания) на выполнение каких-либо услуг, с другой - проис ходит удовлетворение этих запросов. СМО включает в себя следующие элементы: источник требований, входящий поток требований, очередь, обслуживающие устройства (каналы об служивания), выходящий поток требований. Исследованием таких систем занимается теория массового обслуживания.
В данной задаче рассматривается модель СМО с ожиданием, в которой требо вания, поступившие в момент, когда все обслуживающие ка налы заняты, ставятся в очередь и обслуживаются по мере освобождения каналов.
Общая постановка задачи состоит в следующем. Система имеет п обслуживающих каналов, каждый из которых может одновременно обслуживать только одно требование. В систему поступает простейший (пуассоновский) поток требований с параметром . Если в момент поступления оче редного требования в системе на обслуживании уже находится не меньше п требований (т.е. все каналы заняты), то это требование становится в очередь и ждет начала обслуживания. Время обслуживания каждого требования tоб — случай ная величина, которая подчиняется экспоненциальному за кону распределения с параметром . Система является разомкнутой, т.е. поступающий поток требо ваний можно считать неограниченным.
Алгоритм расчета показателей качества функ ционирования разомкнутой системы массового обслуживания с ожиданием.
Вводится параметр . Если , то очередь не может расти безгранично. Это условие имеет следующий смысл: — среднее число требо ваний, поступающих за единицу времени, — среднее время обслуживания одним каналом одного требования, то гда — среднее число каналов, которое необходимо иметь, чтобы обслуживать в единицу времени все поступаю щие требования. Поэтому условие означает, что чис ло обслуживающих каналов должно быть больше среднего числа каналов, необходимых для того, чтобы за единицу времени обслужить все поступившие требования.
Важней шие характеристики работы СМО:
1. Вероятность того, что все обслуживающие каналы сво бодны
|
. |
(13) |
2. Вероятность того, что все обслуживающие каналы заняты:
|
; (). |
(14) |
3. Среднее время ожидания требованием начала обслу живания в системе:
|
; (). |
(15) |
4. Средняя длина очереди:
|
; (). |
(16) |
5. Среднее число свободных от обслуживания каналов:
|
. |
(17) |
ЗАДАЧА 5.
В осно ве создания балансовых моделей лежит балансовый метод, т.е. ме тод взаимного сопоставления имеющихся материальных, трудовых и финансовых ресурсов и потребностей в них. Под балансовой моделью следует понимать систему уравнений, которые удовлетворяют требованиям соответствия наличия ресурса и его использо вания. Балансовый метод и создаваемые на его основе балансо вые модели служат основным инструментом поддержания пропорций в народном хозяйстве.
Матрица А - матрица коэффициентов материальных прямых затрат. В общем случае, когда имеется п отраслей производства, она имеет вид:
=.
Элементы матрицы аij называются коэффициентами прямых материальных затрат. Каждый элемент аij показывает, какое количество продукции i-й отрасли необходимо, если учитывать только прямые затраты, для производства единицы продукции j-й отрасли.
Коэффициенты аij рассчитываются следующим образом:
|
, |
(18) |
где Xj – валовая продукция j-й отрасли.
Если определить векторы-столбцы совокупной (валовой) продукции Х и конечной продукции Y таким образом:
, ,
где xi и уi - соответственно валовая и конечная продукция отрасли i, то система уравнений в матричной форме примет вид
|
, |
(19) |
Эта система уравнений называется экономико-математической моделью межотрас левого баланса (моделью Леонтьева, моделью «затраты— выпуск»). С помощью этой модели можно выполнить следующие варианты расчетов:
1. Задав в модели величины валовой продукции каждой отрасли (Xi), можно определить объемы конечной про дукции каждой отрасли (Yi):
|
, |
(20) |
2. Задав величины конечной продукции всех отраслей (Yi), можно определить величины валовой продукции каждой отрасли (Xi):
|
, |
(21) |
В формулах (3) и (4) Е обозначает единичную матрицу n-го порядка, а (Е - А)-1 обозначает матрицу, обратную к матрице (Е - А). Формула для вычисления обратной матрицы раз мера 2х2 имеет вид:
Обозначая обратную матрицу через В=(Е - А)-1, систему уравнений в матричной форме (21) можно записать в виде
|
, |
(22) |
Элементы матрицы В будем обозначать через bij, тогда из матричного уравнения (22) для любой i-й отрасли можно получить следующее соотношение:
|
, |
(23) |
Коэффициенты bij называются коэффици ентами полных материальных затрат и включают в себя как прямые, так и косвенные затраты всех порядков. Коэффициент полных материальных за трат bij показывает, какое количество продукции i-й отрасли нужно произвести, чтобы с учетом прямых и косвенных затрат этой продукции получить единицу конечной продукции j-й отрасли.
ЛИТЕРАТУРА
Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / В.В. Федосеев, А.Н. Гармаш, Д.М. Дайитбегов и др.; Под ред. В.В. Федосеева. – М.: ЮНИТИ, 2000.
Исследование операций в экономике: Учеб. пособие для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. - М.:ЮНИТИ, 2002.
Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем: Учеб. пособие. - М.: Финансы и статистика, 2001.
Киселев В.Ю. Экономико-математические методы и модели: Учеб. пособие. – Иваново: ИГЭУ, 1998.
Колесников А.Н. Краткий курс математики для экономистов: Учеб. пособие. – М.: ИНФРА-М, 1998.
Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике: Учебник. 2-е изд. – М.: МГУ им. М.В. Ломоносова, «Дело и сервис», 1999.
МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ В УПРАВЛЕНИИ
Методические указания для самостоятельной работы
студентов заочной формы обучения
Составитель ШЕЛЕПИНА Ирина Геннадьевна
Редактор
Лицензия ЛР №020264 от 15.12.96 г.
Подписано в печать . . . Формат 60х84 1/16.
Печать плоская. Усл. печ. л. 1,39. Тираж 100 экз. Заказ
Ивановский государственный энергетический университет
Отпечатано в ОМТ МИБИФ
153003, Иваново, ул. Рабфаковская, 34
2. NOTE ~ so stnds before do - too stnds fter do nd there must be verb exception ldquo;me toordquo; NOTE lso tht the word so hs different menings in the bove exmples
3. Российский союз сельской молодежи Минсельхоз России 7 этаж большой конференцзал 28 ноября 2012 г
4. Задание 1 Задание 2 Задание 3 Задание 1 До введения в российский уголовный процесс единоличного поря
5. Контрольная работа- Проблемы теории государства и права
6. Введение13
7. все мы или почти все глубоко отмечены Достоевским
8. Реферат- Происхождение Солнечной системы и планеты Земля. Основные этапы геологической истории
9. Российский университет кооперации Факультет предпринимательства и таможенного дела Кафедра коммерц
10. Лабораторна робота 1- Створення експертної системи в MtLb
11. Пермский государственный национальный исследовательский университет Юридический факультет Кафед
12. тема собак Виктория Токарева Система собак Помнишь как мы встретились в первый раз В кафе
13. Ich hbe uch die usbildung gemcht und ein Pr Jhre in einem grossen Friseurslon gerbeitet
14. Курсовая работа- Основные правила подбора вин к блюдам
15. юриспруденция Гражданское процессуальное право 3 курс 4 года Дневное отделение ст
16. Для подготовки и проведения фестиваля формируется оргкомитет
17. Введение Одним из самых сложных периодов в онтогенезе человека является подростковый возраст
18. Комплексная информационная автоматизированная система Кафедра
19. Архипелага ГУЛАГ
20. Тема 6 Анализ деловых данных Оптимизация с помощью команды Подбор параметра Использование команд