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

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

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

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

2012

Министерство образования и науки Российской Федерации

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

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

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

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

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

для студентов направлений подготовки бакалавриата

120700, 080100, 080200

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

2012

УДК 519.86:622.3.012 (075.83)

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

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

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

Предназначены для студентов направлений подготовки бакалавриата 120700 «Землеустройство и кадастры», 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.