Студопедия — Решение. В данной модели система ограничений состоит из одного линейного уравнения и нелинейной целевой функции
Студопедия Главная Случайная страница Обратная связь

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

Решение. В данной модели система ограничений состоит из одного линейного уравнения и нелинейной целевой функции






В данной модели система ограничений состоит из одного линейного уравнения и нелинейной целевой функции.

1. Заполняем ячейки на рабочем листе необходимыми переменными, целевой функцией и ограничениями:

2. В окне "Параметры поиска решения" сбрасываем флаги "Линейная модель" (так как решаемая задача есть задача нелинейного программирования)" и "Неотрицательные значения" (в условии задачи нет ограничений на знаки переменных).

3. После нажатия кнопки "Выполнить" получаем ответ:

из которого следует, что минимальное значение целевой функции равно 17278 и достигается при x1 = 91 и x2 = 89.

 

 

ЗАДАНИЕ 3

Решить задачу транспортную задачу. Обозначения: Aj - запасы груза в i-м пункте отправления; Bj - потребности в грузе в j-м пункте назначения; Cij - тарифы перевозок единицы груза из i-го пункта отправления в j-м пункт назначения.

Решение:

Математическая модель транспортной задачи:

F = ∑∑cijxij, (1)

при условиях:

∑xij = ai, i = 1,2,…, m, (2)

∑xij = bj, j = 1,2,…, n, (3)

С целью составления двойственной задачи переменные xij в условии (2) заменим на u1, u2, ui,.., um, а переменные xij в условия (3) на v1, v2, vj,.., vn.

Поскольку каждая переменная xij входит в условия (2,3) и целевую функцию (1) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.

Требуется найти не отрицательные числа ui (при i = 1,2,…,m) и vj (при j = 1,2,..,n), обращающие в максимум целевую функцию

G = ∑aiui + ∑bjvj

при условии

ui + vj ≤ cij, i = 1,2,..,m; j = 1,2,..,n (4)

В систему условий (4) будет mxn неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть:

ui + vj ≤ cij, если xij = 0,

ui + vj = cij, если xij ≥ 0,

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

Числа ui, vj называются потенциалами. Причем число ui называется потенциалом поставщика, а число vj – потенциалом потребителя.

По первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G.

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

 

          Запасы
           
           
           
Потребности          

 

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 100 + 150 + 50 = 300

∑b = 75 + 80 + 60 + 85 = 300

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

 

          Запасы
           
           
           
Потребности          

Поиск первого опорного плана.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

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

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

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

Искомый элемент равен 1

Для этого элемента запасы равны 150, потребности 75. Поскольку минимальным является 75, то вычитаем его.

x21 = min(150,75) = 75.

 

x        
        150 - 75 = 75
x        
75 - 75 = 0        

 

Искомый элемент равен 2

Для этого элемента запасы равны 75, потребности 80. Поскольку минимальным является 75, то вычитаем его.

x22 = min(75,80) = 75.

 

x        
    x x 75 - 75 = 0
x        
  80 - 75 = 5      

 

Искомый элемент равен 3

Для этого элемента запасы равны 100, потребности 60. Поскольку минимальным является 60, то вычитаем его.

x13 = min(100,60) = 60.

 

x       100 - 60 = 40
    x x  
x   x    
    60 - 60 = 0    

 

Искомый элемент равен 4

Для этого элемента запасы равны 50, потребности 85. Поскольку минимальным является 50, то вычитаем его.

x34 = min(50,85) = 50.

 

x        
    x x  
x x x   50 - 50 = 0
      85 - 50 = 35  

 

Искомый элемент равен 5

Для этого элемента запасы равны 40, потребности 35. Поскольку минимальным является 35, то вычитаем его.

x14 = min(40,35) = 35.

 

x       40 - 35 = 5
    x x  
x x x    
      35 - 35 = 0  

 

Искомый элемент равен 7

Для этого элемента запасы равны 5, потребности 5. Поскольку минимальным является 5, то вычитаем его.

x12 = min(5,5) = 5.

 

x       5 - 5 = 0
    x x  
x x x    
  5 - 5 = 0      

 

 

          Запасы
    7[5] 3[60] 5[35]  
  1[75] 2[75]      
        4[50]  
Потребности          

 

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

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.

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

F(x) = 7*5 + 3*60 + 5*35 + 1*75 + 2*75 + 4*50 = 815

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v2 = 7; 0 + v2 = 7; v2 = 7

u2 + v2 = 2; 7 + u2 = 2; u2 = -5

u2 + v1 = 1; -5 + v1 = 1; v1 = 6

u1 + v3 = 3; 0 + v3 = 3; v3 = 3

u1 + v4 = 5; 0 + v4 = 5; v4 = 5

u3 + v4 = 4; 5 + u3 = 4; u3 = -1

 

  v1=6 v2=7 v3=3 v4=5
