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

Примерами циклов могут служить ломаные замкнутые линии:

Циклы в матрице тарифов удовлетворяют следующим свойствам:

Число вершин в каждом цикле четно.

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

Пусть в матрице, состоящей из m строк и n столбцов, произвольно отмечено m+n клеток. Тогда существует цикл, вершины которого лежат в отмеченных клетках.

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

Улучшение плана перевозок. Распределительный метод.

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

Пусть (i0, j0) - свободная клетка. Построим цикл с вершиной (i0, j0), все остальные вершины которого находятся в заполненных клетках. Присвоим свободной вершине (i0, j0) знак + и означим цикл.

Переместим по циклу величину и. Очевидно, значение и не может превосходить min {x -ij}, где x -ij - значения поставок, находящихся в отрицательно означенных вершинах цикла.

При сдвиге по циклу на величину и допустимый план остается допустимым. Стоимость же плана может увеличиваться или уменьшаться.

Рассмотрим, какое изменение ?Z целевой функции вызывается сдвигом по циклу на величину и. Это изменение выразится формулой:

?Z = и ? ( ? {c+ij} - ?{ c -ij}), где ? {c+ij} и ?{ c -ij} - соответственно сумма тарифов по положительно и отрицательно означенным клеткам цикла.

Обозначим величину ? {c-ij} - ?{ c +ij} = ?i0 j0 и назовем ценой цикла величину ?Z = - и ??i0 j0.

Опорный план можно улучшить только в том случае, если существует свободная клетка (i0, j0) , для которой ?Z < 0. Но так как и > 0, то ?Z < 0, если ?i0 j0 > 0.

Итак, опорный план можно улучшить, если существуют свободные клетки с положительной оценкой. Сделав сдвиг по циклу на величину и = min {x -ij}, получим новый опорный план. Свободная клетка (i0, j0) становится заполненной , а клетка, для которой и = min {x -ij}, считается свободной. Если существует несколько клеток, для которых и = min {x -ij}, то клетка с максимальным тарифом считается свободной, а в остальных - нулевая поставка.

Таким образом, сдвиг по циклу на величину и = min {x -ij} позволяет прийти к новому, улучшенному опорному плану. При этом значение целевой функции изменится на величину ?Z = - и ??i0 j0, т.е. уменьшится.

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

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

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

Исходные данные заносятся в таблицу (в случае необходимости модель задачи приводится к закрытой).

Строим начальный опорный план. Занятыми должны быть m+n-1 клеток.

Находим оценки свободных клеток. Так как к улучшению приводит сдвиг по циклу для свободной клетки с положительной оценкой, то целесообразно испытывать их не все подряд, а выбирать в первую очередь клетки, имеющие минимальные тарифы cij. Если ?i j ? 0, то оцениваем следующую свободную клетку и т.д., пока не найдем клетку с положительной оценкой. Если же для всех свободных клеток ?i j ? 0, то найденный опорный план оптимален.

Пусть (i0, j0) - клетка с положительной оценкой. Находим и = min {x -ij}. Делаем сдвиг по циклу на величину и. Получим улучшенный опорный план и т.д.

Пример. Найти распределительным методом оптимальный план транспортной задачи, заданной таблицей.

В данной таблице с помощью способа минимального элемента построен начальный опорный план X0, Z(X0) = 270.

Число заполненных клеток m + n -1 = 3 + 4 -1 = 6.

Приступаем к улучшению опорного плана (если это возможно).

Находим свободную клетку с минимальным тарифом - (1,1). Для нее в таблице постоим означенный цикл пересчета.

С его помощью находим цену цикла ?11=? {c-ij} - ?{c +ij} = =(2+8+2) - (3+4+3) = 2.

Следовательно, сдвиг по циклу на величину и = min {10, 20, 10}=10 выгоден. Значение целевой функции должно измениться на величину ?Z = - и ??11= -10 ? 2=-20.

Сделав сдвиг по циклу на величину и = 10, придем к новому опорному плану Z=250.

Расположим свободные клетки в порядке возрастания тарифов (1,4), (2,2), (1,3), (3,2), (2,4), (3,1).

Для клетки (1,4) цикл пересчета совпадает с циклом (1,1). Следовательно, его цена = -2.

Далее находим:

?22=(2+1) - (3+4) = -4.

?13= (3+3) - (2+4) = 0

?32= (8+2+1) - (5+3+3) = 0

?24= (4+3) - (6+8) = -7

?31= (2+8) - (7+4) = -1.

Так как для всех свободных клеток ?i j ? 0, то найденный план в последней таблице оптимален. Очевидно, он не единственный (об этом говорят нулевые оценки свободных клеток). Построив для клеток ?13 и ?13 циклы пересчета и сделав сдвиг по циклу, получим новые опорные планы.

Задание

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

Указания.

Программа должна содержать меню для выбора способа построения начального опорного плана (в меню должен быть включен каждый из способов );

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

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

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

Литература

Банди Б. Основы линейного программирования. Москва, «Радио и связь», 1989

Балашевич В.А. Основы математического программирования.

