Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Аналитическое решение

Читайте также:
  1. PMCS стала первым Облачным партнером Microsoft по управлению проектами предоставив решение с интеграцией с Office 365
  2. А теперь мое решение проблемы
  3. Аналитическое решение задачи экранирования магнитного поля внутри полого шара
  4. В соответствии с решением приемной комиссии (ПРОТОКОЛ № 8 от 19.08.2013г.) и Правилами приема граждан на обучение в ОГБОУ СПО «Ульяновский строительный колледж» от 06 мая 2013г.
  5. Воскрешение основного вопроса философии
  6. Групповое решение как групподинамический процесс.

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

1) отыскивается исходное опорное решение;

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

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

Построим исходное опорное решение методом «северо-западного угла» (табл. 2). Поскольку потребности первого потребителя В1 (b1=220 м3) больше, чем запасы первого глинзавода А1 (a1=120 м3), то для удовлетворения этих потребностей будем использовать запасы первого и второго глинзавода; в первую ячейку записываем x11=b1=120 м3, в ячейку (2.1) записываем недостающие 100 м3. Далее перемещаемся в ячейку (2.2) и записываем здесь оставшиеся 40 м3. Для удовлетворения потребностей второго бурового участка нам не хватает 140 м3, поэтому воспользуемся запасами третьего глинзавода – в ячейке (3.2) записываем 140 м3. Таким образом, потребности второго потребителя В2 полностью удовлетворены.

Таблица 2. Транспортная таблица (исходное опорное решение)

Склады Потребители Запасы заданные
В1 В2 В3 В4
А1          
А2          
А3          
А4          
Потребности заданные         -

 

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

В результате имеем таблицу с заполненными семью ячейками, что соответствует теории: m+n-1=7, где m и n – число складов и буровых соответственно. Заметим, что суммарная стоимость перевозок исходного опорного решения равна:

Определение оптимального решения методом потенциалов

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

Для того, чтоб допустимый (опорный) план транспортной задачи X={ xij}, был оптимальным, необходимо и достаточно, чтобы существовала система чисел ; , удовлетворяющих условиям:

(5)

(6)

Соотношения (5) и (6) называются условиями потенциальности оптимального плана транспортной задачи. Набор величин приписывается строкам (первой строке - U1, второй – U2 и т.д.), поэтому U1 называется потенциалом первой строки, U2 – потенциалом второй строки и т.д. Аналогично набор величин приписывается столбцам (первому столбцу - V1, второму - V2 и т.д.) и эти величины называются потенциалами соответствующих столбцов.

Соотношение (5) можно переписать в виде:

, где , если . (7)

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

Шаг 1 – определяем потенциалы исходного опорного решения (см. табл. 1). Строкам этого решения назначаем потенциалы U 1, U 2, U 3, а столбцам – потенциалы V 1, V 2, V 3, V 4. Для их расчета составляем систему уравнений:

Имеем восемь неизвестных величин и семь уравнений. Значение любой неизвестной величины задаем произвольным числом, например, U 3=0. Тогда, остальные величины потенциалов будут равны:

U 1=-3; U 2=-2;U4=2; V 1=-1; V 2=2; V 3=4; V 4=3.

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

 

Таблица 3. Транспортная таблица с вычисленными значениями потенциалов

  Склады Потребители Запасы заданные  
В1 В2 В3 В4
  А1                     -3
               
  А2                     -2
               
  А3   -2                
               
  А4   -6   -4            
               
Потребности заданные           -   -
-1         -   -

 

Шаг 2 – вычисляем значения невязок для всех ячеек без перевозок по соотношению (7). Запишем значения невязок в правый верхний угол каждой ячейки (значения невязок выделены полужирным шрифтом). В ряде клеток наблюдаются нарушения (невязки больше нуля): (1,2), (1,3), (1,4), (2,3), (2,4) и, следовательно, план может быть улучшен.

Шаг 3 – организуем замкнутый контур с началом в ячейке (2,3), имеющей максимальную положительную невязку v max=5:

вершина 1 (2,3) ® вершина 2 (3,3) ® вершина 3 (3,2) ® вершина 4 (2,2).

Величинаперераспределения q равна наименьшему значению из перевозок, стоящих в четных вершинах цикла, т.е. q =min{90;40}=40 м3. Вычислим новые значения перевозок для вершин контура: в нечетных вершинах добавляем величину q, а в четных вершинах – вычитаем эту величину:

 

· в вершине 1 (2,3) х 23=0+40=40 м3;

· в вершине 2 (3,3) х 33=90–40=50 м3;

· в вершине 3 (3,2) х 32=140+40=180 м3;

· в вершине 4 (2,2) х 22=40–40=0 м3.

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