u1=0   7[5] 3[60] 5[35]
u2=-5 1[75] 2[75]    
u3=-1       4[50]

 

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij

(3;1): -1 + 6 > 3; ∆31 = -1 + 6 - 3 = 2

Выбираем максимальную оценку свободной клетки (3;1): 3

Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

          Запасы
    7[5][-] 3[60] 5[35][+]  
  1[75][-] 2[75][+]      
  3[+]     4[50][-]  
Потребности          

 

Цикл приведен в таблице (3,1; 3,4; 1,4; 1,2; 2,2; 2,1;). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

          Запасы
      3[60] 5[40]  
  1[70] 2[80]      
  3[5]     4[45]  
Потребности          

 

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

u1 + v3 = 3; 0 + v3 = 3; v3 = 3

u1 + v4 = 5; 0 + v4 = 5; v4 = 5

u3 + v4 = 4; 5 + u3 = 4; u3 = -1

u3 + v1 = 3; -1 + v1 = 3; v1 = 4

u2 + v1 = 1; 4 + u2 = 1; u2 = -3

u2 + v2 = 2; -3 + v2 = 2; v2 = 5

 

  v1=4 v2=5 v3=3 v4=5
u1=0     3[60] 5[40]
u2=-3 1[70] 2[80]    
u3=-1 3[5]     4[45]

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij. Минимальные затраты составят: F(x) = 3*60 + 5*40 + 1*70 + 2*80 + 3*5 + 4*45 = 805

Проверим оптимальность найденного плана по первой теореме двойственности (в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G). G = 0*100 -3*150 -1*50 + 4*75 + 5*80 + 3*60 + 5*85 = 805

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 3-й магазин (60), в 4-й магазин (40). Из 2-го склада необходимо груз направить в 1-й магазин (70), в 2-й магазин (80). Из 3-го склада необходимо груз направить в 1-й магазин (5), в 4-й магазин (45)

ЗАДАНИЕ 4

Решить задачу о назначении венгерским методом по известной матрице эффективностей.

Решение:

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

Составляем исходную таблицу (матрицу):

         
         
         
         
         

 

 

Этап 1. В каждой строке ищем минимальный элемент (выделяем жирным в таблице) и отнимаем от всех элементов строки. Получим:

         
         
         
         
         

 

         
         
         
         
         

 

 

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

         
         
         
         
         

 

         
         
         
         
         

 

Задачей является распределение всех подлежащих назначению единиц в клетки с нулевой стоимостью.

Этап 2. Выбираем строку с одним нулем (строка №1), выделяем нуль жирным и зачеркиваем (выделено серым) оставшиеся нулевые значения этого столбца (столбца №3). Выбираем строку с одним нулевым значением (строка №5), выделяем нуль. Выбираем строку с одним нулем (строка №3), выделяем нуль жирным и зачеркиваем (выделено серым) оставшиеся нулевые значения этого столбца (столбца №4). Выбираем строку с одним нулем (строка №4), выделяем нуль жирным и зачеркиваем (выделено серым) оставшиеся нулевые значения этого столбца (столбца №1).

Выбираем строку с одним нулевым значением (строка №2), выделяем нуль.

 

         
         
         
         
         

 

Получаем оптимальную матрицу назначений

         
         
         
         
         

 

 

Минимальное значение целевой функции: 1 +2+2+1 +2=8.

 







Дата добавления: 2015-04-16; просмотров: 350. Нарушение авторских прав; Мы поможем в написании вашей работы!



Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

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

Классификация и основные элементы конструкций теплового оборудования Многообразие способов тепловой обработки продуктов предопределяет широкую номенклатуру тепловых аппаратов...

Именные части речи, их общие и отличительные признаки Именные части речи в русском языке — это имя существительное, имя прилагательное, имя числительное, местоимение...

Типовые ситуационные задачи. Задача 1. Больной К., 38 лет, шахтер по профессии, во время планового медицинского осмотра предъявил жалобы на появление одышки при значительной физической   Задача 1. Больной К., 38 лет, шахтер по профессии, во время планового медицинского осмотра предъявил жалобы на появление одышки при значительной физической нагрузке. Из медицинской книжки установлено, что он страдает врожденным пороком сердца....

Типовые ситуационные задачи. Задача 1.У больного А., 20 лет, с детства отмечается повышенное АД, уровень которого в настоящее время составляет 180-200/110-120 мм рт Задача 1.У больного А., 20 лет, с детства отмечается повышенное АД, уровень которого в настоящее время составляет 180-200/110-120 мм рт. ст. Влияние психоэмоциональных факторов отсутствует. Колебаний АД практически нет. Головной боли нет. Нормализовать...

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

Studopedia.info - Студопедия - 2014-2024 год . (0.01 сек.) русская версия | украинская версия