Скачать

Решение задач о планировании перевозок

Человек всегда моделировал: мысленно, физически, знаками, в том числе математически.

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

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

Этот процесс в последнее время шел интенсивно во всем мире. Появились целые школы математических методов в США, Франции, ФРГ, Англии и некоторых других странах, что вызвано объективными причинами. Расширение масштабов производства, развитие, кооперации, усложнение межхозяйственных связей и другие, качественные Количественные изменения в экономике привели к резкому увеличению числа управленческих решений, из которых надо выбрать лучшее. Методам линейного программирования посвящено много работ зарубежных и прежде всего американских ученых. Основной метод решения задач линейного программирования симплексный метод был опубликован в 1949 г. Данцигом. Дальнейшее развитие метода линейного и нелинейного программирования получили в работах Форда, Фалкерсона, Куна, Лемке, Госса, Чарнеса и др. В настоящее время методы линейного программирования развиваются главным образом в направлении выявления конкретных экономических задач, к решению которых оно может быть применено, а также по пути создания более удобных алгоритмов для решения задач на ЭВМ.

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

Чрезвычайно велико значение экономико-математических методов при принятии плановых заданий. Увеличение «Цены ошибки» в планировании потребовало решения планово-экономических задач на более высоком уровне их научного обоснования, т.е. прежде всего такими методами, которые давали бы наилучший (оптимальный) или рациональный результат.

Постановка задачи

Изготовленный на 5 кирпичных заводах кирпич поступает на место строящихся объектов.

Ежедневное производство кирпича и потребность в нем указаны в таблице. В нем уже указана цена перевозки 1000 шт. кирпича с каждого из заводов каждого из объектов.

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

Характеристика вида программирования

Задачи оптимального планирования, связанные с отысканием оптимума заданной целевой функции (линейной формы) при наличии ограничений в виде линейных уравнений или линейных неравенств относятся к задачам линейного программирования.

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:

математические модели очень большого числа экономических задач линейны относительно искомых переменных;

· эти типы задач в настоящее время наиболее изучены;

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

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

· некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования. Итак, Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием. Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину спроса, производственную мощность предприятия и другие производственные факторы. Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений

· переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи. Система ограничений, определяющая множество планов, диктуется условиями производства. Задачей линейного программирования (ЗЛП) является выбор из множества допустимых планов наиболее выгодного (оптимального).В общей постановке задача линейного программирования выглядит следующим образом:

Имеются какие-то переменные х = (х₁ , х₂ , … х_n ) и функция этих переменных f(x) = f (х₁ , х₂ , … х_n ), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G:

В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что

а) функция f(x) является линейной функцией переменных х₁ , х₂ , … х_n

б) область G определяется системой линейных равенств или неравенств.

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

· максимум или минимум целевой функции (критерий оптимальности);

· систему ограничений в форме линейных уравнений и неравенств;

· требование неотрицательности переменных.

Пример

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

          (2.4)

       (2.5)

(2.6)

Коэффициенты a_i,j, b_i, c_j, j = 1, 2, ... , n, i =1, 2, ... , m – любые действительные числа (возможно 0).

Итак, решения, удовлетворяющие системе ограничений (2.4) условий задачи и требованиям неотрицательности (2.5), называются допустимыми, а решения, удовлетворяющие одновременно и требованиям минимизации (максимализации) (2.6) целевой функции, - оптимальными.

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

В канонической форме задача является задачей на максимум (минимум) некоторой линейной функции F, ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х₁, х₂, ..., х_n являются неотрицательными:

(2.7)

(2.8)

(2.9)

К канонической форме можно преобразовать любую задачу линейного программирования.

Правило приведения ЗЛП к каноническому виду:

1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением в левую часть некоторой неотрицательной переменной, при чем в неравенства «≤» вводится дополнительная не отрицательная переменная со знаком «+»; в случаи неравенства «≥» - со знаком «-»

   (2.10)

Вводим переменную .

Тогда неравенство (2.10) запишется в виде:

   (2.11)

В каждое из неравенств вводится своя “уравнивающая” переменная, после чего система ограничений становится системой уравнений.

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

              , l - свободный индекс

