Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







ЗАДАЧА ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ ИНВЕСТИЦИЙ ПО ПРОЕКТАМ





ЗАНЯТИЕ 3

ТРАНСПОРТНАЯ ЗАДАЧА

Словесная формулировка. Имеется поставщиков А 1, А 2, …, Аm некоторого однородного грузас запасами a 1, a 2,…, am соответственно. Имеется потребителей B 1, B 2,…, Bn этого груза c заявками b 1, b 2,…, bn. Заданы тарифы перевозок , означающие стоимости перевозки единицы груза от Ai к Bj; кроме того, заданы штрафные тарифы , означающие издержки, вызываемые каждой единицей невывезенного груза поставщиков , , а также штрафные тарифы , означающие издержки, вызываемые каждой единицей недопоставленного груза потребителям , . Требуется составить такой план перевозки грузов, при котором: 1) объемы вывозимых грузов не превышают запасы поставщиков; 2) объемы поставок не превышают заявки потребителей; 3) суммарные издержки всех перевозок минимальны.

Формальная постановка. Используя введенные обозначения, имеем:

(2.1)

(2.2)

 

Задача 2.1. Имеется пять поставщиков и пять потребителей некоторого груза. Стоимости перевозки единицы груза сij от i -го поставщика к j -му потребителю, данные о возможностях поставщиков и запросах потребителей, а также штрафы за недопоставку/невывоз каждой единицы груза, представлены в следующих таблицах:

 

  Потребитель 1 Потребитель 2 Потребитель 3 Потребитель 4 Потребитель 5 Штрафы за невывоз
Поставщик 1            
Поставщик 2            
Поставщик 3            
Поставщик 4            
Поставщик 5            

 

  Потребитель 1 Потребитель 2 Потребитель 3 Потребитель 4 Потребитель 5
Штрафы за недопоставку          

 

  Поставщик 1 Поставщик 2 Поставщик 3 Поставщик 4 Поставщик 5
Возможности поставщиков          

 

  Потребитель 1 Потребитель 2 Потребитель 3 Потребитель 4 Потребитель 5
Запросы потребителей          

 

Каждый поставщик заинтересован поставить весь имеющийся у него груз, каждый потребитель – максимально удовлетворить свои потребности. Составить оптимальный план перевозок с минимальной стоимостью.

Решение: 1) переписываем «возможности поставщиков» в столбец как «запасы»;

2) переписываем «запросы потребителей» как «потребности»

3) подсчитываем (в ячейках В9 и I2) суммарные запасы и суммарные потребности, определяя после этого тип задачи (закрытая, на избыток или на недостаток);

4) подсчитываем кол-во вывезенного (В18:В22), привезенного (D16:H16) груза, остатки у поставщиков (J18:J22) и недопоставки у потребителей (D24:H24);

5) подсчитываем издержки (B13; D13; F13; H13); 7) вызываем «Поиск решения» и решаем задачу:

 

 

Рис 2.1. Шаблон с решением задачи 2.1


Задачи для самостоятельного решения

Задача 2.2. Для строительства 4-х объектов используется кирпич, изготовляемый на трех заводах. Ежедневно на заводе1, заводе2 и заводе3 может изготовляться соответственно 100, 150 и 50 тыс. шт. кирпича. Ежедневные потребности в кирпиче на каждом из строящихся объектов равны 75, 80, 60 и 85 тыс. шт. Известны также тарифы перевозок 1 тыс. шт. кирпича с каждого завода к каждому из строящихся объектов:

 

Объект1 Объект2 Объект3 Объект4  
        Завод1
        Завод2
        Завод3

 

Составить такой план перевозок кирпича к строящимся объектам, при котором общая стоимость перевозок является минимальной. Чему она равна? Ответ: F min=665 при X *= .

