6.2. Задание на контрольную работу № 2

Целями выполнения данной контрольной работы являются: закрепление теоретических знаний студентов по математическому программированию для двух вариантов постановок задач: транспортной задачи линейного программирования и задачи динамического программирования; самостоятельной постановке вероятностной модели времени вывоза запасов материальных средств со складов потребителям и получение реальных результатов по построенной модели.

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

Задача. Имеются два склада с запасами однородных материальных средств в количествах а₁ и а₂; имеются шесть потребителей этих материальных средств с потребностями, соответственно, b₁, b₂, b₃, b₄, b₅, b₆; известны расстояния между складами и потребителями, в километрах (таблица 4); запасы на складах, потребность потребителей, количество автомобилей по списку в автопредприятии и КТГ автомобилей – таблица 5. Однако не известно точное время начала вывоза запасов.

Требуется спланировать вывоз материальных средств (МС) со складов так, чтобы их время вывоза было минимальным – т.е. определить минимальное время вывоза запасов МС со складов.

Учитывая, что количество исправных автомобилей в произвольный момент времени является величиной случайной, требуется определить вероятностную характеристику времени вывоза запасов в зависимости от количества исправных автомобилей. Другими словами, требуется определить функцию распределения вероятности времени вывоза запасов МС со складов потребителям в зависимости от наличия исправных автомобилей в автомобильном предприятии.

Коэффициенты условий движения для всех маршрутов принять: если длина маршрута не превосходит 20 км – 1,1; не более 30 – 1,2; не более 40 – 1,4; более 40 – 1,6.

Время погрузки на складах: если запасы на складах больше потребности потребителей – 1,5, если равны – 1,4, если меньше – 1,3 часа.

Время разгрузки на складах потребителей: если количество разгружаемых материальных средств менее 100 тонн – 1,1; менее 200 – 1,2; менее 300 – 1,3 часа, далее увеличивается с увеличением на каждые 100 тонн на 0,1 часа.

Среднюю грузоподъемность автомобилей принять для всех вариантов равной 5,5 тонны, а скорость движения – 35 км/ч.

Таблица 4

Варианты	Склады	Потребители
		В1	В2	В3	В4	В5	В6
1	А1	15	35	21	33	27	28
	А2	24	25	27	18	26	23
2	А1	25	33	28	45	23	27
	А2	34	52	23	28	16	22
3	А1	28	19	28	25	28	27
	А2	32	54	33	38	36	29
4	А1	15	21	18	15	13	27
	А2	26	22	13	18	16	12
5	А1	24	25	27	18	26	23
	А2	25	33	28	45	23	27
6	А1	24	25	27	19	28	23
	А2	25	33	28	54	33	27
7	А1	34	52	23	21	18	22
	А2	28	19	28	22	13	27
8	А1	35	34	18	25	27	37
	А2	24	32	29	33	28	22
9	А1	19	19	28	25	28	27
	А2	54	54	33	38	36	32
0	А1	21	21	18	15	13	17
	А2	22	22	13	18	16	22

Таблица № 5

№№ вари-антов	Запасы на складах, т		Потребности потребителей, т							К-во а/м, N		КТГ
	а1	а2	b1	b2	b3	b4	b5	b6
1	700	800	330	350	320	230	220	240	50		0,70
2	720	870	250	250	340	190	330	250	55		0,65
3	800	570	280	50	320	220	340	180	40		0,75
4	720	760	210	170	300	400	220	80	68		0,70
5	750	780	100	280	450	230	220	210	77		0,70
6	820	880	290	410	420	250	170	160	58		0,65
7	670	830	190	210	200	300	380	130	67		0,75
8	730	760	220	220	320	220	340	180	64		0,70
9	580	880	400	320	250	200	300	400	53		0,70
0	980	360	250	220	180	380	130	210	45		0,65

