Линейное программирование



страница8/10
Дата02.01.2013
Размер0.83 Mb.
ТипМетодические указания
1   2   3   4   5   6   7   8   9   10

6.2 Построение начального опорного плана

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

Рассмотрим метод минимального элемента. Построение начального опорного плана и его последующее преобразование будем проводить непосредственно в распределительной таблице (таблица 6.1). В соответствии с методом минимального элемента просматривают тарифы таблицы 6.1 и в первую очередь заполняют клетку с минимальным значением тарифа . При этом в клетку записывают максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответствующую поставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом. Процесс распределения заканчивают, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. В результате получают опорный план, который содержит загруженных клеток. В процессе заполнения таблицы могут быть одновременно исключены строка и столбец. Так бывает, когда полностью исчерпывается запас груза и полностью удовлетворяется спрос (вырожденная задача). В этом случае в свободные клетки надо записать число 0–"нуль-загрузка", условно считая такую клетку занятой. Однако число 0 записывают в те свободные клетки, которые не образуют циклов (см. ниже) с ранее занятыми клетками.

Пример 6.1. Предприятие, содержащее сеть из пяти автозаправочных станций, обеспечивается бензином с трех нефтебаз. Суточные потребности АЗС, возможности нефтебаз и тарифы перевозок (руб./тонну) записаны в таблице 6.2.

Требуется определить начальный опорный план данной транспортной задачи и вычислить суточные расходы предприятия на перевозки бензина.

Решение. Поскольку запасы топлива на нефтебазах превышают спрос потребителей, введем фиктивный пункт назначения с потребностью

тонн с нулевыми тарифами перевозок Исходный опорный план перевозок построим

Таблица 6.2

Пункты отправления

Пункты назначения.


Запасы

(тонн)




gif" name="object555" align=absmiddle width=25 height=21>














14

20

10

16

17

80



15

8

14

11

8

90



10

16

12

12

10

140

Потребности,

(тонн)


40


30


90


80


50


290<

<310

методом минимального элемента, начиная планировать перевозки с маршрутов с наименьшими тарифами перевозок.

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

Минимальный тариф, равный нулю, находится в клетках для переменных , и . Положим, например, и запишем это значение в соответствующую клетку таблицы 6.3. Так как потребности пункта обеспечены, исключим временно из рассмотрения шестой столбец. Оставшиеся на первой нефтебазе 60 тонн топлива запишем в клетку (1;3) с наименьшим тарифом, т. е. и исключим временно из рассмотрения первую строку. В пункт назначения

Таблица 6.3

Нефтебазы

Автозаправочные станции

Запасы (тонн)






















14



20


10

60

16



17



0

20

80




15

8

30

14

11

10

8

50


0

90



10

40

16

12

30

12

70


10

0

140

Потреб-ности (тонн)


40


30


90


80


50


20


310


остается доставить 30 тонн топлива. Так как в третьем столбце минимальный тариф находится в клетке (3;3), положим . Далее заполним клетки второй строки (2;5), (2;2) и (2;4) значениями , и . И, наконец, заполним клетки третьей строки (3;1) и (3;4), полагая , . В результате получим начальный опорный невырожденный план (таблица 6.3), число занятых клеток равно .

При данном плане перевозок общая стоимость перевозок равна



6.3 Метод потенциалов

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

Теорема 6.2. Если для некоторого опорного плана транспортной задачи существует система из чисел , , удовлетворяющих условиям

для (6.6)

и для , (6.7)

то –оптимальный план транспортной задачи.

Определение 6.2. Числа и называются потенциалами соответственно -го пункта отправления -го пункта назначения.

В соответствии с введенным понятием потенциалов каждому пункту отправления ставят в соответствие потенциал , а каждому пункту назначения–потенциал .

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

. (6.8)