Ларионов А.И., Юрченко Т.И., Новоселов А.Л. Экономико-математические методы в планировании. Москва, «Высшая школа» , 1991

Вентцель Е.С. Исследование операций.

Лабораторная работа № 8

Тема: «Двухэтапная транспортная задача.»

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

Теоретические сведения.

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

Пусть m ( i = 1,m) пунктов производства, n ( j = 1,n) пунктов потребления и p ( r = 1,p) промежуточных баз.

Как и в обычной транспортной задаче, обозначим через ai, bj соответственно объемы поставок и потребления.

Пусть dr - мощность r -й базы; cir и crj - соответственно стоимость перевозки единицы продукции от поставщиков на базы и с базы к потребителям.

Тогда модель задачи имеет вид:

Если суммарная пропускная мощность баз равна суммарной мощности поставщиков и суммарному спросу потребителей, т.е.

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

В таких случаях задачу можно решать по частям:

составить оптимальный план поставок от поставщиков к базам.

Составить оптимальный план поставок с баз к потребителям.

Оптимальный план задачи будет объединением двух оптимальных планов, составленных по частям.

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

Приведем двухэтапную транспортную задачу к классической задаче. Для этого будем считать базы одновременно поставщиками и потребителями. Для каждой базы в расширенной матрице (поставщики + базы) - (базы + потребители) отведем строку и столбец. Тогда матрица тарифов будет состоять из 4-х блоков:

В первом - левом верхнем блоке отражаются связи поставщиков с базами (i r), в 4-м - связи баз с потребителями.

Так как по условию задачи непосредственные перевозки от поставщиков к потребителям запрещены, то во 2-м блоке все тарифы считают равными М (где М - некоторое заведомо большое число).

Аналогично, перевозки между базами также запрещены по условию задачи, поэтому 3-й левый нижний блок - перевозки между базами - также заполнен показателями М.

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

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

Изменение нахождения начального опорного плана:

а) необходимо распределить поставки в одном из блоков (1-м или 4-м)

б) заполнить фиктивную диагональ.

в) распределить поставки в другом блоке (4-м или 1-м)

Если цикл пересчета проходит через фиктивную диагональ, то он обязательно проходит через нее дважды: одна вершина цикла, находящаяся на диагонали, будет всегда +, другая -.

Пример. Имеется два маслодельных завода А1, А2. Сливочное масло поступает сначала в холодильники Д1, Д2, Д3, а из них - в пункты потребления В1, В2, В3 и В4. Исходные данные представлены в таблицах:

Тарифы перевозок от поставщиков на базы

Тарифы перевозок с баз к потребителям

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

Решение.

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

Определим начальный опорный план способом минимального элемента (распределение начато с 4-го блока).

а) x12=75 x21=150 x22=175 x23=175 x34=225

б) заполняем фиктивную диагональ (разность dr - xrj)

в) заполняем 1-й блок. Так как на базах Д1 и Д3 после поставок потребителям остались неиспользованными мощности d1=165 и d3=35, то в блоке 1 конечное значение поставок на базы будут соответственно меньше на d1 и d3:

x11=75 x12=50 x13=225 x22=450

Улучшим план.

а) выбираем свободную клетку с минимальным тарифом (3, 4) и строим цикл (3,4)-(3,5)-(4,5)-(4,4).

Д34= 29 - 27 = 2 (план можно улучшить)

И = min {75, 150}=75

б) (4, 2) : строим цикл (4,2)-(4,4)-(3,4)-(3,1)-(1,1)-(1,2)-(4,2).

Д42= 33 - 32 = 1 (план можно улучшить)

И = min {75, 165, 50}=50

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

Итак, оптимальный план перевозок имеет вид:

x i =1 r =1=125 x i =1 r =3=225 x i =2 r =2=450 x r =1 j =1=125 x r=2 j =1=25 x r=2 j =2=250 x r =2 j =3=175

x r =3 j =4=225

Z0 = 21225 д.е. и Zопт = 21025 д.е. Таким образом, улучшение плана составило экономию денежных средств на перевозку в объеме 200 д.е.

Замечание. Если решать задачу в 2 этапа, т.е. находить сначала оптимальный план поставок поставщиков к холодильникам, а затем задачу оптимальных поставок с холодильников к потребителям, суммарные потери составят минимально 25350 д.е.

Задание

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

Указания.

Программа должна содержать меню для выбора способа построения начального опорного плана (в меню должен быть включен каждый из способов );

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

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

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

Литература

1. Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов / Под ред. В.С. Зарубина, А.П. Крищенко. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2000.

2. Таха, Хемди А. Введение в исследование операций. - М.: Изд. дом «Вильямс», 2005

3. Банди Б. Основы линейного программирования. - Москва: «Радио и связь», 1989.

4. Балашевич В.А. Основы математического программирования. - Минск: «Высшая школа», 1985.

5. Ларионов А.И., Юрченко Т.И., Новоселов А.Л. Экономико - математические методы в планировании.- М.: «Высшая школа», 1991.

6. Сакович В.А. Исследование операций - Минск: «Высшая школа», 1985

Размещено на Allbest.ru