Исходные данные для контрольной работы выбираются по двум последним цифрам шифра студента: по последней цифре – расстояния между складами и потребителями (таблица 4), по предпоследней цифре – запасы материальных средств на складах, потребность потребителей, количество автомобилей в автомобильном предприятии по списку, коэффициент технической готовности автомобилей на автомобильном предприятии (таблица 5).

Контрольная работа № 2 решается с использованием ЭВМ. Для этого используются программы: transp.exe - для решения транспортной задачи линейного программирования, dptr-4.exe – для решения задачи динамического программирования и используется стандартный табличный процессор Excel – для определения и отображения в графическом режиме плотности распределения и функции распределения времени вывоза запасов со складов в зависимости от количества автомобилей в автопредприятии и их технической готовности.

Методические указания к выполнению контрольной работы № 2.

При выполнении контрольной работы рекомендуется следующий порядок ее выполнения:

1. Исходя из индивидуального шифра, студент выбирает вариант своего задания из таблиц 4 и 5.

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

3. Осуществляется постановка задачи динамического программирования и формируется массив исходных данных для решения задачи. При этом указываются какие данные решения транспортной задачи линейного программирования, являются исходными для решения задачи динамического программирования. Задача решается на ЭВМ.

4. В результате решения строится график зависимости времени вывоза запасов потребителям от наличия исправных автомобилей в автопредприятии – с использованием табличного процессора Excel.

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

6. Оформить работу в соответствии с требованиями по оформлению контрольных работ, включая следующие моменты:

• а) дать краткое теоретическое описание постановки транспортной задачи линейного программирования; подготовить массив исходных данных для ее решения; на схеме показать результаты решения задачи;

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

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

Рассмотрим формирование основных моментов контрольной работы на реальном примере. На первом этапе осуществляем выбор варианта исходных данных. В качестве исходных данных принимаем:

Таблица 6

Склады	Потребители
	В1	В2	В3	В4	В5	В6
А1	25	35	24	33	27	28
А2	34	25	27	38	28	33

Таблица № 7

Запасы на складах, т		Потребности потребителей, т							Кол-во а/м, N		КТГ
а1	а2	b1	b2	b3	b4	b5	b6
800	850	310	380	320	330	220	240	66		0,75

На втором этапе осуществляем постановку транспортной задачи линейного программирования.

Постановка транспортной задачи.

Имеется n складов A₁, A₂, ..., A_n с однородными материальными средствами в количествах а₁, а₂, . . ., a_n; имеется m потребителей B₁, B₂, ..., B_m данных материальных средств, потребности которых равны соответственно b₁, b₂,..., b_m; известны транспортные издержки c_ij, связанные с доставкой единицы (например, тонны) материальных средств со склада A_i потребителю B_j (i = 1, 2, ..., n; j = 1, 2, ..., m). Графическая постановка – рис. 7.

A₂

B₁

A₁

B₂

B_m

А_n

Рис. 7

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

Математическая модель транспортной задачи.

Неизвестными (управляемыми факторами) в задаче являются величины x_ij - объем подвоза однородных материальных средств со склада A_i потребителю B_j (i = 1, 2, ..., n; j = 1, 2, ..., m).

Условия, которым должны подчиняться неизвестные:

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

запланированный суммарный объем выдаваемых со склада материальных средств не может превосходить наличия их на складе;

объем подвоза по любому маршруту должен быть неотрицательным.

С учетом сказанного получаем математическую модель:

целевая функция: _{n m}

  c_ij x_ij  min,

^{i=1 j=1}

ограничения: _{n m}

 x_ij  b_j, j = 1, 2, ..., m,  x_ij  a_i, i = 1, 2, ..., n;

^{i=1 j=1}

условия, накладываемые на неизвестные:

х_ij  0  i, j_.

Реальная математическая модель транспортной задачи имеет вид:

целевая функция:

25x₁₁+35x₁₂+24x₁₃+33x₁₄+27x₁₅+28x₁₆+34x₂₁+25x₂₂+27x₂₃+38x₂₄+28x₂₅+33x₂₆min

ограничения:

x₁₁ + x₁₂ + x₁₃ + x₁₄ + x₁₅ + x₁₆  800;

x₂₁ + x₂₂ + x₂₃ + x₂₄ + x₂₅ + x₂₆  850;

x₁₁ + x₂₁  310;

x₁₂ + x₂₂  380;

x₁₃ + x₂₃  320;

x₁₄ + x₂₄  330;

x₁₅ + x₂₅  220;

x₁₆ + x₂₆  240;

условия, накладываемые на неизвестные:

x₁₁  0; x₁₂  0; x₁₃  0; x₁₄  0; x₁₅  0; x₁₆  0;

x₂₁  0; x₂₂  0; x₂₃  0; x₂₄  0; x₂₅  0; x₂₆  0.

Формируем массив исходных данных для решения в виде таблицы 8.

Таблица 8

Склады	Потребители						Запасы, т
	В1	В2	В3	В4	В5	В6
А1	25	35	24	33	27	28	800
А2	34	25	27	38	28	33	850
Потреб-ность, т	310	380	320	330	220	240

Результаты решения задачи отображаем на схеме (рис. 8).

На третьем этапе осуществляется постановка задачи динамического программирования, формулируется теорема Беллмана и готовится массив исходных данных.

В₁

В₂

В₃

310 70 250 380

А₁

А₂

90 330 220

В₄

В₅

В₆

Рис. 8

Постановка задачи динамического программирования.

Рассматривается развивающийся во времени управляемый процесс и задачу об оптимальном управлении данным процессом. Областью применения динамического программирования является решение оптимизационных многоэтапных задач управления с одним критерием эффективности. Этап характеризуется тем, что на нем принимается только одно управленческое решение. Развитие исследуемого процесса происходит, детерминировано, т.е. если известно его состояние, в котором он находился на каком-то этапе, и принятое на данном этапе решение, то оно однозначно определяет состояние процесса на следующем этапе.

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

Динамическое программирование базируется на принципе оптимальности Беллмана (теореме Беллмана), который заключается в следующем: для того, чтобы процесс в целом развивался оптимально, необходимо и достаточно, чтобы его развитие из любого достигнутого промежуточного состояния протекало оптимально.

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

Рассмотрим последний этап. На начало этого этапа процесс может находиться в различных состояниях, что зависит от решений, принимавшихся на предыдущих этапах. Поэтому для каждого возможного состояния процесса на начало последнего этапа находим оптимальное для этого этапа решение.

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

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

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

Математическая постановка задачи динамического программирования.

Имеется несколько маршрутов подвоза МС, реальные объемы подвоза на этих маршрутах, протяженности маршрутов (исходные данные и результаты решения транспортной задачи линейного программирования). Определяются коэффициенты условий движения на маршрутах, времена погрузки на складах и выгрузки МС на складах потребителей; списочное количество автомобилей в автомобильном предприятии, средняя грузоподъемность одного автомобиля и коэффициент технической готовности автомобилей в автомобильном предприятии.

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

Условием успешного окончания всего комплекса работ по доставке МС потребителям является выделение на каждый маршрут не менее одного автомобиля.

Время доставки запасов (t_дост) одним автомобилем составляет:

t_дост = t_погр + t_выгр + 2 l К_уд / V_ср,

где t_погр – время погрузки МС на складах, ч;

t_выгр – время выгрузки МС на складе потребителя, ч;

l – длительность маршрута, км;

К_уд – коэффициент условий движения на маршруте;

V_ср – средняя скорость движения на маршруте, км/ч.

Тогда полное время доставки запасов МС одному потребителю составляет:

T_дост = t_дост m,

где m = Q / (q N_выд) – необходимое количество рейсов для вывоза запасов МС со склада одному потребителю; округляется в большую сторону;

Q – количество МС, вывозимых для данного потребителя со склада, т;

q – средняя грузоподъемность одного автомобиля, т;

N_выд – выделенное количество автомобилей на данный маршрут.

Целевая функция задачи динамического программирования будет иметь вид: