Клетки, которые содержат нулевые перевозки (хi, j = 0), называют свободными, а ненулевые — занятыми (xi, j >0).
По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного, удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины текущих нераспределенных запасов обозначаются аi (q), а текущих неудовлетворенных потребностей — bj (q). Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем аi (0) = аi, bj (0) = bj. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: xi, j = min{аi (q), bj (q)}. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:
(22)
Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: аi (q+1) = 0 или bj (q+1) = 0. Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i +1, т. е. переместиться к следующей клетке вниз по столбцу. Если же bj (q+1) = 0, то значит, полностью удовлетворена потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции.
Основываясь на условии баланса запасов и потребностей, нетрудно доказать, что за конечное число шагов мы получим допустимый план. В силу того же условия число шагов алгоритма не может быть больше, чем m+n-1, поэтому всегда останутся свободными (нулевыми) mn-(m+n-1) клеток. Следовательно, полученный план является базисным. Не исключено, что на некотором промежуточном шаге текущий нераспределенный запас оказывается равным текущей неудовлетворенной потребности (аi (q) = bj (q)). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана.
Рисунок. 2 Рисунок. 3
Рассмотрим применение метода северо-западного угла на конкретном примере. Транспортная таблица (рис. 2) содержит условия некоторой задачи, а в (рис. 3) показан процесс поиска допустимого плана, включая последовательное изменение объема нераспределенных запасов и неудовлетворенных потребностей. Стрелки отражают траекторию перехода по клеткам транспортной таблицы, а цифры, находящиеся за ее пределами, — текущие нераспределенные остатки после назначения объема для очередной клетки.
Особенностью допустимого плана, построенного методом северо-западного угла, является то, что целевая функция на нем принимает значение, как правило, далекое от оптимального. Это происходит потому, что при его построении никак не учитываются значения сi, j. В связи с этим на практике для получения исходного плана используется другой способ — метод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наименьшими ценами.
Использование транспортной задачи для построения оптимального плана доставки товаров потребителям
. Из трех пунктов хранения (или производства) требуется доставить однородный груз в пять пунктов потребления. Количество груза ai в каждом пункте отправления, объемы потребления bj, а также стоимости cij перевозки единицы груза из пункта отправления i в пункт потребления j указаны в таблице.
Составить такой план перевозок, при котором общая стоимость перевозок была бы минимальной.
Все данные нашей задачи сведем в табл. 1.
Таблица 1 — Исходные данные
bj
ai 170 190 140 180 120 160 3 13 14 18 14 400 25 14 7 5 16 340 11 4 10 18 9
Решим транспортную задачу с помощью метода потенциалов.
1. Проверим, является ли данная задача закрытой.
Задача открытая. Вводим «фиктивный» пункт потребления объемом в 100 ед. Стоимость перевозок в этот пункт принимает равным 0.
Таблица 2 — Ввод фиктивного пункта потребления
bj
ai 170 190 140 180 120 160 3 13 14 18 14 0 400 25 14 7 5 16 0 340 11 4 10 18 9 0
Находим первый план задачи методом, например, наименьшего элемента матрицы транспортных издержек (последний столбец при этом не принимаем во внимание, т.к. он связан с фиктивным пунктом потребления). Т.к., то удовлетворяем запрос первого потребителя: х13 = 160 заносим в таблицу. И т.д.
Таблица 3 — Базисный план
bj
ai 170 190 140 180 120 160 160 400 140 180 80 340 10 190 120 20 Опорный план должен занимать m + n — 1 = 3 + 6 — 1 = 8 клеток.
F=4310
Проверим, не является ли найденный план оптимальным? Для оптимального плана сумма потенциалов для занятых клеток, а для свободных, т. е.. Вычислим потенциалы, исходя из соотношений для занятых клеток. Результаты вычислений заносим в седьмой столбец () и четвертую строку () таблицы.
Таблица 4 — Расчет потенциалов
bj
ai 170 190 140 180 120 160 3
160 13 14 18 14 0 3 400 25 14 7
140 5
180 16 0
80 11 340 11
10 4
190 10 18 9
120 0
20 11 0 -7 -4 -6 -2 -11 Выполняется ли второе требование критерия оптимальности метода потенциалов? Вычисляем для всех свободных клеток разность и клетки, для которых эта разность положительна, помечаем знаком плюс, отрицательные разности заносим в соответствующие клетки.
Таблица 5 — Сравнение потенциалов с ценой перевозки
bj
ai 170 190 140 180 120 160 3
160 13
+ 14
+ 18
+ 14
+ 0
+ 3 400 25
+ 14
+ 7
140 5
180 16
+ 0
80 11 340 11
10 4
190 10
+ 18
+ 9
120 0
20 11 0 -7 -4 -6 -2 -11 Все потенциалы положительные, план оптимален.
Заключение
Математическое моделирование, некогда бывшее «terra incognita» для широких инженерных (и не только инженерных) слоев, за последние десятилетия резко изменилось. Произошел качественный скачок в разработке моделей, их верификации, в создании и использовании модельно-обоснованных методов исследования, в способах анализа и представления результатов моделирования.
Академическое понимание и узкопрофессиональное использование методов моделирования уступает место широкому наступлению имитационных моделей в самых разных областях компьютеризации общества.
Методы экономико-математического моделирования, возможности применения которых существенно расширились благодаря современному программному обеспечению ПЭВМ, представляют собой один из наиболее динамично развивающихся разделов прикладной экономической науки.
Современный маркетолог должен хорошо разбираться в экономико-математических методах, уметь их практически применять для моделирования реальных маркетинговых ситуаций. Это позволит лучше усвоить теоретические вопросы современной экономики, повысить уровень квалификации и общей профессиональной культуры специалиста.
Сделалось возможным применять экономико-математические модели и в маркетинговой деятельности предприятия.
Особенной трудностью в данном процессе является подбор информации и формализация модели, так как маркетинговая деятельность предприятия разнообразна, на нее влияет большое количество факторов, поэтому приходится зачастую абстрагироваться от многих из них, поэтому результаты полученные в процессе моделирования необходимо производить проверку адекватности полученных результатов.
Список литературы
Акулич И. Л. Математическое программирование с примерах и задачах. М.: Высшая школа, 2005
Гибкое развитие предприятий: эффективность и бюджетирование. М.: Дело, 2000
Гранберг А. Г. Математические модели социалистической экономики. М., 2005
Додж М., Кината К., Стинсон К. Excel для Windows в 2 т. М.: Русская редакция, 2004
Иванилов Ю.И., Лотов А. В. Математические модели в экономике. М., Наука, 2006
Контуры инновационного развития мировой экономики. Прогноз на 2000;2015 гг.(под ред. Дымкина А.). М.: Наука, 2000
Липсиц И.В., Коссов В. В. Инвестиционный проект. М. Бек, 2006
Львов Д. С. Эффективное управление техническим развитием. М.: Экономика, 2002
Малыхин В. И. Математическое моделирование экономики. М., УРАО, 2003
Математические методы в планировании отраслей и предприятий (под ред. Попова И.Г.). М.: Экономика, 2002
Сахал Д. Технический прогресс: концепции, модели, оценка. М.: Финансы и статистика, 2003
Твисс Б. Управление научно-техническими нововведениями. М.: Экономика, 2005
Форрестер Дж. Мировая динамика. М.: Наука, 2006
Экономические аспекты научно-технического прогнозирования. (под ред. Виленского М.А.) М.: Экономика, 2005
Яковец Ю. В. Закономерности научно-технического прогресса и их планомерное использование. М.: Экономика, 2004