Таблица 4

  Склады Потребители Запасы заданные  
В1 В2 В3 В4
  А1       -1   -1   -1      
               
  А2       -5       -2      
               
  А3                    
               
  А4   -1   -4            
               
Потребности заданные           -   -
          -   -

 

Уменьшение стоимости перевозок по отношению к исходному опорному плану составит:

Теоретически это уменьшение равно q×v max=40×5=200 руб., что совпадает с рассчитанным выше значением.

Начинаем проверку оптимальности сначала.

Шаг 1 – составляем новую систему потенциалов:

Пусть U 3=0. Тогда

U 1=2; U 2=3;U4=2; V 1=4; V 2=2; V 3=4; V 4=3.

Занесем эти значения потенциалов в транспортную таблицу взамен старых (см. табл. 4).

Шаг 2 – определяем значения невязок для всех ячеек с «нулевыми» перевозками по соотношению (7). Значения невязок записаны в правом верхнем углу ячеек и выделены полужирным шрифтом.

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

Шаг 3 – организуем замкнутый контур с началом в ячейке (3,1), имеющей максимальную положительную невязку v max=3:

вершина 1 (3,1) ® вершина 2 (2,1) ® вершина 3 (2,3) ® вершина 4 (3,3).

q =min{100;50}=50 м3

Вычислим новые значения перевозок для вершин контура: в нечетных вершинах добавляем величину q, а в четных вершинах – вычитаем эту величину:

· в вершине 1 (3,1) х 31=0+50=50 м3;

· в вершине 2 (2,1) х 21=100–50=50 м3;

· в вершине 3 (2,3) х 23=40+50=90 м3;

· в вершине 4 (3,3) х 33=50–50=0 м3.

 

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

Таблица 5

  Склады Потребители Запасы заданные  
В1 В2 В3 В4
  А1           -1   -1     -1
               
  А2       -1       -2      
               
  А3           -3   -3    
               
  А4   -1               -1
               
Потребности заданные           -   -
          -   -

Уменьшение стоимости перевозок по отношению к предыдущему опорному плану составит:

руб.,

что совпадает с теорией: q×v max=50×3=150 руб.

Начинаем проверку оптимальности сначала.

Шаг 1 – рассчитаем очередную систему потенциалов:

..

Пусть U 3=0. Тогда

U 1=-1; U 2=0;U4=-1; V 1=1; V 2=3; V 3=1; V 4=0.

Занесем эти значения потенциалов в транспортную таблицу взамен старых (см. табл. 5).

Шаг 2 – определяем значения невязок для всех ячеек с «нулевыми» перевозками по соотношению (7). Значения невязок записаны в правом верхнем углу ячеек и выделены полужирным шрифтом.

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

Шаг 3 – организуем замкнутый контур с началом в ячейке (1,2), имеющей максимальную положительную невязку v max=3:

вершина 1 (1,2) ® вершина 2 (3,2) ® вершина 3 (3,1) ® вершина 4 (1,1).

q =min{180;120}=120 м3

Вычислим новые значения перевозок для вершин контура: в нечетных вершинах добавляем величину q, а в четных вершинах – вычитаем эту величину:

· в вершине 1 (1,2) х 12=0+120=120 м3;

· в вершине 2 (3,2) х 32=180–120=60 м3;

· в вершине 3 (3,1) х 31=50+120=170 м3;

· в вершине 4 (1,1) х 11=120–120=0 м3.

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

Таблица 6

  Склады Потребители Запасы заданные  
В1 В2 В3 В4
  А1   -2       -3   -3      
               
  А2       -2       -2      
               
  А3           -3   -3    
               
  А4   -1   -1           -1
               
Потребности заданные           -   -
          -   -

 

Уменьшение стоимости перевозок по отношению к предыдущему опорному плану составит:

руб.,

что не совпадает с теорией: q×v max=120×3=360 руб.

Начинаем проверку оптимальности сначала.

Шаг 1 – рассчитаем очередную систему потенциалов:

..

Пусть U 3=0. Тогда

U 1=1; U 2=0;U4=-1; V 1=1; V 2=2; V 3=1; V 4=0.

Занесем эти значения потенциалов в транспортную таблицу взамен старых (см. табл. 6).

Шаг 2 – определяем значения невязок для всех ячеек с «нулевыми» перевозками по соотношению (7). Значения невязок записаны в правом верхнем углу ячеек и выделены полужирным шрифтом.

Все невязки неположительные, следовательно, оптимальное решение найдено.


Дата добавления: 2015-11-16; просмотров: 120 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Математическая модель| Решение с помощью MS Excel

mybiblioteka.su - 2015-2024 год. (0.017 сек.)