Задача 2.3. В трех хранилищах горючего хранится 175, 125 и 140 тонн бензина. Этот бензин запрашивают четыре заправочные станции в количествах, равных соответственно 180, 110, 60 и 40 тонн. Тарифы перевозок 1 тонны бензина с хранилищ к заправочным станциям заданы в таблице

Хранилища Заправочные станции
I II III IV
А        
В        
С        

 

Составить такой план перевозки бензина, при котором общая стоимость перевозок является минимальной, а все заправочные станции получают столько, сколько запрашивают. Штрафы за недопоставку и за невывоз бензина равны нулю.

Ответ: F min=1675 при X *= .

Задача 2.4. На трех мелькомбинатах объединения «Мука» ежедневно производится 110, 190 и 90 тонн муки. Эта мука потребляется четырьмя хлебозаводами, ежедневные потребности которых равны соответственно 80, 60, 170 и 80 тонн. Тарифы перевозок 1 тонны муки с мелькомбинатов к каждому из хлебозаводов известны и задаются матрицей

Мелькомбинаты Хлебозаводы
  I II III IV
А        
В        
С        

 

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

Ответ: F min=1280 при X *= .

Задача 2.5. Заводы автомобильной фирмы MG расположены в Лос-Анджелесе, Детройте и Новом Орлеане. Основные центры распределения продукции сосредоточены в Денвере и Майами. Объемы производства указанных трех заводов равняются 1000, 1500 и 1200 автомобилей ежеквартально. Величины квартального спроса в центрах распределения составляют 2300 и 1400 автомобилей соответственно. Стоимость перевозки по железной дороге одного автомобиля на одну милю равняется 8 центам. Расстояние в милях между заводами и центрами распределения приведены в таблице:

 

Лос-Анджелес    
Детройт    
Новый Орлеан    
  Денвер Майами

 

Составить такой план перевозок автомобилей в центры распределения, при котором общая стоимость перевозок является минимальной. Чему она равна? Ответ: F min=31320000 при X *= .

Задача 2.6. Заводы фирмы расположены в городах Лидсе и Кардиффе; они доставляют товары на склады городов Манчестер, Бирмингем и Лондон. Расстояния (в милях) между этими городами приведены в таблице:

 

  Заводы Склады
Манчестер Бирмингем Лондон
Лидс      
Кардифф      

 

Завод в Лидсе выпускает в год 800 т. товаров, а в Кардиффе - 500 т. Манчестерский склад вмещает 400 т., Бирмингемский - 600 т., а Лондонский - 300 т. Стоимости перевозки единицы товара на единицу расстояния равны по любым направлениям. Как следует транспортировать товары для минимизации стоимости перевозок?

Ответ: F min=125000 при .


ДОМАШНЕЕ ЗАДАНИЕ

Часы суток

 

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

Решение. Обозначим: число автобусов, выходящих на линию в 0 часов; число автобусов, выходящих на линию в 4 часа; число автобусов, выходящих на линию в 8 часов; число автобусов, выходящих на линию в 12 часов; число автобусов, выходящих на линию в 16 часов; число автобусов, выходящих на линию в 20 часов. Тогда математическая формулировка задачи принимает вид задачи линейного программирования:

Ответ: fmin =26 при (4; 10; 0; 8; 4; 0).

 

 

ЗАНЯТИЕ 3

ЗАДАЧА ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ ИНВЕСТИЦИЙ ПО ПРОЕКТАМ

 

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

Формальная постановка. Пусть инвестиционный период разбит на m временных интервалов, следующих непосредственно один за другим; и – объем инвестиций в j -й проект и их предельное значение соответственно; коэффициент возврата этих инвестиций в начале i -го интервала. Пусть средства инвестора хранятся в банке с коэффициентом доходности ki за i -й интервал. Тогда остатки и на банковском счете инвестора в начале и конце i -го периода будут равны:

; ; , , (1.1)

где H – величина средств инвестора в начале инвестиционного периода.

Остатки на начало m -го интервала следует максимизировать:

. (1.2)

