Problems of transport type, optimizing problems, computer mathematical modeling компьютерное математическое моделирование оптимизационных задач транспортного типа широкова Ольга Александровна

COMPUTER MATHEMATICAL MODELLING OF OPTIMISING PROBLEMS OF TRANSPORT TYPE Shirokova Olga A. Kazan Federal University , Olga.Shirokova@ksu.ru, OShirokova@mail.ru In the paper the technology of construction of computer models of optimizing problems of transport type in MS Excel is considered and the analysis of various practical situations is carried out. Problems of transport type, optimizing problems, computer mathematical modeling КОМПЬЮТЕРНОЕ МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ ТРАНСПОРТНОГО ТИПА Широкова Ольга Александровна Казанский (Приволжский) федеральный университет Olga.Shirokova@ksu.ru, OShirokova@mail.ru В работе рассматривается технология построения компьютерных моделей оптимизационных задач транспортного типа в MS Excel и проводится анализ различных практических ситуаций. Задачи транспортного типа, оптимизационные задачи, компьютерное математическое моделирование В курсе компьютерного математического моделирования важное значение имеет выработка практических навыков проведения компьютерного эксперимента. На примере ряда моделей из различных областей науки и практической деятельности необходимо проследить все этапы компьютерного моделирования, начиная с исследования моделируемой предметной области и постановки задачи до интерпретации результатов. Рассмотрим технологию построения компьютерных моделей оптимизационных задач транспортного типа в MS Excel, сместив акценты с собственно нахождения оптимального решения на исследование построенной модели. Такое исследование является очень важным при подготовке студентов к аналитической деятельности. Оптимизационные модели транспортного типа [1,2] используются для составления наиболее экономичных планов перевозки продукции из нескольких пунктов отправления в несколько пунктов назначения. Транспортную модель можно также применять и при рассмотрении ряда других практических ситуаций, связанных с управлением запасами, составлением сменных графиков, назначением исполнителей на рабочие места и др. Кроме того, транспортную модель можно видоизменять, чтобы она учитывала перевозку нескольких видов продукции. Широкое практическое приложение транспортной задачи обусловило ее обязательное рассмотрение в курсе компьютерного моделирования. На занятиях необходимо уделить внимание вопросам разработки компьютерной модели задачи и последующего анализа различных практических ситуаций. Постановка задачи. Фирмой разрабатывается план обеспечения потребителей горюче-смазочными материалами (ГСМ). Исходные данные о запасах ГСМ в хранилищах, заявках на ГСМ в центрах распределения и стоимости перевозки 1 т ГСМ от хранилищ к центрам распределения (матрица стоимости) представлены в нижеследующей таблице. Рис. 1 Требуется разработать такой план доставки ГСМ от хранилищ к центрам распределения, чтобы общая стоимость перевозок была минимальной. Математическая модель задачи. Рассматриваемая задача является транспортной задачей закрытого типа, другими словами, сбалансированной транспортной задачей. Последнее название отражает условие сбалансированности запасов и потребностей, имеющееся в рассматриваемой задаче, т. е. (1) где т — количество исходных пунктов (в рассматриваемой задаче количество хранилищ); п — количество пунктов назначения (в рассматриваемой задаче количество центров распределения); а, — количество (объем ) груза в i-м исходном пункте; bj — количество (объем) груза, которое должно быть завезено в j-й пункт назначения. Для рассматриваемой задачи имеем: Таким образом, она является сбалансированной. Так как запасы равны потребностям, то все запасы будут вывезены, а все потребности будут удовлетворены. Данные условия можно записать в виде следующих уравнений: (2) (3) где— искомые переменные задачи — количество (объем) груза, которое должно быть перевезено с i-го исходного пункта в j-й пункт назначения. Так как количество перевозимого груза не может принимать отрицательные значения, то в рассматриваемой задаче имеет место условие неотрицательности, т. е.: (4) Выражения (2)—(4) образуют систему ограничений задачи, целевая функция в которой задается выражением: (5) где — стоимость перевозки одной единицы груза (в рассматриваемой задаче 1 т ГСМ) с i-ro исходного пункта в j-й пункт назначения. — коэффициенты матрицы стоимости, заданной в условии задачи (рис. 1). Экономическая интерпретация выражения (5) становится ясной, если его записать в развернутом виде: (6) Так как — это стоимость перевозки одной единицы груза с i-го исходного пункта в j-й пункт назначения, — объем перевозимого груза по данному маршруту, то — это стоимость перевозки груза по маршруту «i-й исходный пункт —j-й пункт назначения». Сложение стоимостей перевозок по всем возможным маршрутам образует стоимость общего плана перевозок. Объединяя выражения (2)—(6), получаем модель сбалансированной транспортной задачи: (7.1) (7.2) (7) (7.3) (7.4) Опираясь на общую модель (7), разработаем математическую модель для рассматриваемой задачи. Выражение (7.1) запишется в виде системы следующих уравнений: (8) Выражение (7.2) — в виде системы уравнений: (9) Условие неотрицательности (7.3) будет задано 20 неравенствами следующего вида: (10) Целевая функция (7.4) запишется в виде выражения: (11) Таким образом, математическая модель рассматриваемой задачи разработана, можно переходить к вычислительной модели задачи. Решение задачи в MS Excel. Форма представления вычислительной модели задачи на рабочем листе может быть самой различной [3]. Для рассматриваемой задачи предлагается вычислительная модель, представленная на рис. 2. Представленная вычислительная модель включает в себя две таблицы. Первая таблица содержит матрицу стоимости и служит для ввода и редактирования исходных данных задачи, вторая таблица — для ввода формул и расчета значений, соответствующих оптимальному решению. При этом диапазон B12:F15 отведен для расчета оптимального плана перевозок, а ячейка G19 — для расчета целевой функции. Построение вычислительной модели задачи на рабочем листе состоит в записи выражений (8)—(11) в MS Excel. Поскольку диапазон B12:F15 отведен для расчета оптимального плана перевозок, то ячейка В12 соответствует переменной , ячейка С12 — переменной и т. д. Уравнения (8) записываются в диапазоне G12:I15, а уравнения (9) — в диапазоне B16:F18. Условие неотрицательности (10) зададим позже в диалоговом окне Параметры поиска решения. Для расчета целевой функции отведена ячейка G19. Введем в эту ячейку формулу =СУММПРОИЗВ (B3:F6; B12:F15), которая соответствует математическому выражению (11). Ищем ее минимальное значение. Рис. 2 Таким образом, вычислительная модель задачи на рабочем листе разработана. Переходимм к решению задачи в диалоговом окне Поиск решения. В диалоговом окне Параметры поиска решения активизируем флажки Линейная модель и Неотрицательные значения и получим решение задачи (рис. 3). Рис. 3 План перевозок, рассчитанный в ячейках B12:F15, является оптимальным. При данном решении значение целевой функции, рассчитанное в ячейке G19, минимально и равно 4300 у.е. Построенная модель сбалансированной транспортной задачи служит основой для разработки различных модифицированных моделей, учитывающих разнообразные ситуации, возникающие на практике. Рассмотрим некоторые из них. Рис. 4 В практической деятельности встречаются задачи, связанные с блокированием перевозок. Это может быть обусловлено причинами техногенного характера, ремонтными работами (закрытие моста и т. п.). Например, необходимо заблокировать перевозку по маршруту Хранилище 2 — Центр 3. Математически это указание запишется в виде ограничения. При этом в диалоговом окне Поиск решения введем ограничение D13 = 0 (т.е. x23=0). Другим, «искусственным», способом задания блокировки является назначение большой стоимости перевозки блокируемому маршруту в матрице стоимости. Например, для блокировки маршрута Хранилище 3— Центр 1 зададим с31 = 1000, для чего в ячейку В5 матрицы стоимости введем большое число 1000. Решение представлено на рис. 4 Далее рассмотрим схему недопоставки в условиях дефицита. При этом постараемся обеспечить равномерную недопоставку ГСМ во все пять центров. При дефиците в 400 т (400 — 1750 — 1350) она будет составлять 80 т ГСМ для каждого центра. Однако, как легко заметить, такое решение будет несправедливым. Например, недопоставка в 80 т для Центра 2 будет лишь неприятностью, а для Центра 4 —большой проблемой. Отсюда напрашивается пропорциональное распределение ГСМ относительно масштабов (потребностей) центров, что и будет являться справедливым решением. Существуют различные подходы к пропорциональному распределению ресурсов. Рассмотрим два из них [4]. Первый подход состоит в расчете коэффициента обеспеченности Корректировка потребностей осуществляется в соответствии с формулой: , где — новое значение спроса в j-м центре; — старое значение спроса в j-м центре. Второй подход состоит вследующем: вначале определяется доля каждого центра в общем объеме потребностей: Логичным будет в соответствии с этими долями осуществить и недопоставку , где — объем недопоставки в j-й центр, – общий объем недостающих ресурсов (объем дефицита). Корректировка потребностей осуществляется в соответствии с формулой: Выбрав тот или иной способ корректировки потребностей, рассчитаем их новые значения. Все расчеты целесообразно проводить непосредственно на рабочем листе MS Excel. При этом заметим, что задача из несбалансированной вновь превращается в сбалансированную. После внесения необходимых изменений на рабочем листе в диалоговом окне Поиск решения запускаем процедуру поиска. Решение задачи представлено на рис. 5. В рассмотренной задаче транспортировка ГСМ осуществляется в условиях дефицита, т.е. при условии: . Наряду с «дефицитной» постановкой задачи возможна и противоположная ей «избыточная» постановка, т. е. когда выполняется условие . Рис. 5. Рассмотренные модели, безусловно, не отражают все разнообразные ситуации, которые встречаются в практической деятельности. Тем не менее, их можно рекомендовать для дальнейших исследований в курсе компьютерного математического моделирования. Литература Вентцель Е.С. Исследование операций.  М.: Советское радио, 1972.  552с. Ашманов С.А. Линейное программирование. Учебное пособие.  М.: Наука, 1981.  304с. Курицкий Б. Поиск оптимальных решений средствами Excel 7.0.  Спб.: BHV  Санкт-Петербург, 1997. Трофимец В.Я., Трофимец Е.Н. Компьютерное моделирование оптимизационных задач транспортного типа в Microsoft Excel //Информатика и образование, 2008.

