АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Проверка опорного решения на выполнение граничных условий

Читайте также:
  1. III Проверка правильности настройки ККСВ. Вновь проводится пункт 2 , при этом контролируется своевременность зажигания с/д и отключение контактора.
  2. IV. Алгоритм действий командира (начальника) при увольнении военнослужащего в связи с невыполнением им условий контракта
  3. IV. Первичная проверка усвоения новых знаний.
  4. IX. Сложные решения
  5. V. Изучение гидрогеологических, инженерно-геологических, экологических и других природных условий месторождения
  6. V. Повторная проверка
  7. Wiley, 1993), p. 142. Перепечатано с разрешения.
  8. Абсолютизм. Общая характеристика. Особенности стиля. Используемые композиционные решения, конструктивные элементы и строительные материалы. Ключевые здания. Ключевые архитекторы.
  9. Алгоритм решения дробно-рациональных неравенств.
  10. Алгоритм решения задачи
  11. Алгоритм решения ЗЛП графическим методом
  12. Алгоритм решения.

а) по строкам:

1. 100+50+1250=1400

2. 2000 =2000

3. 550 =550

5. 1300+304+896=2500

6. 800 =800

б) по столбцам:

1. 100+2000 =2100

2. 50+550+1300=1900

3. 1250+800 =2050

4. 304 =304

5. 896 =896

Проверка на число занятых клеток.

;9=9, т.е. решение верное и невырожденное.

Вычисление значения целевой функции.

 

Z= 44*100+41*50+42*1250+43*2000+26*550+

+19*1300+22*304+0*896+44*800=225838

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

Вычислим потенциалы. За первый потенциал возьмем =100, все остальные потенциалы вычисляем для занятых клеток по формуле . Для свободных клеток вычисляем оценки . Результаты расчетов заносим в табл.12.

 

 

Таблица 12

Потенциалы и оценки для опорного решения задачи

  №           5(ф)
         
1     -   + 2   22
   
 
 


  -1 -43 -21
  115   -1
 
 


  0 0 -7
5 122 18   -4 + 19   -3 - 22    
  98   -3 -3     -1   -24

План не оптимален, так как в клетке (1;4) =2.

Zk=144*2100+141*1900+142*2050+144*304+122*896+

+(100*1400+101*2000+115*550+122*2500+98*800)=225838

Улучшение опорного плана

Строим замкнутый прямоугольный цикл для клетки (1,4) с оценкой =2 (табл.12). Проставляем знаки «+» и «-», начиная с испытуемой клетки. Среди отрицательных вершин выбираем наименьшее значение хij, (хmin=50), это тот ресурс, который перемещается по циклу (прибавляется или вычитается в зависимости от проставленных знаков в вершинах цикла). Таким образом, получаем новые значения переменных хij (новое решение задачи). Результаты описанных действий сведем в табл.13.

 

Таблица 13

Улучшенное на 2-м шаге решение задачи

  №           5(ф)
         
1       -2 - +   -24
   
 
 


 
 


-2

   -1 -45 -23
3     - 26   +     -7
5     -2 + 19     -1 -1 - 22    
    98   -3 -5   -3 -26

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

а) по строкам:

1. 100+1250+50 =1400

2. 2000=2000

3. 550=550

5. 1350+254+896=2500

6. 800=800

б) по столбцам:

1. 100+2000=2100

2. 550+1350=1900

3. 1250+800=2050

4. 50+254=304

5.896=896

Значение целевой функции определяется по формуле:

(для задачи на максимизацию должно выполняться условие: ).

2*50=100, где оценка испытуемой клетки, -перемещаемая поставка.

Z2=225838+100=225938

Дополнительно для контроля значение целевой функции рассчитывается по формуле: 44*100+42*1250+46*50+43*2000+26*550+19*1350+

+22*254+44*800=225938.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |

Поиск по сайту:

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