Транспортная задача в матричной постановке и ее свойства

Данная задача сводится к определению такого плана перевозок некоторого продукта из пунктов его производства в пункты потребления (||x_i,j||_mxn), который минимизирует целевую функцию

 на множестве допустимых планов

 при соблюдении условия баланса

Если привести условия транспортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (m+)mn. Матрицы систем уравнений в ограничениях имеют ранги, равные соответственно m и. Однако, если, с одной стороны, просуммировать уравнения по m, а с другой — уравнения по n, то получим одно и то же значение. Из этого следует, что одно из уравнений в системе является линейной комбинацией других. Таким образом, ранг матрицы транспортной задачи равен m+ -1, и ее невырожденный базисный план должен содержать m+ -1 ненулевых компонент.

Процесс решения транспортной задачи удобно оформлять в виде последовательности таблиц. Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта a_i), а столбцы — пунктам потребления (последняя клетка каждого столбца содержит значение потребности b_j). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (x_i,j=0), называют свободными, а ненулевые — занятыми (x_i,j>0).

C_1,1            C_1,2               ……        C_1,n

X_1,1            X_1,2               ……        X_1,n      A₁

C_2,1            C_2,2               ……        C_2,n

X_2,1            X_2,2               ……        X_2,n      A₂

….             ….                ….           ….       ….

C_m,1           C_m,2              ……        C_m,n

X_m,1           X_m,2              ……        X_m,n     A_m

B₁              B₂                 ….           B_n

Построение исходного допустимого плана в транспортной задаче

По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины текущих нераспределенных запасов обозначаются а_i^(q), а текущих неудовлетворенных потребностей — b_j^(q). Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем а_i⁽⁰⁾= а_i, b_j⁽⁰⁾= b_j. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: х_i,j=min{а_i^(q),b_j^(q)}. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:

а_i^(q+1)= а_i^(q) - x_i,j, b_j^(q+1)= b_j^(q) - x_i,j

Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: а_i^(q+1)=0 или b_j^(q+1)= 0. Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i+1, т. е. переместиться к следующей клетке вниз по столбцу. Если же b_j^(q+1)= 0, то значит, полностью удовлетворена потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции.

Основываясь на условии баланса запасов и потребностей, нетрудно доказать, что за конечное число шагов мы получим допустимый план. В силу того же условия число шагов алгоритма не может быть больше, чем m+-1, поэтому всегда останутся свободными (нулевыми) mn-(m+-1) клеток. Следовательно, полученный план является базисным. Не исключено, что на некотором промежуточном шаге текущий нераспределенный запас оказывается равным текущей неудовлетворенной потребности (а_i^(q)=b_j^(q)). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана.

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

Несбалансированная задача

Если сумма единиц товара поставщиков не равна сумме единиц товара потребителей, то задача не сбалансированная (открытая), иначе задача сбалансированная (закрытая).

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

Алгоритм метода потенциалов для транспортной задачи

Алгоритм начинается с выбора некоторого допустимого базисного плана (первоначальный план перевозок, составленный, например, методом северо-западного угла). Если данный план не вырожденный, то он содержит m+-1 ненулевых базисных клеток, и по нему можно так определить потенциалыu_i и v_j, чтобы для каждой базисной клетки (т. е. для той, в которой x_i,j> 0) выполнялось условие v_j-u_i=c_i,j, если x_i,j>0

Переменные u_i называют потенциалами пунктов производства, a v_j — потенциалами пунктов потребления.

Для этого составьте систему для заполненных клеток плана перевозок:v_j-u_i=c_i,j; где c_i,j - стоимость перевозки из пункта i в пункт j.

Поскольку система содержит m+-1 уравнение и m+ неизвестных, то один из потенциалов можно задать произвольно. После этого остальные неизвестные v_j и u_i - определяются однозначно.

Критерий оптимальности

Для того чтобы допустимый план транспортной задачи x_i,j был оптимальным, необходимо и достаточно, чтобы нашлись такие потенциалы u_i, v_j, для которых

v_j-u_i=c_i,j, если x_i,j>0,

v_j-u_i≤c_i,j, если x_i,j=0