Соотношение (1.1) вместе с рекуррентными соотношениями (1.2), описывающими динамику изменения средств инвестора, условиями и , представляют формальную постановку задачи.

 

Задача 1.1. Компания, желая оптимальным образом использовать имеющиеся у нее денежные средства, разрабатывает оптимальный план инвестиций на ближайшие пять лет. На выбор у компании имеется пять инвестиционных проектов, параметры денежных потоков которых представлены в следующей таблице

 

Год Проект А Проект В Проект С Проект D Проект Е
  -1   -1 -1 -1
  0,7 -1 0,2 -1  
  0,1 0,1 0,6 0,5 0,1
  0,1 0,1 0,4 0,9 0,6
  1,6   1,6 2,5 1,6

 

Участие в инвестиционном проекте «С» обязательное и требует не менее 6,9 млрд. руб., а проект «В» не допускает инвестиций более 6,2 млрд. руб. Размер имеющихся у компании денежных средств на момент планирования инвестиций составляет 14 млрд. руб.

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

 

Решение. В соответствиис формализацией (1.1)-(1.2) остатки и на банковском счете инвестора в начале и конце i -го года будут равны:

; ; , ,

Остатки в конце периода следует максимизировать:

Добавляя условия , , , получаем и решаем задачу с помощью надстройки «Поиск решения» Excel:

1) отводим блок ячеек под искомые размеры инвестиций (ячейки B10:F10 на шаблоне, рис.1 ниже);

2) считаем обороты (G3:G7) и остатки денег (H3:H7) на р/с компании для каждого года;

3) ставим задачу в «Поиске решения» и решаем ее.

 

 

Рис 1. Шаблон с решением задачи 1.1

 


Задача 1.2. Представители пяти проектов конкурируют между собой за получение кредита. Графики потока платежей погашения кредитов представлены в таблице:

Год Проекты
A B C D E
  -1,0   -1,0 -1,0  
  +0,3 -1,0 +1,0    
  +1,0 +0,3     -1,0
    +1,0   +1,75 +1,4

Например, проект А стартует в начале первого года сразу после получения кредита; в начале второго года возвращает инвестору 0,3 от всей взятой суммы; в начале третьего года (момент окончания проекта) взятые деньги возвращаются с коэффициентом 1. Проект В аналогичен проекту А, но начинается на год позже. И так далее. Доходы, полученные от текущих проектов, можно направить в другие. Средства инвестора хранятся на банковском счете с доходностью 6% годовых. Максимальная сумма, требуемая для проекта А, равна 500 у.е. По другим проектам объем вложений не ограничен. В начальный момент у инвестора имеется 1000 у.е. Найти оптимальные объемы инвестиций в проекты, обеспечивающие максимальный доход инвестора к началу 4-го года периода.

Решение. В соответствиис формализацией (1.1)-(1.2) остатки и на банковском счете инвестора в начале и конце i -го года будут равны:

; ; , ,

Остатки на начало 4-го года периода следует максимизировать:

Добавляя условия , ; получаем задачу и решаем ее с помощью надстройки «Поиск решения» Excel:

 

 

Рис. 1.2. Шаблон с решением задачи 1.2

 

Задачи для самостоятельного решения

Задача 1.3. Инвестор, располагающий суммой в 500 тыс. евро, желает максимизировать денежную наличность к концу шестимесячного периода. Характеристики возможных инвестиций даны в таблице.

Инвестиции Начало Длительность Процент дохода
А каждый месяц 1 месяц 1,5
В месяц 1, 3, 5 2 месяца 3,5
С месяц 1, 4 3 месяца  
D месяц 1 6 месяцев  

Доход по каждому виду инвестиций в конце срока с процентами, указанными в таблице. С начала 5-го месяца до начала 7-го инвестору необходимо иметь на руках не менее 300 тыс. евро. Каков максимальный доход к концу шестимесячного периода?

Ответ: 48499,5 евро.

Задача 1.4. Инвестор, располагающий суммой в 500 тыс. евро, желает максимизировать денежную наличность к началу 4-го года периода. Имеется таблица с коэффициентами возврата по каждому из пяти возможных вариантов инвестиций:

  Годы Возможные инвестиции
A B C D E
  -1,0 -0,5 -1,0 -0,5  
  +0,3 -0,5 +1,0 -0,25 -0,5
  +1,0 +0,3 +0,1 -0,25 -0,5
    +1,0   +1,75 +1,4

Определить оптимальный план инвестиций. Чему будет при этом равен инвестиционный доход D?

Ответ: .

D = 459039,5 евро.

 

Задача 1.5. Инвестор, располагающий суммой в 500 тыс. евро, желает максимизировать денежную наличность к началу 4-го года периода. Имеется таблица с коэффициентами возврата по каждому из пяти возможных вариантов инвестиций:

  Годы Возможные инвестиции
A B C D E
  -1,0 -0,5 -1,0 -0,5  
  +0,3 -0,5 +1,0 -0,25 -0,5
  +1,0 +0,3 +0,1 -0,25 -0,5
  +0,2 +1,0 +0,3 +1,75 +1,4

С учетом рисков на каждый из вариантов решено направить не менее 100 тыс.евро. Чему будет при этом равен инвестиционный доход при оптимальном инвестировании?

Ответ: D = 465666,7 евро.

 


ТРАНСПОРТНАЯ ЗАДАЧА

Словесная формулировка. Имеется поставщиков А 1, А 2, …, Аm некоторого однородного грузас запасами a 1, a 2,…, am соответственно. Имеется потребителей B 1, B 2,…, Bn этого груза c заявками b 1, b 2,…, bn. Заданы тарифы перевозок , означающие стоимости перевозки единицы груза от Ai к Bj; кроме того, заданы штрафные тарифы , означающие издержки, вызываемые каждой единицей невывезенного груза поставщиков , , а также штрафные тарифы , означающие издержки, вызываемые каждой единицей недопоставленного груза потребителям , . Требуется составить такой план перевозки грузов, при котором: 1) объемы вывозимых грузов не превышают запасы поставщиков; 2) объемы поставок не превышают заявки потребителей; 3) суммарные издержки всех перевозок минимальны.

Формальная постановка. Используя введенные обозначения, имеем:

(2.1)

(2.2)

 

Задача 2.1. Имеется пять поставщиков и пять потребителей некоторого груза. Стоимости перевозки единицы груза сij от i -го поставщика к j -му потребителю, данные о возможностях поставщиков и запросах потребителей, а также штрафы за недопоставку/невывоз каждой единицы груза, представлены в следующих таблицах:

 

  Потребитель 1 Потребитель 2 Потребитель 3 Потребитель 4 Потребитель 5 Штрафы за невывоз
Поставщик 1            
Поставщик 2            
Поставщик 3            
Поставщик 4            
Поставщик 5            

 

  Потребитель 1 Потребитель 2 Потребитель 3 Потребитель 4 Потребитель 5
Штрафы за недопоставку          

 

  Поставщик 1 Поставщик 2 Поставщик 3 Поставщик 4 Поставщик 5
Возможности поставщиков          

 

  Потребитель 1 Потребитель 2 Потребитель 3 Потребитель 4 Потребитель 5
Запросы потребителей          

 

Каждый поставщик заинтересован поставить весь имеющийся у него груз, каждый потребитель – максимально удовлетворить свои потребности. Составить оптимальный план перевозок с минимальной стоимостью.

Решение: 1) переписываем «возможности поставщиков» в столбец как «запасы»;

2) переписываем «запросы потребителей» как «потребности»

3) подсчитываем (в ячейках В9 и I2) суммарные запасы и суммарные потребности, определяя после этого тип задачи (закрытая, на избыток или на недостаток);

4) подсчитываем кол-во вывезенного (В18:В22), привезенного (D16:H16) груза, остатки у поставщиков (J18:J22) и недопоставки у потребителей (D24:H24);

5) подсчитываем издержки (B13; D13; F13; H13); 7) вызываем «Поиск решения» и решаем задачу:

 

 

Рис 2.1. Шаблон с решением задачи 2.1


Задачи для самостоятельного решения

Задача 2.2. Для строительства 4-х объектов используется кирпич, изготовляемый на трех заводах. Ежедневно на заводе1, заводе2 и заводе3 может изготовляться соответственно 100, 150 и 50 тыс. шт. кирпича. Ежедневные потребности в кирпиче на каждом из строящихся объектов равны 75, 80, 60 и 85 тыс. шт. Известны также тарифы перевозок 1 тыс. шт. кирпича с каждого завода к каждому из строящихся объектов:

 

Объект1 Объект2 Объект3 Объект4  
        Завод1
        Завод2
        Завод3

 

Составить такой план перевозок кирпича к строящимся объектам, при котором общая стоимость перевозок является минимальной. Чему она равна? Ответ: F min=665 при X *= .

Задача 2.3. В трех хранилищах горючего хранится 175, 125 и 140 тонн бензина. Этот бензин запрашивают четыре заправочные станции в количествах, равных соответственно 180, 110, 60 и 40 тонн. Тарифы перевозок 1 тонны бензина с хранилищ к заправочным станциям заданы в таблице

Хранилища Заправочные станции
I II III IV
А        
В        
С        

 

Составить такой план перевозки бензина, при котором общая стоимость перевозок является минимальной, а все заправочные станции получают столько, сколько запрашивают. Штрафы за недопоставку и за невывоз бензина равны нулю.

Ответ: F min=1675 при X *= .

Задача 2.4. На трех мелькомбинатах объединения «Мука» ежедневно производится 110, 190 и 90 тонн муки. Эта мука потребляется четырьмя хлебозаводами, ежедневные потребности которых равны соответственно 80, 60, 170 и 80 тонн. Тарифы перевозок 1 тонны муки с мелькомбинатов к каждому из хлебозаводов известны и задаются матрицей

Мелькомбинаты Хлебозаводы
  I II III IV
А        
В        
С        

 

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

Ответ: F min=1280 при X *= .

Задача 2.5. Заводы автомобильной фирмы MG расположены в Лос-Анджелесе, Детройте и Новом Орлеане. Основные центры распределения продукции сосредоточены в Денвере и Майами. Объемы производства указанных трех заводов равняются 1000, 1500 и 1200 автомобилей ежеквартально. Величины квартального спроса в центрах распределения составляют 2300 и 1400 автомобилей соответственно. Стоимость перевозки по железной дороге одного автомобиля на одну милю равняется 8 центам. Расстояние в милях между заводами и центрами распределения приведены в таблице:

 

Лос-Анджелес    
Детройт    
Новый Орлеан    
  Денвер Майами

 

Составить такой план перевозок автомобилей в центры распределения, при котором общая стоимость перевозок является минимальной. Чему она равна? Ответ: F min=31320000 при X *= .

Задача 2.6. Заводы фирмы расположены в городах Лидсе и Кардиффе; они доставляют товары на склады городов Манчестер, Бирмингем и Лондон. Расстояния (в милях) между этими городами приведены в таблице:

 

  Заводы Склады
Манчестер Бирмингем Лондон
Лидс      
Кардифф      

 

Завод в Лидсе выпускает в год 800 т. товаров, а в Кардиффе - 500 т. Манчестерский склад вмещает 400 т., Бирмингемский - 600 т., а Лондонский - 300 т. Стоимости перевозки единицы товара на единицу расстояния равны по любым направлениям. Как следует транспортировать товары для минимизации стоимости перевозок?

Ответ: F min=125000 при .


ДОМАШНЕЕ ЗАДАНИЕ







Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.