РАСПРЕДЕЛИТЕЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

РАСПРЕДЕЛИТЕЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Методические указания к лабораторным работам

для студентов специальности 120303, 080100, 080200

САНКТ-ПЕТЕРБУРГ

Федеральное государственное образовательное учреждение высшего профессионального образования

Национальный минерально-сырьевой университет «Горный»

Кафедра информатики и компьютерных технологий

РАСПРЕДЕЛИТЕЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Методические указания к лабораторным работам

для студентов специальности 120303, 080100, 080200

САНКТ-ПЕТЕРБУРГ

УДК 519.86:622.3.012 (075.83)

РАСПРЕДЕЛИТЕЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Методические указания для выполнения лабораторных работ для студентов специальностей 120303. /НМСУ «Горный». Сост.: В.В. Беляев, Т.Р. Косовцева. СПб, 2012., 39 с.

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

Предназначены для студентов специальностей 120303 «Городской кадастр», 080100 «Экономика», 080200 «Менеджмент» дневной и заочной формы обучения, могут быть полезны всем, изучающим математическое моделирование.

.

Табл. 3. Рис.20. Библиогр.: 3 назв.

Научный редактор доц. Прудинский Г.А.

© Национальный минерально-сырьевой университет «Горный», 2012

Введение

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

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

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

ЛАБОРАТОРНАЯ РАБОТА 3.

3.Транспортная задача

Цель работы: изучить постановку транспортной задачи; освоить метод потенциалов.

3.1. Постановка задачи. основные формулы

Частным случаем задачи ЛП является транспортная задача-задача о планировании перевозки грузов. Она может быть сформулирована следующим образом.

Пусть имеется m поставщиков однородного груза. Запасы его у каждого из поставщиков равны a_i (i=1,2,…m) единиц соответственно. Также существует n потребителей , j - потребитель имеет потребность в грузе b_j (j=1,2,…n). Пусть стоимость перевозки единицы груза от i-го поставщика j-му потребителю равна c_ij. Требуется определить план перевозок (объемы грузоперевозок от i-го поставщика j-му потребителю) таким образом, чтобы все запасы были вывезены, потребности в грузе удовлетворены, и суммарная стоимость перевозок была минимальной.

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

Составим математическую модель транспортной задачи закрытого типа.

Обозначим через x _ij объем грузоперевозок от i -го поставщика j -му потребителю. Тогда целевая функция может быть определена соотношением:

(3.1)

где: F - суммарная стоимость всех перевозок.

Требование о вывозе груза у всех поставщиков порождает следующие фазовые ограничения:

, (3.2)

а требование об удовлетворении потребностей в грузе всех потребителей порождает такие фазовые ограничения:

. (3.3)

Соотношения

(3.4)

являются естественными ограничениями.

Заметим, что транспортная задача, определяемая соотношениями (3.1) - (3.4), содержит подлежащих определению переменных.

Транспортная задача (ТЗ) является частным случаем задачи ЛП и может быть решена симплекс-методом. Специфический характер ТЗ позволяет использовать для решения специальные таблицы – транспортные таблицы. Пример такой таблицы приведен на рис.3.1.

3.2. Решение транспортной задачи

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

Решение строится в два этапа:

· на первом этапе отыскивается исходное опорное решение;

· на втором этапе методом последовательных итераций ищется оптимальное решение.

3.2.1. Определение исходного опорного решения

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

В первую клетку (1,1) занесем значение:

_· Если a₁ > b₁, то x₁₁=b₁ и потребности первого потребителя удовлетворены полностью, это позволяет закрыть первый столбец. Двигаемся далее по первой строке. Для этого в клетку (1,2) записываем меньшее из чисел a₁ - b₁ и b₂,, т.е. x₁₂ = min { a₁ - b₁; b₂ }.

_· Если a₁<b₁, то x₁₁ = a₁ и запасы первого поставщика вывезены полностью, и закрываем первую строку. Двигаемся далее по первому столбцу. Для этого в клетку (2,1) записываем меньшее из чисел b₁-a₁ и a₂ , т.е. x_{2 1} = min{ b₁-a₁; b₂ } _.

Далее двигаемся от клетки к клетке, пока на каком-то этапе не исчерпаются ресурсы и потребности.

В результате этой процедуры m+ n -1 клеток будут содержать перевозки, остальные – будут пустыми.

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

3.2.2. Построение оптимального решения

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

Поиск по сайту: