Главная страница
Навигация по странице:

  • 5.4.1. ХАРАКТЕРНЫЕ ОСОБЕННОСТИ И ОБЩАЯ ПОСТАНОВКА ТРАНСПОРТНОЙ ЗАДАЧИ

  • 5.4.2. ВЫБОР ОПТИМАЛЬНОГО ПЛАНА ТРЕЛЕВКИ

  • 5.4.2.1. Содержание заданной ситуации.

  • 5.4.2.2. Постановка задачи выбора оптимального плана трелевки. Определение цели

  • Построение математической модели

  • 5.4.3.3. Алгебраическое решение задачи методом потенциалов . Алгоритм решения транспортной задачи методом потенциалов

  • Процедура решения транспортной задачи на основе алгоритма.

  • 5.4.3. КОМПЬЮТЕРНОЕ РЕШЕНИЕ ПОСТАВЛЕННОЙ ЗАДАЧИ В МАТЕМАТИЧЕСКИХ ПРОГРАММНЫХ СРЕДАХ

  • Транспортная задача. Задача линейного программирования выбор эффективного плана транспортировки древесины


    Скачать 1.77 Mb.
    НазваниеЗадача линейного программирования выбор эффективного плана транспортировки древесины
    АнкорТранспортная задача.docx
    Дата17.07.2018
    Размер1.77 Mb.
    Формат файлаdocx
    Имя файлаТранспортная задача.docx
    ТипЗадача
    #21607

    5.4. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО
    ПРОГРАММИРОВАНИЯ: ВЫБОР ЭФФЕКТИВНОГО ПЛАНА
    ТРАНСПОРТИРОВКИ ДРЕВЕСИНЫ

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

    Транспортная и сетевые задачи и модели [3, 7], 9, 57], разрабатываемые на их основе, используются также при: 1) управлении запасами; 2) составлении сменных графиков и календарных планов; 3) определении наиболее экономичной схемы транспортировки древесины из исходных пунктов различными видами транспорта: водный – плоты, баржи и пр.; сухопутный – автомобильный, железнодорожный и пр.); 4) проектировании трассы лесовозной дороги на основе критерия минимальной стоимости се строительства; 5) регулировании расхода воды и т. д.

    Специфическая структура этой задачи предполагает использование более эффективного вычислительного метода, основой которого является сим- плекс–метод, хотя последний не отвергается. В данном разделе рассматривается пример с изложением всей последовательности моделирования и подробными пояснениями теории вопроса на конкретном отраслевом примере.
    5.4.1. ХАРАКТЕРНЫЕ ОСОБЕННОСТИ И ОБЩАЯ ПОСТАНОВКА ТРАНСПОРТНОЙ ЗАДАЧИ
    Характерными особенностями транспортных моделей являются: 1) наличие не менее двух исходных пунктов поставки; 2) наличие не менее двух конечных пунктов потребления; 3) из каждого исходного пункта в каждый конечный пункт поставляется однородная продукция – хлысты, сортименты, пиломатериалы и пр.; 4) известны или можно определить величины, характеризующие объем продукции, поставляемой из каждого исходного пункта, – мощность по отгрузке каждого исходного пункта; 5) известны или можно определить объемы продукции, потребляемые в каждом пункте назначения, – мощность по приемке каждого из пунктов потребления; 6) известны или можно определить себестоимость (затраты) или прибыль перевозки единицы продукции из каждого исходного пункта в каждый пункт потребления.

    Цель, достигаемая решением транспортной задачи, – определение такого количества продукции, которое следует транспортировать из каждого исходного пункта в каждый пункт назначения и при котором транспортные расходы будут минимальными или прибыль (в линеаризованных задачах) от транспортировок будет максимальна. Какова цель – минимизация затрат на транспортировку или максимизация прибыли – таков и выбор критерия. На рис. 5.18 изображена транспортная модель в виде сети с т исходными пунктами и п пунктами назначения. Исходным пунктам и пунктам назначения соответствуют вершины (окружности), а маршрутам транспортировки – дуги (прямые линии). Количество продукции, отгружаемое (производимое) в каждом пункте i, обозначим через аi, а потребляемое (хранимое) в каждом пункте j – через bj; сij – себестоимость транспортировки единицы продукции из каждого исходного пункта i в каждый пункт назначения j.


    рис518.jpg

    Рис. 5.18. Схематическое представление транспортной модели


    Обозначим через xij – количество продукции (объемы), перевозимое из исходного пункта i в пункт назначения j. Тогда задача ЛП транспортного типа в общем виде формулируется следующим образом:

    минимизировать у= (5-13)

    при ограничениях = (5.14)

    весь объем транспортировки из каждого i-го пункта не может быть больше, чем там имеется в наличии:

    , j=; (5.15)

    весь объем транспортировки в каждый j-й пункт должен быть, по крайней мере, равен спросу (потребности) этого пункта:

    xij i= j=. (5.16)

    Если суммарный объем исходных пунктов (поставщиков) равен суммарному объему пунктов потребления (потребителей), Σаibj , то модель называется сбалансированной транспортной моделью.

    В реальных производственных ситуациях не всегда соблюдается изложенное условие – объем поставок равен объему потребления. Поэтому с целью упрощения процесса решения транспортную модель искусственно приводят к сбалансированной посредством введения фиктивных исходных пунктов или фиктивных пунктов назначения. В этом случае в выражения ограничений (5.14) – при введении фиктивного исходного пункта – или (5.15) – при введении фиктивного пункта потребления – вносятся соответствующие дополнения. Стоимость транспортировки из фиктивного исходного в фиктивный пункты потребления принимается равной нулю.

    5.4.2. ВЫБОР ОПТИМАЛЬНОГО ПЛАНА ТРЕЛЕВКИ
    Здесь представлен пример постановки транспортной задачи [3] для ситуации, когда объемы поставки не равняются объемам потребления. Задачи такого типа весьма актуальны в текущий момент в связи истощенным лесным фондом и, как следствие, наличием отводимых в рубку разрозненных лесосек неправильной конфигурации. Постановку задачи для нашего примера рассмотрим в последовательности, рекомендуемой в разделах 1.1, 1.5, 2.3.

    5.4.2.1. Содержание заданной ситуации. Имеются две лесосеки Л1 и Л2, в каждой из которых базируется по одной лесозаготовительной бригаде. Обе бригады производят трелевку хлыстов на три погрузочных пункта П1, П2 и П3. Изложенная ситуация представлена на рис. 5.19. Сменный объем трелевки с лесосеки Л1–Q1=250 м3, с лесосеки Л2–Q2=150 м3.

    Вместимость погрузочных пунктов в расчете на смену составляет, соответственно, V1=200 м3; V2=150 м3; V3=100 м3. Себестоимость трелевки 1 м3 с каждой лесосеки на каждый погрузочный пункт составляет, соответственно: с первой на первый – 2 руб.; с первой на второй – 1,5 руб.; с первой на третий – 4 руб.; со второй на первый – 3 руб.; со второй на второй – 2 руб.; со второй на третий 1 руб. Для корректного решения рассматриваемой задачи введем допущение о том, что трелевка производится с условных центров лесосек. Перечисленные ранее затраты на трелевку 1 м3 являются средними по каждой лесосеке и определены трелевкой из условных центров.


    рис519.jpg

    Рис. 5.19. Графическое представление задачной ситуации


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

    5.4.2.2. Постановка задачи выбора оптимального плана трелевки.

    Определение цели. Найти объемы трелевки с каждой лесосеки на каждый погрузочный пункт, минимизирующие затраты на трелевку в смену (транспортные издержки).

    Формулировка проблемы. Общая содержательная формулировка задачи дана в п. 5.4.2.1.

    Этапы формулировки проблемы включают в себя:

    1) управляемые переменные – сменные объемы трелевки с каждой лесосеки на каждый погрузочный пункт, м3;

    2) переменные состояния – технологические и технико – экономические факторы: сменные объемы трелевки с каждой лесосеки, вместимости каждого погрузочного пункта, себестоимость трелевки 1 м3 с каждой лесосеки на каждый погрузочный пункт по соответствующим волокам, количество лесосек и погрузочных пунктов;

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

    4) критерий - суммарные затраты на трелевку, руб.

    Построение математической модели. Для построения математической модели принимается допущение о том, что производится транспортировка однородной продукции и конструируемая транспортная модель является однопродуктовой. С порядком конструирования и решения многопродуктовых моделей можно познакомиться в [7 и 55].

    Построение (конструирование) математической модели производится в следующем порядке:

    1) обозначение переменных – объемов трелевки с каждой лесосеки в каждый погрузочный пункт – производится в соответствии с рис. 5.19 (в обозначениях первый индекс i соответствует номеру лесосеки, второй j – номеру погрузочного пункта) и имеет следующий вид: х11, x12, x13, x21, x22, x23; у – функция цели;

    2) целевая функция разрабатывается исходя из того, что затраты на любой из маршрутов равны произведению себестоимости трелевки 1 м3 по данному маршруту на объем трелевки (пока неизвестный) лесоматериалов по этому же маршруту, отсюда и с учетом выражения (5.13) функция цели примет следующий вид:

    у==2х11+1,5x12+4х13x21+2х22+1x23;

    3) построение ограничений производится на основе содержательной сущности задачи, в которой отражены: а) ограничения на объем трелевки с каждой лесосеки: необходимо стрелевать с каждой лесосеки столько древесины, сколько на них заготавливается в смену; б) ограничения на объем поступления или потребления: необходимо доставить на каждый погрузочный пункт столько древесины, сколько обеспечивает его вместимость, и не менее. В содержании задачи определено, что суммарный объем трелевки в смену Q=Q1+Q2=400 м3, а вместимость погрузочных пунктов V=V1+V2+V3=450 м3. В этом случае имеем несбалансированную транспортную модель, Q<V. Приведение транспортной модели к сбалансированной, чтобы недостаток древесины в 50 м3 для погрузочных пунктов оптимально распределялся между ними, производится введением дополнительной фиктивной лесосеки Q со сменным объемом трелевки в 50 м3. В связи с тем, что реально такой лесосеки нет – трелевка из нее не производится, полагаем, что себестоимость трелевки с этой лесосеки равняется нулю.

    Аналогичный прием можно использовать, если объем поставок больше объема потребления – объем трелевки с лесосек больше вместимости погрузочных пунктов. В этом случае вводится фиктивный погрузочный пункт. При введении фиктивной лесосеки Л появляются три дополнительные переменные х31, х32, х33, и ограничения с учетом выражений (5.14)–(5.15) примут следующий вид:

    x11+x12+x13=Q1;

    x21+x22+x23=Q2;

    x31+x32+x33=Q3ф;
    x11+x21+x31=V1;

    x12+x22+x32=V2;

    x13+x23+x33=V3;

    Итак, окончательная постановка задачи выглядит следующим образом: минимизировать

    у==2х11+1,5x12+4х13x21+2х22+1x23;

    при ограничениях

    x11+x12+x13=Q1;

    x21+x22+x23=Q2;

    x31+x32+x33=Q3;
    x11+x21+x31=V1;

    x12+x22+x32=V2;

    x13+x23+x33=V3; (5.17)
    xij0 для всех значений i и j. Аналогично ставятся другие транспортные задачи.

    5.4.3.3. Алгебраическое решение задачи методом потенциалов.

    Алгоритм решения транспортной задачи методом потенциалов включает в себя следующую последовательность шагов:

    1) нахождение начального допустимого решения;

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

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

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

    Первый шаг алгоритма метода потенциалов – первая итерация. Более компактно транспортная модель представляется в виде так называемой транспортной таблицы, имеющей вид матрицы, в которой строки соответствуют исходным пунктам – лесосеки, а столбцы – пунктам потребления – погрузочные пункты. Коэффициенты себестоимости или затрат, руб./м3, располагаются в правом верхнем углу каждой клетки, i, j. На пересечении соответствующих строк и столбцов в клетках показываются объемы транспортировки, не противоречащие поставленным ограничениям.

    Базисными переменными в транспортной таблице считаются те, которым присвоено какое-либо значение объема транспортировки. Поставленная транспортная задача имеет т+(n-1) независимых уравнений, и начальное допустимое решение должно иметь т+(n-1) базисных переменных. Сущность начального допустимого решения заключается в том, что необходимо получить такое допустимое распределение объемов транспортировки по маршрутам, при котором удовлетворялись бы поставленные ограничения. Иначе, сумма всех объемов по строкам и столбцам равнялась бы объемам заготовки соответствующих лесосек и объемам потребления (вместимости) соответствующих погрузочных пунктов.

    Для нахождения начального базисного допустимого решения используется процедура, основанная на правиле северо-западного угла (известен также метод минимальной стоимости по принципу первоначального распределения объемов по маршрутам, имеющим минимальную себестоимость в порядке ее возрастания). На основе правила северо-западного угла объемы трелевки по маршрутам распределяются так, чтобы они удовлетворяли поставленным ограничениям, т. е. были бы допустимыми. Следуя этому правилу переменной х11, расположенной в северо-западном углу таблицы, приписывается максимальное значение, допустимое ограничением на отгрузку Q1 или потребление V1. После этого вычеркивается соответствующий столбец или строка, для которого дальнейшее заполнение остальных клеток недопустимо по поставленному ограничению. Эта операция фиксирует тот факт, что остальные переменные вычеркнутого столбца равны нулю. Если ограничение выполняется одновременно для столбца и строки, то вычеркивается произвольно либо строка, либо столбец. Оставшийся объем распределяется на следующие клетки не вычеркнутых либо строки, либо столбца и так далее, до тех пор, пока не останется не вычеркнутой одна строка (столбец).

    рис520.jpg

    Рис. 5.20. Начальное допустимое решение

    Процесс получения начального допустимого решения в целом выглядит следующим образом (в последовательности перехода и назначения объемов в 1 м3 по маршрутам от переменной к переменной). Из того, что модель предварительно была сбалансирована, Q=V, то отсюда следует, что одно уравнение является зависимым и транспортная модель содержит m+(n-1) (3+3-1=5) независимых уравнений и начальное базисное допустимое решение должно иметь 5 базисных переменных. Для нахождения начального базисного допустимого решения используем процедуру, основанную на правиле северо-западного угла

    Базисные переменные (рис. 5.20) принимают значения x11=200=>х12=50=>x22=100=>х23=50=>х33=50, остальные небазисные переменные равняются нулю. В реальности данный план означает, что необходимо производить трелевку в указанных объемах, соответственно, из первой лесосеки на первый погрузочный пункт, из первой во второй, из второй во второй, из второй в третий, из третьей в третий. Для полученного плана затраты на трелевку составляют 200•2 + 50•1,5 + 100•2 + 50•1 + 50•0=735 руб. в смену.

    Оптимален ли этот план? На этот вопрос дает ответ условие оптимальности симплекс-метода (см. разд. 5.3.8, наличие положительных коэффициентов при небазисных переменных транспортной таблицы).

    Второй шаг алгоритма – нахождение включаемой в базис переменной на основе метода потенциалов. В методе потенциалов строке i и столбцу j транспортной таблицы ставятся в соответствие числа и vj. Для каждой базисной переменной xij текущего решения потенциалы и vj должны удовлетворять уравнению +vj=cij. Количество таких уравнений, соответствующих базисным переменным, в виде системы т+п-1, и в этой системе (т+п) неизвестных. Если количество уравнений, соответствующих базисным переменным, менее чем т+п-1 (например, т+п-2), то для успешной реализации данного шага алгоритма за базисную принимается любая небазисная переменная, наиболее удобная для последующего построения цикла. Значения потенциалов можно определить из системы, придавая одному их них произвольное значение (обычно полагается j=0). Затем решается система из т+п-1 уравнений относительно т+п-1 остальных потенциалов. Оценки для небазисных переменных хpq определяются после получения решения для базисных переменных в соответствии с соотношением Сpq=ир+vq- (величины Сpq не зависят от выбора значения иi).

    В дальнейшем на основе Сpq для включения в базис выбирается небазисная переменная, имеющая наибольшее положительное значение Сpq(сравните с условием оптимальности симплекс-метода при решении задачи на отыскание минимума – в качестве включаемой в базис переменной выбирается та, при которой коэффициент в уравнении функции цели имеет наибольшее положительное значение). Используем рассмотренный метод к условиям поставленной нами задачи (см. рис. 5.21):

    x11: u1+v1=c11=2;

    x12: u1+v2=c12=1,5;

    x22: u2+v2=c22=2;

    x23:u2+v3=c23=1;

    x33:u3+v3=c33=0.

    Полагая иi=0, получим v1=2; v2=1,5; и2=0,5; v3=0,5; u3=-0,5. Оценки потенциалов для небазисных переменных:

    x13: C13=u1+v3-c13=0+0,5-4=-3,5

    x21: C21=u2+v1-c23=0,5+2-3=-0,5

    x31: C13=u3+v1-c31=-0,5+2-0=1,5

    x21: C32=u3+v2-c32=-0,5+1,5-0=1

    В соответствии с условием оптимальности небазисная переменная х31 (выделена подчеркиванием в тексте и штриховкой на рис. 5.21), имеющая максимальную положительную оценку С31, принимается в качестве включаемой в базис.

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

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

    Правила построения цикла следующие: 1) цикл начинается и заканчивается включаемой в базис небазисной переменной; 2) он состоит из последовательности горизонтальных и вертикальных (связанных) отрезков, концами которых должны быть базисные переменные, за исключением тех концов, которые относятся к включаемой в базис переменной; 3) количество всех переменных, охваченных циклом, должно быть четным; 4) при построении цикла не существенно, в каком направлении – против или по часовой стрелке – происходит обход цикла.

    рис521.jpg

    Рис. 5.21. Второй и третий шаги первой итерации

    Рассмотрим иллюстрацию цикла на нашем примере. Последовательность обхода и построения цикла согласно изложенным правилам следующая: x31=>x11=>x12=>x22=>x23=>x33=>x31

    Если значение (см. рис. 5.21) вводимой в базис переменной x31 увеличивается на какую-либо величину, то для сохранения допустимости решения значения базисных переменных, стоящих на изломах рассматриваемого цикла, необходимо скорректировать следующим образом: уменьшить х11 на эту величину, увеличить x12 на эту величину, уменьшить x22 на эту величину и т. д. в соответствии со знаками “-“(уменьшить) и "+"(увеличить), расставленными в соответствующих клетках таблицы. При подобном перераспределении объемов трелевки по маршрутам не будут нарушаться ограничения задачи на объемы заготовленной древесины с лесосек и объемы вместимости на погрузочных пунктах.

    Переменная, исключаемая из базиса, выбирается из находящихся на изломах цикла переменных, значения которых уменьшаются при увеличении x31. Они располагаются в таблице на местах, отмеченных знаком "-", это – x11, x22, x33. Выводимой из базиса становится та, которая имеет наименьшее значение, поскольку именно она раньше всех достигает нуля, и любое дальнейшее уменьшение делает ее отрицательной (сравните с условием допустимости симплекс-метода, где исключаемая переменная определяется минимальным соотношением, здесь знаменатель равен 1). В нашем случае минимальна х33=50, тогда значение x31=50; х11=150; х12=100; х22=50; х23=100, и транспортная таблица принимает вид, представленный на рис. 5.22.

    Суммарные затраты на трелевку (функция цели) для полученного плана равняются у=150•2+100•1,5 +50•2+100•1+50•0=650 руб.

    Оптимальность нового решения определяется вычислением новых потенциалов:

    x11: u1+v1=2;

    x12: u1+v2=1,5;

    x22: u2+v2=2;

    x23: u2+v3=1;

    x31:u3+v1=0.

    Полагая u1=0, получим v1=2; v2=1,5; u2=0,5; v3=0,5; u3=-2. Оценки потенциалов для небазисных переменных:

    x13: C13=u1+v3-c13=0+0,5-4=-3,5

    x21: C21=u2+v1-c21=0,5+2-3=-0,5

    x32: C32=u3+v2-c32=-2+1,5-0=-0,5

    x33: C33=u3+v3-c33=-2+0,5-0=-1,5

    рис522.jpg

    Рис. 5.22. Оптимальное решение

    В соответствии с условием оптимальности можно сделать вывод о достижении оптимального решения. Полученный план трелевки древесины обеспечит минимальные затраты. При этом сменные маршруты и соответствующие объемы трелевки примут следующий вид (рис. 5.22): 150 м3 – по маршруту с первой лесосеки на первый погрузочный пункт; 100 м3 – по маршруту с первой лесосеки на второй погрузочный пункт; 50 м3 – по маршруту со второй лесосеки на второй погрузочный пункт; 100 м3 – со второй лесосеки на третий погрузочный пункт. И недостающие 50 м3 (фиктивные) – по маршруту с третьей фиктивной лесосеки на первый погрузочный пункт. Суммарные затраты (себестоимость) на трелевку при этом плане составят 650 рублей.
    5.4.3. КОМПЬЮТЕРНОЕ РЕШЕНИЕ ПОСТАВЛЕННОЙ ЗАДАЧИ В МАТЕМАТИЧЕСКИХ ПРОГРАММНЫХ СРЕДАХ
    Компьютерное решение транспортных задач в сфере лесозаготовок, в частности разработки рациональных планов транспортировки круглых лесоматериалов и трелевки хлыстов, включает в себя следующие этапы: выбор соответствующей программной среды; ввод и редактирование поставленной задачи; получение оптимального решения; проведение задачи анализа на чувствительность.

    Рассмотрим использование среды Excel для решения поставленной задачи оптимизации плана трелевки хлыстов. Подробно с методикой постановок и решения задач оптимизации в программных средах, а также с правилами использования этих сред можно ознакомиться в 5.3.9. Пример решения задачи оптимизации плана трелевки хлыстов представлен на рис. 5.23 – 5.24. Рис. 5.23 отображает начальную постановку задачи в табличной форме и открытое окно диалога «Поиск решения».

    Содержание ячеек таблицы постановки задачи (рис. 5.23) представлено следующей информацией:

    1) ячейки строк Al-A11, В1-В2,С1-С2, F1-F2, G1-G2 и столбцы D, Е1-E11 содержат текстовую поясняющую информацию;

    2) ячейки ВЗ-В11 содержат начальные значения объемов трелевки по всем возможным маршрутам (приняты равными нулю), которые в процессе поиска решения будут изменяться и в конечном итоге примут оптимальные значения;

    3) ячейки СЗ-С11 содержат, соответственно, значения затрат на трелевку 1 м3 по каждому из возможных маршрутов и имеют постоянные значения;

    4) ячейки F3-F8 определяют текущие значения объема трелевки с i-й лесосеки, i=, на все j-е погрузочные пункты и объема потребления (вместимости) j-го, j=, погрузочного пункта со всех i-х лесосек в соответствии с выражениями (5.17) (F3=ВЗ+В4+В5; F4=В6+В7+В8; F5=В9+В10+В11; F6=ВЗ+В6+В9; F7=В4+В7+В10; F8=В5+В8+В11);

    5) ячейка F9 содержит минимальную из сумм, получаемых в процессе поиска решения, по объемам заготовки на лесосеках или по объемам вместимости погрузочных пунктов (=MИH(CУMM(F3:F5); CУMM(F6:F8))), ячейка F10 содержит величину фиктивного объема;

    рис523.jpg

    Рис. 5.23. Исходная постановка транспортной задачи в Excel

    6)ячейка F11 определяется выражением (5.17) функции цели (=СУММ(СЗ*ВЗ; С4*B4; С5*В5; С6*В6; С7*В7; С8*В8)), которая в конечном итоге при поиске оптимального решения принимает минимальное значение;

    7)ячейки G3-G9 содержат предельные постоянные значения ограничений по заготовке древесины на соответствующих лесосеках и вместимости соответствующих погрузочных пунктов.

    В окне Поиск решения указаны ячейка $F$11, содержащая функцию цели, ячейки (переменные) $В$3:$В$11, подлежащие изменению в процессе поиска решения и ограничения в соответствии с постановкой (5.17).

    Содержание ячеек таблицы оптимального решения задачи (рис. 5.24) представлено следующей информацией:

    1) ячейки строк А1-А11, В1-В2, С1-С2, F1-F2, G1-G2 и столбцы D, E1-E11 содержат текстовую поясняющую информацию;

    2) ячейки ВЗ-В11 содержат конечные, оптимально распределенные, значения объемов трелевки по всем возможным маршрутам;

    3) ячейки СЗ-С11 содержат, соответственно, значения затрат на трелевку 1 м3 по каждому из возможных маршрутов и имеют постоянные значения;

    4) ячейки F3-F8 содержат оптимальное решение значений объема трелевки с i-й лесосеки, i=, на все j-е погрузочные пункты и объема потребления (вместимости) j-го, j=, погрузочного пункта со всех i-х лесосек;

    5) ячейка F11 содержит минимальное значение суммы себестоимостей по всем маршрутам, определенным в оптимальном решении.

    Сопоставление компьютерного и алгебраического решения поставленной задачи методом потенциалов определяет их полное совпадение.

    рис524.jpg

    Рис. 5.24. Результаты оптимального решения транспортной задачи в Excel


    УПРАЖНЕНИЯ

    К разделам 5.4.1, 5.4.2.2

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

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

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

    Разработайте математическую модель и поставьте задачу оптимизации по содержательному описанию из упражнения к разд. 5.4.1, 5.4.2.2
    К разделу 5.4.2.3

    Выполните решение поставленной задачи алгебраически на основе метода потенциалов. Сравните результаты алгебраического и эвристического решений на предмет проверки Вашего эвристического выбора. Оцените свой выбор и свои априорные – методом потенциалов – инженерные умения и навыки на основе проведенного сравнения.
    ВОПРОСЫ ДЛЯ САМОПРОВЕРКИ
    1. Какие задачи лесозаготовительного комплекса могут быть решены на основе транспортной задачи?

    2. Что означает понятие "сбалансированная транспортная задача"?

    3. Какова последовательность разработки модели и постановки транспортной задачи оптимизации?

    4. Что является критерием при оптимизации объемов транспортировки круглых лесоматериалов из лесопромышленных складов потребителям – трелевки хлыстов с лесосек на погрузочные пункты? Какие еще критерии Вы могли бы использовать при постановке подобных задач?

    5. Перечислите шаги алгоритма метода потенциалов.

    6. К какому объекту лесозаготовок на предприятии – месте прохождения производственной практики – Вы могли бы применить подобный оптимизационный подход?



    написать администратору сайта