Вычислите коэффициенты изменения стоимости (dc_i,j) для незаполненных клеток плана: dc_i,j = v_j- u_i - c_i,j

Заметьте: если все dc_i,j оказались отрицательными, то полученный план оптимальный. Если есть хотя бы один положительный элемент dc_i,j, то далее ведущей (опорной) клеткой будет клетка (i,j) (при dc_i,j>0).

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

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

Решение задачи

1. Определим модель задачи

b1+b2+b3+b4+b5+b6=230+220+130+170+190+110=1050

a1+a2+a3+a4+a5=240+360+180+120+150=1050

Так как Σa_i=Σb_j, то модель задачи является закрытой.

2. Построим распределительную таблицу по методу северо-западного угла.

                V1=8    V2=0    V3=5    V4=2    V5=1    V6=6

               230       220       130       170       190       110

U1=0       240       150                   90                      

U2=5       360       80                                 170       110     

U3=4       180                   180                                

U4=6       120                   40                                 80       

U5=9       150                               40                       110

3.Определяем целевую функцию Z для первого этапа по формуле

Z= ΣC_ij*X_ij

Z1=90*5+150*8+80*13+170*7+110*6+180*4+40*6+80*7+40*14+110*15=8270

4.Определим потенциалы для заданных клеток, где U1=0 по формуле

U_i+V_j=C_ij

5.определим оценки свободных клеток, исходя из условия:

Δ_ij=C_ij-( U_i+V_j)

Δ₁₂=7 Δ₃₅=5

Δ₁₄=8 Δ₃₆=1

Δ₁₅=11 Δ₄₁=0

Δ₁₆=2 Δ₄₃=1

Δ₂₂=3 Δ₄₄=5

Δ₂₃=0 Δ₄₆=2

Δ₂₆=2 Δ₅₁=-8

Δ₃₁=0 Δ₅₂=3

Δ₃₃=2 Δ₅₄=4

Δ₃₄=3 Δ₅₅=-2

Т.к среди оценок свободных клеток есть отрицательная оценка Δ₅₁=-8 то решение является не оптимальным, значит, продолжаем решение задачи.

6.Для перехода к следующей итерации строим цикл по λ=min|X_ij| по четным клеткам λ=min|150;40|=40

7.Определим целевую функцию для второго этапа

Z2=Z-λ|X_ij|=8270-40*8=7950

                V1=8    V2=0    V3=5    V4=2    V5=1    V6=14

               230       220       130       170       190       110

U1=0       240       110                   130                    

U2=5       360       80                                 170       110     

U3=4       180                   180                                

U4=6       120                   40                                 80       

U5=1       150       40                                               110

Экономическая интерпретация

Для достижения минимальной стоимости перевозок в размере 7210 ед. кирпича следует перевозить следующим образом:

1. От первого кирпичного завода кирпич в количестве 80 ед. был перевезен к первому строящемуся объекту. В количестве 130 ед. был перевезен к третьему строящемуся объекту. В количестве 30 ед. был перевезен к шестому строящемуся объекту.

2. От второго кирпичного завода кирпич в количестве 170 ед. был перевезен к четвертому строящемуся объекту. В количестве 190 ед. был перевезен к пятому строящемуся объекту.

3. От первого кирпичного завода кирпич в количестве 100 ед. был перевезен ко второму строящемуся объекту. В количестве 80 ед. был перевезен к шестому строящемуся объекту.

4. От четвертого кирпичного завода кирпич в количестве 120 ед. был перевезен ко второму строящемуся объекту.

5. От пятого кирпичного завода кирпич в количестве 150 ед. был перевезен к первому строящемуся объекту.

Характеристика программы оптимизации

Для вызова программы оптимизатора необходимо выбрать команду меню Сервис→Поиск решения. Если команда Поиска решения отсутствует в меню Сервис, то надо установить эту настройку.

Для установки программы Поиск решения необходимо в меню Сервис выбрать команду Настройки. Далее в диалоговом окне Настройки необходимо установить флажок Поиск решения. Надстройка, останется активной до тех пор, пока она не будет удалена.

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

Окно Поиск решения вызывается командой меню Сервис→Поиск решения.

