Оптимизация доставки грузов и план выпуска продукции.

Содержание

1. Постановка задачи и основные исходные данные
2. Формирование связей пунктов отправления и назначения
2.1. Формирование математической модели задачи
2.2. Оптимальное прикрепление пунктов отправления и назначения груза
3. Разработка оптимального плана выпуска продукции
3.1. Формирование математической модели задачи
3.2. Решение задачи оптимизации плана выпуска продукции симплекс-методом
4. Анализ полученных результатов
Список использованной литературы

Оптимизация доставки грузов и план выпуска продукции.

Di,j - ограничение пропускной способности коммуникации между поставщиком Ai и потребителем Bj.M - некоторое число, близкое к бесконечностиe - некоторое число, близкое к нулю.Исходная таблица по данным задачи имеет вид:ПоставщикПотребительЗапасы грузаКЛМНРA 2000M 3000M 1600M 1000M 1450M350Д 2050M 2200M 2300M 2600M 2100M270Е 1600M 2000M 1700M 3300M 1700M200Потребность1803002007070 2.2. Оптимальное прикрепление пунктов отправления и назначения грузаБудем обозначать всех поставщиков через Ai, а потребителей через Bj.Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям.Находим опорный план для задачи с ограничениями.Введем некоторые обозначения:Ai* - излишек нераспределенного груза от поставщика AiBj* - недостача в поставке груза потребителю BjDi,j- ограничение пропускной способности коммуникации между поставщиком Ai и потребителем Bj Находим незанятую клетку с минимальным тарифом: (1,4).Помещаем туда меньшее из чисел A1*=350, B4*=70 и D1,4=MНаходим незанятую клетку с минимальным тарифом: (1,5).Помещаем туда меньшее из чисел A1*=280, B5*=70 и D1,5=MНаходим незанятую клетку с минимальным тарифом: (1,3).Помещаем туда меньшее из чисел A1*=210, B3*=200 и D1,3=MНаходим незанятую клетку с минимальным тарифом: (3,1).Помещаем туда меньшее из чисел A3*=200, B1*=180 и D3,1=MНаходим незанятую клетку с минимальным тарифом: (3,2).Помещаем туда меньшее из чисел A3*=20, B2*=300 и D3,2=MНаходим незанятую клетку с минимальным тарифом: (2,2).Помещаем туда меньшее из чисел A2*=270, B2*=280 и D2,2=MНаходим незанятую клетку с минимальным тарифом: (1,2).Помещаем туда меньшее из чисел A1*=10, B2*=10 и D1,2=MПоставщикПотребительЗапасы грузаB1B2B3B4B5A1 200 M 30010M 160200M 10070M 14570M350A2 205 M 220270M 230 M 260 M 210 M270A3 160180M 20020M 170 M 330 M 170 M200Потребность1803002007070 Целевая функция F=144350 Решаем задачу c ограничениями методом потенциалов:Этап 1Так как суммарная величина нераспределенного груза/потребностей epsilon = 0, то текущий план является опорным планом транспортной задачи с ограничениями.Этап 2Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Uj+Vi=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.Потенциалы Ui:U1=0V2=C1,2-U1= 300V3=C1,3-U1= 160V4=C1,4-U1= 100V5=C1,5-U1= 145U2=C2,2-V2= -80U3=C2,3-V2= -100V1=C3,1-U3= 260Определяем значения оценок Si,j=Ci,j-(Vj-Ui) для всех свободных клеток:Для случая Xi,j = 0 условие оптимальности оценки Si,j определяется следующим образом: Si,j >=0.Для случая Xi,j = Di,j условие оптимальности оценки Si,j определяется следующим образом: Si,j <=0.оценки Si,j для всех клеток, удовлетворяющих условию: Xi,j = 0 S1,1 = c1,1 - (v1 + u1) = -60.S2,1 = c2,1 - (v1 + u2) = 25.S2,3 = c2,3 - (v3 + u2) = 150.S2,4 = c2,4 - (v4 + u2) = 240.S2,5 = c2,5 - (v5 + u2) = 145.S3,3 = c3,3 - (v3 + u3) = 110.S3,4 = c3,4 - (v4 + u3) = 330.S3,5 = c3,5 - (v5 + u3) = 125.оценки Si,j для всех клеток, удовлетворяющих условию: Xi,j = Di,j отсутствуютЕсли имеются неоптимальные оценки и для случая Xi,j = 0, и для случая Xi,j = Di,j, то наиболее потенциальной(неоптимальной) из них считается максимальная по модулю оценка. Если имеется несколько клеток с одним и тем же наиболее неоптимальным значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,1). Для нее оценка равна -60.Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус".ПоставщикПотребительЗапасы грузаB1B2B3B4B5A1+200 M-30010M 160200M 10070M 14570M350A2 205 M 220270M 230 M 260 M 210 M270A3-160180M+20020M 170 M 330 M 170 M200Потребность1803002007070 Перемещаем по циклу груз величиной в 10 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:ПоставщикПотребительЗапасы грузаB1B2B3B4B5A1 20010M 300 M 160200M 10070M 14570M350A2 205 M 220270M 230 M 260 M 210 M270A3 160170M 20030M 170 M 330 M 170 M200Потребность1803002007070 Целевая функция F= 143750 Значение целевой функции изменилось на 600 единиц по сравнению с предыдущим этапом. Этап 3Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Uj+Vi=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.Потенциалы Ui:U1=0V1=C1,1-U1= 200V3=C1,3-U1= 160V4=C1,4-U1= 100V5=C1,5-U1= 145U3=C1,3-V1= -40V2=C3,2-U3= 240U2=C2,2-V2= -20Определяем значения оценок Si,j=Ci,j-(Vj-Ui) для всех свободных клеток:Для случая Xi,j = 0 условие оптимальности оценки Si,j определяется следующим образом: Si,j >=0.Для случая Xi,j = Di,j условие оптимальности оценки Si,j определяется следующим образом: Si,j <=0.оценки Si,j для всех клеток, удовлетворяющих условию: Xi,j = 0 S1,2 = c1,2 - (v2 + u1) = 60.S2,1 = c2,1 - (v1 + u2) = 25.S2,3 = c2,3 - (v3 + u2) = 90.S2,4 = c2,4 - (v4 + u2) = 180.S2,5 = c2,5 - (v5 + u2) = 85.S3,3 = c3,3 - (v3 + u3) = 50.S3,4 = c3,4 - (v4 + u3) = 270.S3,5 = c3,5 - (v5 + u3) = 65.оценки Si,j для всех клеток, удовлетворяющих условию: Xi,j = Di,j отсутствуютТак как все условия оптимальности выполнены, то полученный план является оптимальным.Транспортная задача решена. Перейдем к обозначениям в исходных данных:ПоставщикПотребительЗапасы грузаКЛМНРA 20010M 300 M 160200M 10070M 14570M350Д 205 M 220270M 230 M 260 M 210 M270Е 160170M 20030M 170 M 330 M 170 M200Потребность1803002007070 Целевая функция F= 1437503. Разработка оптимального плана выпуска продукции3.1. Формирование математической модели задачиСимплекс метод – универсальный метод для решения линейной системы уравнений или неравенств и линейного функционала. Общая идея симплексного метода (метода последовательного улучшения плана) для решения задачи линейного программирования состоит в:– умении находить начальный опорный план;– наличии признака оптимальности опорного плана;– умении переходить к нехудшему опорному плану.Т.е. основная идея симплекс-метода решения задачи линейного программирования состоит в переходе от базиса Б к новому базису Б’ так, чтобы новое значение функции f уменьшилось (увеличилось) или по крайней мере не увеличилось (не уменьшилось). Таким путем можно прийти к базису, дающему минимум (максимум) функции f, либо выяснить, что задача не имеет решений. Переход к новому базису Б происходит путем удаления из исходного множества базисных переменных одной переменной и введения вместо нее другой свободной переменной. Эти преобразования связаны с перестройкой системы. Результатом каждого очередного этапа преобразований является новый базис и соответствующее ему опорное решение и значение целевой функции. Этот подход составляет основное содержание метода решения задачи линейного программирования, называемого симплекс – методом.Симплекс-метод – это метод упорядоченного перебора опорных планов. Упорядоченность в данном случае обеспечивается последовательным перебором опорных планов с монотонным изменением значения целевой функции в сторону возрастания (убывания). В теоретическом обосновании симплексного метода обнаруживается, что в случае единичного базиса (векторы образуют единичную матрицу) коэффициенты разложения некоторого вектора по векторам базиса, используемые в симплексной процедуре, совпадают с компонентами самого вектора (в общем же случае придется решать систему уравнений). Поэтому на практике стремятся иметь дело с единичным базисом. Пусть стоит задача максимизации (минимизации)LX=j=1nCjXj (2.1)при условиях j=1nAjXj=B 2.2 Xj≥0, j=1,…,n (2.3)где Aj (j=1,...,n) , B - m-мерные векторы.Вектор X=(X1,X2,..,Xn) , удовлетворяющий условиям (2.2) и (2.3), называется планом. Множество планов в геометрической интерпретации представляет собой выпуклый многогранник. План, который обращает в равенство хотя бы n независимых ограничений задачи, называется опорным планом. Опорный план соответствует некоторой вершине многогранника планов. Опорный план содержит не свыше m положительных компонент (m - число независимых ограничений задачи). Опорный план, содержащий менее m положительных компонент, называют вырожденным. Оптимальный план является опорным (если оптимум достигается на двух опорных планах, то оптимальны все планы, соответствующие отрезку, соединяющему соответствующие вершины). Система m векторов Aj при положительных компонентах опорного плана называется базисом этого плана. Предположим, что исходная задача приведена к канонической форме (2.1)-(2.3) при В 0 и первые m векторов начального базиса образуют единичную матрицу (их можно принять за базис). Для единообразия описания вычислительной процедуры в дальнейшем будем пользоваться т. н. симплексными таблицами вида:В первом столбце таблицы (С баз) записывают коэффициенты целевой функции (С1, С2 …Сm) при базисных переменных (напомним, что в базис входят только векторы, образующую единичную подматрицу, как в нашем случае А1 / Аm). Во втором столбце (Базис плана) должны находиться базисные векторы данного опорного плана, а в третьем столбце (План Х) - правая часть ограничений задачи (базисные компоненты плана). Таким образом, перемножая элементы первого столбца таблицы со столбцом - "План Х", и суммируя эти произведения, мы получаем значение целевой функции (ячейка - L(X)=С1*В1 + С2*В2+…+ +Сm*Bm). Первая строка симплексной таблицы содержит коэффициенты линейной функции нашей задачи и остается неизменной на протяжении всего решения (С1, С2, …, Сn). В центральной части таблицы записывают коэффициенты при неизвестных в ограничениях исходной задачи (Z11,…, Z1n,…, Zm1,…, Zmn). При этом следует заметить, что коэффициенты при базисных переменных в ограничениях задачи составляют единичную подматрицу.