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

Студентки гр.

Преподаватель

Тема работы: Применение методов линейного и динамического программирования для решения практических задач (по вариантам)

Исходные данные:

Задача 1

На первом складе (А1) содержится сталь двух марок: 2300 т марки «а» и 3000 т марки «б».

Сталь этих марок содержится также и на втором складе (А2) в следующих количествах: 2500 т марки «а» и 4400 т марки «б».

Сталь должна быть вывезена в два пункта потребления: в пункт В1 необходимо поставить 1100 т стали марки «а», 1600 т марки «б» и остальные 300 т стали любой марки.

Аналогично второй пункт потребления В2 должен получить 6900 т стали, из них 1400 т марки «а» и 4900 т марки «б».

Известно, что 1 т стали марки «а» может заменить 0.7 т стали марки «б» (то есть, вместо стали марки «б» можно использовать соответствующее количество стали марки «а», но не наоборот).

Стоимость перевозок в денежных единицах (ДЕ) за тонну составляют: из пункта А1 в пункты В1 и В2 3.6 ДЕ и 5.6 ДЕ, и из пункта А2 в В1 и В2, соответственно, 4.3 ДЕ и 5.6 ДЕ.

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

1. Провести параметрическое изменение правых частей:

• если в решении отсутствуют перевозки с заменой марок стали («а» на «б»), то провести постепенное изменение запасов на обоих складах (увеличение - для стали марки «а», и уменьшение для стали марки «б») до тех пор, пока по крайней мере 100 т стали марки «а» не будут направлены на замену стали марки «б»;

• если в решении присутствуют такие перевозки, то провести обратное постепенное изменение запасов, пока перевозки с заменой марок стали не исчезнут (рассмотреть вариант только с увеличением запасов стали марки «б» без изменения запасов стали марки «а» на обоих складах).

1. Провести параметрическое изменение целевой функции:

• предварительно существено увеличить запасы стали обеих марок (в правых частях), чтобы на предпочтительность перевозок стали той или иной марки не влияли ограничения по запасам; • убедиться в отсутствии замен (или в их наличии), для чего заново решить задачу; • затем провести постепенное изменение (увеличение или уменьшение - по смыслу) стоимости перевозок стали марки «б» (при прежней стоимости перевозок стали марки «а») до появления хотя бы 100 т замены (или до исчезновения замен).

Задача 2

В пункте В2 сталь поступает на условный производственный комплекс, состоящий из сталелитейного и станкостроительного заводов. Он функционирует в течение 5 лет.

Начальный запас стали составляет 3800 т (для решения; интервал для исследования — 1000–10000 т (*)).

Исходные производственные мощности заводов соответственно:

• по стали — 4100 т в год;
• по станкам — 1800 станков в год (для решения; интервал для исследования — 100–5000 станков). (**)

Сталь расходуется на производство станков (1.2 т на каждый) и собственно стали, а также на расширение производственных мощностей комплекса. При этом каждая тонна стали, направленная на ее производство, обеспечивает выпуск 2.5 т. Тонна стали, идущая на расширение производственной мощности сталелитейного завода, увеличивает последнюю на 0.3 т, а для увеличения производственных мощностей станкостроительного завода на один станок необходимо затратить 12 т стали.

Реализация решения о распределении стали на следующий год осуществляется в конце очередного года планируемого периода; станкостроительный завод не может получать более половины имеющегося запаса стали.

Требуется:

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

2. провести исследование (поочередно, по одному фактору) влияния начальных условий (*) и (**) на структуру и результат решения (т.е. на распределение стали и на объем выпуска станков).

Задача 3

Склад пункта реализации станков имеет вместимость 15 единиц. Пополнение склада возможно только первого числа каждого месяца. Станки привозят автотранспортом (1 рейс), причем стоимость рейса складывается из постоянных затрат 30 денежных единиц (ДЕ) и затрат на доставку каждого станка 10 ДЕ. За один рейс (и, следовательно, в месяц) может быть доставлено не более 7 станков.

Затраты на хранение станка в течение месяца составляют 8 ДЕ.

Ожидаемый спрос на станки приведен в табл. 1. Отсутствие требуемого количества станков на складе недопустимо.

В начальный момент на складе находится 1 станок.

1. определить план заказов, минимизирующий стоимость;

2. определить границы изменения стоимости хранения станка, в которых найденный план является оптимальным;

3. определить границы изменения постоянных затрат на совершение рейса, в которых найденный план является оптимальным;

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

Таблица 1: Ожидаемый спрос на станки по месяцам