Поле «Установить целевую ячейку» служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу.

Кнопка «Равной» служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор заданного числа). Чтобы установить заданное число необходимо ввести его в поле.

Поле «Изменяя ячейки» служит для указания ячеек, значение которого изменяется в процессе Поиска решения до тех пор, пока не будут выполняться наложенные ограничения и условия оптимизации значения ячейки вводятся имена или адреса изменяемых ячеек, разделяя их запятыми, Изменяемые ячейки должны быть прямо или косвенно связаны с целевой ячейкой. Допускается установка до 200 изменяемых ячеек.

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

Поле «Ограничения» служит для отображения списка граничных условий поставленной задачи. Команда Добавить служит для отображения диалогового окна Добавить ограничения.

Команда «Изменить» служит для отображения диалогового окна Изменение ограничения.

Команда «Удалить» служит для снятия указанного курсором ограничения.

Команда «Выполнить» служит для запроса поиска решения поставленной задачи.

Команда «Закрыть» служит для выхода из окна диалога без запуска поиска решения поставленной задачи. При этом сохраняются установки, сделанные в окнах диалога, появлявшихся после нажатий на кнопки «Параметры», «Добавить», «Изменить» или «Удалить».

Команда «Параметры» служит для отображения диалогового окна Параметры поиска решения, в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения.

Кнопка «Восстановить» служит для очистки полей окна диалогового и восстановления значений параметров поиска решения, используемых по умолчанию.

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

1. В меню Сервис выбрать команду Поиск решения

2. Нажать кнопку «Параметры».

3. Нажать кнопку «Сохранить модель». Появится окно сохранить модель.

4. В поле «Задайте область модели» введите ссылку на верхнюю ячейку столбца, в котором нужно разместить модель оптимизации.

Значение элементов управления диалоговых окон «Поиска решения» и «Параметры» поиска решения записываются на лист. Чтобы использовать на листе несколько моделей оптимизации, нужно сохранить их в разных диапазонах.

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

Диалоговое окно «Загрузить модель» используется для задания ссылки на область загружаемой модели оптимизации. Ссылка должна адресовать область модели целиком, недостаточно указывать только первую ячейку.

Для запуска оптимизатора нужно нажать на кнопку «Выполнить» в окне «Поиск решения».

Чтобы прервать поиск решения, нужно нажать клавишу Esc.

Инструкция по выполнению

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

1. Создать исходную таблицу.

2. В меню Сервис выбрать команду Поиск решения.

3. Откроется диалоговое окно «Поиск решения».

4. В поле «Установить целевую ячейку» выбрать ячейку В18.

5. В поле «Равной» нажимать на кнопку минимальному значению.

6. В поле «Изменяя ячейки» ввести имена или адреса изменяемых ячеек, разделяя их запятыми. В моем примере введен диапазон ячеек $C$4; $E$7, содержащий искомые величины плана производства продукции. Изменение ячеек должна быть прямо или косвенно связана с целевой ячейкой.

7. Поле «Ограничения» служит для отображения списка граничных условий поставленной задачи. В исходной задаче это следующее ограничение.

1) $В$4:$В$7>=$В$13:$В$16 - количество перевозимой продукции не может превышать производственных возможностей филиалов.

2) $С$11:$Е$11>=$С$9:$Е$9 – количество доставляемой продукции не должна быть меньше потребностей потребителей.

3) $С$4:$Е$7>=0 – число перевозок не может быть отрицательным.

8. Далее необходимо сохранить модель. Для этого:

а) В меню Сервис выбрать команду Поиск решения

б) Нажать кнопку параметры.

в) В поле «Задайте область модели» ввести ячейку столбца, в котором хотим разместить модель оптимизации.

9. В окне «Параметры поиска решения» нажать на кнопку ОК. А в окне «Поиск решения» щелкнуть по кнопке Выполнить, чтобы получить решение данной задачи.

10. После чего появится окно «Результаты поиска решения». В этом окне будет написано «Решение найдено». Все ограничения и условия оптимальности выполнены, нажав на кнопку «Сохранить найденное решение». Закрыть данное окно при помощи кнопки ОК.