Проверка задачи на разрешимость

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

Транспортные задачи. Метод потенциалов.

Задачи о назначениях

 

Направление подготовки 080200 Менеджмент

 

 

Профиль подготовки (бакалавриат)

Производственный менеджмент

 

 

Квалификация (степень) выпускника

Бакалавр

 

Уфа 2012

УДК 519.86

ББК 65.23

Л 12

 

Рекомендовано к изданию методической комиссией экономического факультета (протокол № ___ от _ _________ 2010 г.)

 

 

Составитель: доцент Шатова В.С.

 

Рецензент: ст. преподаватель кафедры информатики и ИТ Саитова Э.С.

 

 

Ответственный за выпуск:

зав.кафедрой статистики и информационных систем в экономике

д.э.н., профессор Рафикова Н.Т.

 

 

ОГЛАВЛЕНИЕ

 

Введение

1 Цель и задачи………………………………………….………………….. 4

2 Методика решения транспортной задачи линейного программирования

методом потенциалов………………………………..…………….…………5

2.1 Последовательность решения задачи………………………………..…5

2.1.1 Проверка задачи на разрешимость………………………………. 5

2.1.2 Построение матрицы задачи…………………………………….. 6

2.1.3 Решение задачи методом потенциалов…………..….…….…… 6

2.1.4 Реализация метода потенциалов…………………………………7

2.1.5 Экономический смысл решения…………………………………14

3 Вопросы для самоконтроля……………………………………………….15

Библиографический список………………………………………….……...16

ВВЕДЕНИЕ

 

С экономической точки зрения транспортная задача линейного программирования представляет собой задачу о наиболее рациональном
плане перевозок однородного груза.

Общая постановка задачи формулируется следующим образом:
имеется m поставщиков с запасами Ai единиц груза и n потребителей с по­-
требностями в грузах Вj). Известны расстояния от каждого поставщика до
каждого потребителя: С i j (где i - номер поставщика, j - номер потребите-
ля). Определить, от какого поставщика до какого потребителя и сколько
единиц груза надо перевезти, чтобы вывезти весь груз от всех поставщи-
ков, удовлетворить потребности всех потребителей и при этом общие за­
траты на транспортировку были бы минимальными, т.е. составить опти-.
мальный план перевозок.

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

 

 

1 ЦЕЛЬ И ЗАДАЧИ

 

Цель: Освоить методику решения транспортных задач линейного программирования методом потенциалов.

Задачи: 1 Научиться математически формулировать задачи распределительного типа.

2 Уяснить алгоритм метода потенциалов.

3 Решить транспортную задачу методом потенциалов.

4 Сформулировать краткие выводы по результатам решения задачи.

Требование к организации рабочего места (оборудование, приборы, материалы): Для выполнения задания необходимо наличие компьютера. Программное обеспечение: пакет экономических расчетов PER, программа обработки электронных таблиц EXCEL

 

2 МЕТОДИКА РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ПОТЕНЦИАЛОВ

 

Рассмотрим простейший пример экономической задачи о перевозках.

Условие задачи. На трех пасеках пчелосовхоза имеется 560 пчелосемей, причем на первой пасеке - 200, второй - 150 и третьей - 210 пчелосемей. Требуется отвезти пчелосемьи для опыления сельскохозяйственных культур на четыре точки: первая точка вмещает 150 пчелосемей, вторая -190, третья - 100, четвертая - 120 пчелосемей. Определить, от какой пасеки до какой точки и сколько пчелосемей необходимо перевезти, чтобы общие затраты на их, перевозки были минимальными. Расстояния от пасек до точек известны (табл.1).

 

Таблица I - Расстояния от пасек до точек, км.

Пасеки	Точки
I
II
III

Последовательность решения задачи

Проверка задачи на разрешимость

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

A₁ + A₂+ A₃ = B₁ + B₂ + B₃+В₄ (1)

(или в сокращенной записи ( Ai = Bj).

Выполнение данного равенства есть необходимое и достаточное условие совместимости и, следовательно, разрешимости транспортной за­дачи.

В нашей задаче:,

наличие пчелосемей на всех пасеках: Ai = 200 + 150 + 210 =560; потребность всех точек: Bj=150+190 + 100 + 120 = 560.

Таким образом Ai = Bj =560, т.е: задача закрытая. Методом потенциалов решаются только закрытые задачи.

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

Примечание 1. Если суммарные запасы поставщиков превышают сум­марное потребности потребителей или наоборот, суммарные потребности потребителей больше суммарных запасов поставщиков, т.е.

Ai > Bj или Ai < Bj

 

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

Ai - Bj,

или дополнительная строка, в которой запас груза равен разности:

Bj - Ai

Тарифы всех клеток, как фиктивного поставщика, так и фиктивного
потребителя принимаются равными нулю.

Переход от открытой модели к закрытой означает приведение моде­ли транспортной задачи к канонической форме.