Похожие:

	Урок английского языка в VII классе по теме: «Problems of Free Time» «Problems of Free Time». But before we discuss this problem let’s revise what we know about free time and learn some new words		Institute for Information Transmission Problems ras
	Математическое моделирование термически нагруженных конструкций котельных агрегатов Специальность: 05. 13. 18 – Математическое моделирование, численные методы и комплексы программ		Урока: закрепить полученные умения и навыки по теме «Environment. Problems that it faces» Цели урока: закрепить полученные умения и навыки по теме «Environment. Problems that it faces»
	Тюменский государственный университет «утверждаю»: Проректор по учебной работе Вычислительные, программные, информационные системы и компьютерные технологии", "Математический анализ и приложения", "Математическое...		Тема урока : «Environmental Problems» Развивающая – развитие активности, способности к анализу, обобщению и формулированию собственных выводов
	Программа элективного курса «Компьютерное моделирование» Учебный курс «Компьютерное моделирование» предназначен для изучения в старших классах профильной школы. Курс является элективным,...		Исследование и разработка бионических методов и алгоритмов для решения задач транспортного типа
	Компьютерное моделирование фоновых условий в эксперименте gerda и... При планировании, подготовке и интерпретации результатов экспериментов в физике атомного ядра, элементарных частиц, неускорительной...		Урок английского языка Тема: Environmenral Problems Тип урока: по основной дидактической цели – урок комплексного применения изученного
	Labour migration from the Central Asia to Russia: Sociocultural problems and contradictions Среда обитания. Особенности строения: специализация клеток, два клеточных слоя(наружный и внутренний)		М. С. Кузнецов a dicision of the exports and import problems of russian... Решение проблем экспорта и импорта машиностроительного комплекса россии на основе синергетического подхода
	Урок: “Ecological problems in nao and in Russia” Цели проводимого урока: систематизация знаний о деятельности экологических организаций, активизация лексики, закрепление грамматических...		Программа по формированию навыков безопасного поведения на дорогах... Оборудование- электронный плакат по теме «How to tackle with our problems?», мультимедийный проектор, магнитофон, аудиозапись, тексты...
	Урок Краснова Ольга Александровна Литературное чтение. Обобщающий урок Краснова Ольга Александровна, учитель начальных классов		Математическое и компьютерное моделирование для неразрушающего... Они изготавливаются в форме тонких пластин различной геометрии, монтаж которых с учетом современного развития технологий изготовления...