Компьютерное проектирование (моделирование)

Контрольная работа. Задачи
1. Построение моделей одноиндексных задач линейного программирования.
2. Графический метод решения одноиндексных задач
и Т.Д. ...

Линейное программирование

Линейное программирование

рис.4). При этом общее потребление ингредиента А снизится, что приведет к его недефицитности [ресурс (1)], а дефицитным будет ресурс (2).РешениеОбозначим количество автомобилей, перевозимых из i-го завода в j-й пункт потребления через .Проверим равенство суммарного производства автомобилей и суммарного спроса откуда следует вывод – задача несбалансирована, поскольку спрос на автомобили меньше объема их производства. Для установления баланса введем дополнительный фиктивный центр с ежеквартальным спросом 400 шт. (). Фиктивные тарифы приравняем к нулю (т.к. перевозки в действительности производиться не будут).Согласно результатам проверки сбалансированности задачи в транспортной матрице должно быть три строки, соответствующих заводам и три столбца, соответствующих центрам распределения (см.табл.1). Тариф перевозки обычно вписывают в правом нижнем углу клетки матрицы для удобства дальнейшего нахождения опорных планов задачи.Таблица 1Транспортная матрица задачи №4.1DEФиктивныйпотребительОбъем произв., шт./кварталА1000802150B15001001080C1200102680Спрос, шт./квартал190014004003700Задание ЦФСуммарные затраты в рублях на ежеквартальную перевозку автомобилей определяются по формулеЗадание ограничений [шт./квартал]РешениеОбозначим количество автомобилей, перевозимых из i-го завода в j-й пункт потребления через .Проверим равенство суммарного производства автомобилей и суммарного спросаоткуда следует вывод – задача несбалансирована, поскольку спрос на автомобили превышает объем их производства. Для установления баланса введем дополнительный фиктивный город (завод) с ежеквартальным объемом производства 200 шт. (). Фиктивные тарифы приравняем к нулю (т.к. перевозки в действительности производиться не будут).Так как поставка с завода А в распределительный центр Е не планируется изначально, то введем запрещающий тарифВ нашем случае , то есть, например, возьмем Согласно результатам проверки сбалансированности задачи №4.2 в транспортной матрице должно быть четыре строки, соответствующих заводам и два столбца, соответствующих центрам распределения (табл.2). Тариф перевозки обычно вписывают в правом нижнем углу клетки матрицы для удобства дальнейшего нахождения опорных планов задачи.Таблица 2Транспортная матрица задачи №4.2DEОбъем произв., шт./кварталА1000801000B1300100108C120010268Фиктивный город(завод)20000Спрос, шт./квартал230014003700Задание ЦФСуммарные затраты в рублях на ежеквартальную перевозку автомобилей определяются по формуле, но при этом мы должны учесть штрафы, за недопоставку автомобилей в распределительные центры D и E Задание ограничений [шт./квартал]РешениеОбозначим количество продукции, перевозимых из i-го склада в j-й магазин через .Проверим равенство суммарных запасов на складах и суммарного спроса в магазинахоткуда следует вывод – задача несбалансирована, поскольку запасы на складах меньше спроса в магазинах. Для установления баланса введем дополнительный фиктивный склад с запасами 10 (480-470=10). А) Фиктивные тарифы приравняем к нулю Результаты нахождения опорного плана различными методами представлены в табл.1, 2 и 3.Метод северо-западного угла.Таблица 1Транспортная таблица с опорным планом северо-западного углаПунктыотправления, Пункты потребления, Запасы,ед. продукции120740812160/40/0410513098140/130/0927031006170/100/000010010/0Потребность,ед. продукции120/050/10/0200/70/0110/10/0480Опорный план , найденный методом северо-западного углаСоответствующая ЦФ (общие затраты на перевозку) 2). Методом минимального элементаТаблица 2Транспортная таблица с опорным планом минимального элементаПунктыотправления, Пункты потребления, Запасы,ед. продукции7816012160/0110459308140/30/09502403806170/120/80/010000010/0Потребность,ед. продукции120/110/050/0200/40/0110/30/0480Опорный план , найденный методом минимального элемента 3) Методом ФогеляТаблица 3Транспортная таблица с опорным планом ФогеляШтрафы строк,785011102160/50/0116--110430598140/30/011111920215036170/20/01111710000010/00----120/110/050/30/0200/150/0110/0480Штрафы столбцов,42123324332-536-53--Опорный план , найденный методом ФогеляБ) Фиктивные тарифы сделаем одинаковые по величине и превышающие максимальный размер из реальных тарифовВ нашем случае , то есть, например, возьмем Результаты нахождения опорного плана различными методами представлены в табл.4, 5 и 6.1). Метод северо-западного угла.Таблица 4Транспортная таблица с опорным планом северо-западного углаПунктыотправления, Пункты потребления, Запасы,ед. продукции120740812160/40/0410513098140/130/0927031006170/100/01001001001010010/0Потребность,ед. продукции120/050/10/0200/70/0110/10/0480Опорный план , найденный методом северо-западного углаСоответствующая ЦФ (общие затраты на перевозку)2). Методом минимального элементаТаблица 5Транспортная таблица с опорным планом минимального элементаПунктыотправления, Пункты потребления, Запасы,ед. продукции7816012160/0120459208140/20/09502403806170/120/80/01001001001010010/0Потребность,ед. продукции120/050/0200/40/0110/30/10/0480Опорный план , найденный методом минимального элемента3) Методом ФогеляТаблица 6Транспортная таблица с опорным планом ФогеляШтрафы строк,785011102160/50/016---120420598140/20/011111920215036170/20/01117-1001010010010010/000000120/050/30/0200/150/0110/0480Штрафы столбцов,3324332-536-53--9695--Опорный план , найденный методом ФогеляВыводы: 1. В методе северо-западного угла различий нет, так как не зависимо от того используются нулевые фиктивные тарифы или какие-то другие, мы заполняя двигаемся из левого верхнего угла в правый нижний угол. 2. Когда распределение производиться методом наименьшего элемента и методом Фогеля, то и опорные планы отличаются и значение целевой функции, так как когда у нас фиктивные тарифы равны нулю, то мы начинаем заполнять с этих клеток, а когда у нас фиктивные тарифы являются величинами больше всех остальных тарифов, то мы эти клетки заполняем в последнюю очередь.РешениеВ задаче 4.1 была получена транспортная матрица (таблица 1)Таблица 1Транспортная матрица задачи №4.1DEФиктивныйпотребительОбъем произв., шт./кварталА1000802150B15001001080C1200102680Спрос, шт./квартал190014004003700Результаты нахождения опорного плана различными методами представлены в табл.2, 3 и 4.Метод северо-западного угла.Таблица 2Транспортная таблица с опорным планом северо-западного углаDEФиктивныйпотребительОбъем произв., шт./кварталА10001000/0802150B9006001500/600/01001080C8004001200/400/0102680Спрос, шт./квартал1900/900/01400/800/0400/03700Опорный план , найденный методом северо-западного углаСоответствующая ЦФ (общие затраты на перевозку)2). Методом минимального элементаТаблица 3Транспортная таблица с опорным планом минимального элементаDEФиктивныйпотребительОбъем произв., шт./кварталА6004001000/600/0802150B13002001500/200/01001080C12001200/0102680Спрос, шт./квартал1900/1300/01400/200/0400/03700Опорный план , найденный методом минимального элемента3) Методом ФогеляТаблица 4Транспортная таблица с опорным планом ФогеляDEФиктивныйШтрафы строк,А10008021501000/080135-В90010020010840001500/1100/200/010088С10212006801200/06834341900/900/01400/200/0400/03700Штрафы столбцов,204002040-240-Опорный план , найденный методом ФогеляРешениеПусть переменные  – это время, в течение которого i-й станок будет выпускать j-ю ткань. Исходные данные представлены в таблице 1Таблица 1Распределительная матрица задачи №6.1ПроизводительПродукцияФондвремени, чВ1В2В3А11 (, руб./т)(, т/ч) 65244360А2612242890А3372924148146А42953361296Объем выпуска, т705632162976ЦФ имеет смысл себестоимости выпуска запланированного количества ткани всех видовОграничения имеют видПреобразуем РЗ в ТЗ, т.е. представим исходную задачу в виде, когда ткани производит только один станок – базовый и все параметры задачи согласуем с его характеристиками. В качестве базового можно выбирать любой из станков. Мы выберем станок с максимальной производительностью, т.е. . По формуле (6.2) определим производительности станков , нормированные относительно производительности базового станка:;Таким образом, базовый станок работает в двенадцать раз быстрей первого станка, в шесть раз быстрее второго станка и в восемь раз быстрей четвертого.Пересчитаем фонды времени станков по формуле (6.3): [ч]; [ч]; [ч]; [ч].Из этих величин следует, что тот объем работ, который первый станок выполняет за свой фонд времени 360 ч базовый станок сможет выполнить за 300 ч.; второй станок выполняет за свой фонд времени 90 ч базовый станок сможет выполнить за 15 ч. Аналогично объем работ, который четвертый станок выполняет за 1296 ч базовый выполнит за 162 ч.Пересчитаем плановое задание по формуле (6.4): [ч]; [ч]; [ч].Отсюда следует, что план выпуска первого вида ткани базовый станок выполнит за 98 ч, второго вида – за 134 ч, третьего вида – за 62 ч.Пересчет себестоимостей производим по формуле (6.5), например: [руб./ч];  [руб./ч];  [руб./ч].В полученной ТЗ условие баланса (4.2) не выполняется, т.к. суммарный фонд времени станков больше, чем это необходимо для выполнения плана по выпуску всех тканей (353 ч > 294 ч). Введем фиктивный столбец и запишем все пересчитанные параметры РЗ в транспортную матрицу (см. табл.2). Фиктивные тарифы для упрощения приравняем к нулю.Таблица 2Транспортная матрица задачи №6.1СтанкиТканиФонд времени, чВ1В2В3ВФА172120192030А24324896015А3216216480146А41441201440162Объем выпуска , ч981346259353Для упрощения вместо оптимального решения рассмотрим опорный план , найденный методом северо-западного угла.Преобразуем опорный план ТЗ в опорный план РЗ согласно (6.6)Таким образом, первый станок должен 360 ч производить ткань первого вида,второй станок должен 90 ч производить ткань первого вида,третий станок должен 53 ч производить ткань первого вида и 93 ч производить ткань второго вида,четвертый станок должен 328 ч производить ткань второго вида, 496 ч производить ткань третьего вида и 472 ч простаивать Определим, сколько метров ткани каждого вида должны произвести станки по формуле (6.7)Определим общую себестоимость производства по формуле (6.1), используя вычисленные значения элементов матрицы (руб.).РешениеПостроим сетевую модель разработки и производства станков, используя упорядочение работ из табл.7.1.Рис.1. Сетевая модель задачи №7.1РешениеПостроим сетевую модель организации выступления хора при свечах, используя данные табл.7.2. Рис.1. Сетевая модель задачи №7.2РешениеА) Рассчитаем временные параметры событий и работ сетевой модели задачи №7.1, определим критические пути и их длительность.Все вычисления будем заносить в таблицу.Перечень работ и их продолжительность перенесем во вторую и третью графы. При этом работы следует записывать в графу 2 последовательно: сначала начиная с номера 1, затем с номера 2 и т.д.Во второй графе поставим число, характеризующее количество непосредственно предшествующих работ (КПР) тому событию, с которого начинается рассматриваемая работа.Так, для работы (5,6) в графу 1 поставим число 2, т.к. на номер 5 оканчиваются 2 работы: (3,5),(4,5).Далее заполняем графы 4 и 5. Для работ, имеющих цифру 0 в графе 2, в графу 4 также заносятся нули, а их значения в графе 5 получаются в результате суммирования граф 3 и 4.Для заполнения следующих строк графы 4, т.е. строк начиная с номера 2, просматриваются заполненные строки графы 5, содержащие работы, которые оканчиваются на этот номер, и максимальное значение переносится в графу 4 обрабатываемых строк.Этот процесс повторяется до тех пор, пока не будет заполнена последняя строка таблицы.Графы 6 и 7 заполняются обратным ходом, т.е. снизу вверх. Для этого просматриваются строки, оканчивающиеся на номер последнего события, и из графы 5 выбирается максимальная величина, которая записывается в графу 7 по всем строчкам, оканчивающимся на номер последнего события (т.к. tр(i)= tп(i)).Процесс повторяется до тех пор, пока не будут заполнены все строчки по графам 6 и 7.Содержимое графы 8 равно разности граф 6 и 4 или граф 7 и 5.Работа (i,j)Количество предшествующих работПродолжительность tijРанние сроки: начало tijР.Н.Ранние сроки: окончание tijР.О.Поздние сроки: начало tijП.Н.Поздние сроки:окончание tijП.О.Резервы времени: полный tijПРезервы времени: свободный tijС.В.Резервы времени: событий Rj(1,2)030303000(2,3)163939000(3,4)12911911000(3,5)119101617725(4,5)1111121617505(4,7)1711181320202(4,8)1911201120000(5,6)2512171722505(6,9)1417212226550(7,8)1018182020220(8,9)2620262026000(9,10)2326292629000(10,11)1729362936000а) графы 1 и 3 заполняются на основе исходных данных.б) в графе 2 записывается количество предшествующих работ по сетевому графику или определяется из графы 1 по числу работ, имеющих второй цифрой в коде ту, с которой начинается данная работа.г) в графе 4 раннее начало работ, выходящих из исходного события, а раннее окончание этих работ равно их продолжительности (гр. 5). Раннее начало последующих работ определяется путем выбора максимального из сроков раннего окончания предшествующих работ. Количество сравниваемых сроков равно количеству предшествующих работ графы 2. Раннее начало последующих работ можно определить после того, как найдено раннее окончание предшествующих. В свою очередь раннее окончание каждой работы находится как сумма величин раннего начала и продолжительности данной работы;г) продолжительность критического пути определяется после заполнения граф 4 и 5 как максимальная величина из сроков раннего окончания работ, которые ведут к завершающему событию 9;д) найденная величина критического пути ТKP дням заносится в графу 7 для всех работ, ведущих к завершающему событию. Затем заполнение ведется снизу вверх. Находятся все работы, следующие за рассматриваемой, и определяются разности между поздним окончанием этих работ и их продолжительностями.