Задание 1 (вариант 11)
Определить оптимальный план выгрузки маршрута однородного груза на станции с помощью табличного симплексного метода линейного программирования
На станции необходимо выгрузить маршрут однородного груза из 80 вагонов.
Каждый из трёх грузовых фронтов может вместить определённое количество вагонов.
Таблица 1.1
Количественные характеристики грузовых фронтов
Грузовой фронт |
Вместимость фронтов, ваг. |
Затраты локомотиво-часов на один вагон |
Доход, ден.ед./ваг. |
1 |
20 |
0,2 |
3 |
2 |
40 |
0,4 |
3 |
3 |
25 |
0,3 |
4 |
Подаёт, расставляет, собирает и убирает их один локомотив, который работает 23 часа в сутки.
Затраты локомотиво-часов маневровой работы, отнесённые на один вагон, различны для каждого грузового фронта. За выгрузку вагонов станция взимает с клиентов определённую плату. Но из-за различной технической оснащённости грузовых фронтов доход от выгрузки одного вагона не одинаков. Необходимо распределить вагоны по грузовым фронтам так, чтобы обеспечить максимальную выгрузку за сутки и максимальный доход.
Требуется:
Построить математическую модель задачи. Решить задачу табличным симплексным методом. Проанализировать решение, сделать вывод.
Задание 2
Построить оптимальный план работы двух погрузчиков на двух площадках с помощью графического симплекс-метода линейного программирования
Двум погрузчикам разной мощности за 24 часа нужно погрузить на первой площадке 228 т., на второй – 170 т.
Первый погрузчик на первой площадке может погрузить 12 т. в час, на второй – 12 т. в час.
Второй - на первой площадке 12 т. в час, на второй - 13 т. в час.
Стоимость работ, связанных с погрузкой 1 т., первым погрузчиком на первой площадке – 10 ден. ед., на второй – 8 ден. ед., вторым погрузчиком на первой площадке - 11 ден. ед, на второй - 13 ден. ед.
Нужно составить план работы, т.е. найти, какой объём работ должен выполнить каждый погрузчик на каждой площадке, чтобы стоимость всех работ по погрузке была минимальной.
Требуется:
1) записать постановку задачи;
2) формализовать задачу посредством задания математической модели;
3 свести задачу с четырьмя неизвестными к задаче с двумя неизвестными;
4) решить задачу, применяя графический метод решения;
5) проанализировать решение, сделать вывод.
Задание 3
Построить оптимальный план транспортировки продукции от поставщиков потребителям
Филиалы фирмы А1, А2 и А3 производят однородную (или взаимозаменяемую) продукцию и доставляют её потребителям В1, , B2 и В3.
В трёх пунктах производства сосредоточен груз в количествах соответственно 200, 50, 120 единиц.
Имеющийся груз необходимо доставить потребителям, спрос которых выражается величинами 150,45,75,50 единиц.
Известна стоимость производства и перевозки единицы продукции из -го (1,2,3) пункта отправления в -тый пункт назначения (1,2,3,4).
Требуется составить план перевозок, который полностью удовлетворяет спрос потребителей в грузе, и при этом суммарные транспортные издержки минимизируются.
Требуется:
1) записать постановку задачи;
2) установить тип модели транспортной задачи;
3) формализовать задачу посредством задания математической модели;
4) построить начальный план перевозок методом северо-западного угла (или методом минимальной стоимости), определить соответствующие ему затраты на перевозки;
5) методом потенциалов найти оптимальный план и соответствующие ему затраты;
6) проанализировать решение, сделать вывод.
Задание 4
Построить оптимальный план доставки груза от поставщиков потребителям как транспортную задачу в сетевой форме
Имеется сеть (рис. 4.1) с десятью вершинами. Часть вершин () обозначают поставщиков продукции, остальные потребителей.
Ребра, соединяющие вершины, определяют возможные пути следования груза, а цифры на рёбрах - расстояния между станциями. Цифры со знаком «+» («плюс») у вершин означают ресурсы поставщиков, а со знаком «-» («минус») - потребности получателей. Необходимо прикрепить поставщиков к потребителям так, чтобы пробеги были наименьшими.
Таблица 4.1
Варианты исходных данных (избытки и недостатки груза у поставщиков и потребителей)
вариант |
Номер вершины сети |
|||||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
11 |
-10 |
200 |
-100 |
150 |
-50 |
-40 |
-22 |
-10 |
-18 |
-100 |
Задание 5
Решить задачу распределения инвестиций между предприятиями методом динамического программирования
Производственное объединение выделяет четырём входящим в него предприятиям кредит в сумме 100 млр. ден. ед. для расширения производства н увеличения выпуска продукции. По каждому предприятию известен возможный прирост (1,...,4) выпуска продукции (в денежном выражении) в зависимости от выделенной ему суммы .
Выделяемые суммы кратны 20 млр. ден. ед. При этом предполагаем, что прирост выпуска продукции на м предприятии не зависит от суммы средств, вложенных в другие предприятия, а общий прирост выпуска продукции в производственном объединении равен сумме приростов, полученных на каждом предприятии объединения. Распределить кредит таким образом, чтобы общий прирост выпуска продукции на производственном объединении был максимальным. Требуется:
1) записать постановку задачи;
2) формализовать задачу в терминах динамического программирования;
3) решить задачу, применяя математический аппарат динамического программирования;
4) проанализировать решение, сделать вывод.
Задание 6
Построить сетевой график (длина работы - tij ) Выделить критический путь и найти его длину. Определить резервы времени каждого события . Определить резервы времени (полные, частные первого вида, свободные и независимые) всех работ и коэффициенты напряженности работ, не лежащих на критическом пути. Выполнить оптимизацию сетевого графика по времени.
Таблица 6.1
Работы |
tij |
dij |
kij |
|
В-11 |
||
1,2 |
9 |
6 |
0,6 |
1,3 |
8 |
3 |
0,1 |
1,4 |
14 |
12 |
0,3 |
2,3 |
16 |
2 |
0,8 |
2,5 |
5 |
2 |
0,9 |
3,5 |
12 |
7 |
0,5 |
4,6 |
4 |
2 |
0,3 |
5,6 |
10 |
7 |
0,4 |
|
В=165 |
Расчёт временных параметров сетевого графика включает четыре этапа.
Первый этап называется прямым проходом. Вычисления начинаются с исходного события и продолжаются, пока не будет достигнуто завершающее событие всей сети.
Для каждого события вычисляется число, представляющее ранний срок свершения события по формуле
. (6.1)
На втором этапе, называемом обратным проходом, вычисления начинаются с завершающего события и продолжаются до тех пор, пока не будет достигнуто исходное событие. Для каждого события вычисляют поздний срок свершения события по формуле
. (6.2)
На третьем этапе рассчитывается резерв времени событий по формуле
R(i) = tп(i) – tр(i). (6.3)
На четвёртом этапе определяют критические события, как не имеющие резервов времени, критические работы и критический путь. По результатам расчётов строят сводную таблицу, необходимую для построения календарного графика.
При расчете временных параметров вручную удобно проводить вычисления непосредственно на графе, воспользовавшись четырехсекторной схемой. В этом случае каждый кружок, обозначающий событие, делят на четыре сектора, в каждом из которых записывается соответствующая информация (рис. 6.2).
Рис. 6.2. Четырех секторная схема
Проставляем в верхних секторах номера событий (в соответствии с ранжированием). Рассматривая события в порядке возрастания номеров и имея в виду, что tр(1) = 0, по входящим в это событие работам по формуле (6.1) определяем tр(j) и записываем в левом секторе. Начиная с конечного события, для которого tп(n) = tкр (п – номер конечного события), для каждого события по выходящим из него работам по формуле (6.2) определяем tп(i) и записываем в правом секторе.
Список использованной литературы:
Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986. Вентцель Е.С. Исследование операций. - М: Сов. радио, 1972. Калихман И.Л. Сборник задач по математическому программированию. - М.: Высшая школа, 1975 Костевич Л.С. Математическое программирование. - Мн.: ООО «Новое знание», 2003. Кузнецов А.В., Холод Н.И. Математическое программирование. - Мн.: Выш. школа, 1982. Сборник задач и упражнений по высшей математике. Математическое программирование / Под ред. А.В.Кузнецова - Мн.: Выш. школа, 1995.