Если все числа , то найденный опорный план является оптимальным. Если же для некоторой свободной клетки , то найденный опорный план не является оптимальным и необходимо перейти к новому опорному плану. Для этого рассматривают все свободные клетки, для которых , и среди данных чисел выбирают наименьшее (наибольшее по абсолютной величине). Клетку, которой соответствует это число, следует заполнить.

Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других занятых клеток и связанных с заполненной так называемым циклом.

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

Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами.

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

  1. каждой из клеток, связанных циклом с данной свободной клеткой,

приписывают определенный знак, причем свободной клетке–знак

плюс, а всем остальным клеткам–поочередно знаки минус и плюс;

  1. в данную свободную клетку переносят меньшее из чисел , стоя-

щих в минусовых клетках. Одновременно это число прибавляют к

соответствующим числам, стоящим в плюсовых клетках, и вычита- ют из чисел, стоящих в минусовых клетках. Клетка, которая ранее

была свободной, становится занятой, а минусовая клетка, в которой

стояло наименьшее из чисел , считается свободной.

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

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

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

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

Пример 6.2. Найти оптимальный опорный план задачи из примера 6.1 и вычислить суточные расходы предприятия на перевозки бензина по этому плану.

Решение. Начальный опорный план задачи найден в примере 6.1.

Итерация 1 Для определения потенциалов составляем систему уравнений вида (6.6):

, , , ,

, , ,

Полагая , найдем, что , , , , , , , .

Потенциалы проставлены в таблице 6.4. Определим оценки свободных клеток:

, ,

, ,

, ,

, ,

,

Таблица 6.4.

40 30 90 80 50 20

14

20

10

60

+

16

17

0

20





15

8

30

14

11

10

8

50

0



10

40

16

12

30



12

70

10

0

+



, , , , , .

Так как среди чисел имеются отрицательные, то построенный план перевозок не является оптимальным и надо перейти к новому опорному плану.

Итерация 2. Наиболее потенциальной является клетка (3;6). Строим для клетки (3;6) цикл непосредственно в таблице 6.4. В него войдут клетки (3;6), (3;3), (1;3), (1;6). Наименьшее количество груза, стоящее в минусовых вершинах цикла, равно 20. В результате смещения по циклу получим новый опорный план (таблица 6.5).

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

, , , ,

, , , .

Ее решение имеет вид: , , , , , , , , .

Таблица 6.5

40 30 90 80 50 20

14

20

10

80

16

17

0



15

8

30

14

11

10

8

50

0



10

40

16

12

10

12

70

10

0

20


1   2   3   4   5   6   7   8   9   10

Похожие:

Линейное программирование iconЛинейное программирование
Линейное программирование (ЛП) это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на...
Линейное программирование iconПеречень вопросов для вступительного экзамена в аспирантуру по специальности 05. 13. 18 «Математическое моделирование, численные методы и комплексы программ» Математические основы
Математическое программирование, линейное программирование, выпуклое программирование
Линейное программирование iconЛинейное программирование. Методы решения одношаговых задач оптимального управления
Методы решения таких задач получили название математического программирования. Простейшим случаем математического программирования...
Линейное программирование iconМатематическое программирование
В математическом программировании выделяют линейное программирование – когда функции и линейны, квадратичное программирование, когда...
Линейное программирование iconЛинейное программирование задачи математического и линейного программирования
Соответствующие методы, позволяющие решать указанные задачи, объединяются под общим названием «математическое программирование»
Линейное программирование iconПараметрическое линейное программирование
Параметрическое программирование представляет собой один из разделов математического программирования, изучающий задачи, в которых...
Линейное программирование icon«Линейное программирование и симплекс метод»

Линейное программирование iconВопросы экзамена Методы оптимизации Раздел Линейное программирование
Алгоритм симплекс-метода без корректного вида базиса с искусственными переменными
Линейное программирование iconЛинейное программирование и симплекс метод
...
Линейное программирование iconТранспортная задача
Линейное программирование является одним из разделов математического программирования – области математики, разрабатывающей теорию...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org