Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Лабораторная работа № 4 Решение задач оптимизации симплекс-методом
На основе алгоритма симплекс-метода создать работающее программное приложение в виде компонента для решения задач по отысканию максимума или минимума функции. Симплекс-метод решения задач линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный план, и каждый ее опорный план является невырожденным). Указанный переход возможен, если известен какой-нибудь исходный опорный план. Рассмотрим задачу, для которой этот план можно непосредственно записать. Пусть дана функция, для которой необходимо найти наибольшее или наименьшее значение, если значения всех неизвестных неотрицательные.
ƒ = C0 + C1x1 + C2x2 +...+ Cnxn
и система m линейных уравнений с n неизвестными. Это называется системой ограничений: a11x1 + a12x2 +...+ a1nxn = b1 a21x1 + a12x2 +...+ a2nxn = b2 ... am1x1 +am2x12 +...+ amnxn = bm
Целевую функцию представим в виде:
ƒ - C1x1-C2x2 -...-Cnxn = C0
Составим симплекс-таблицу.В дальнейшем будем считать, что ранг матрицы системы ограничений равен r. В системе ограничений выбран базис (основные неизвестные) x1,x2,...xn и коэффициенты в правой части не отрицательны. В этом случае система ограничений будет иметь вид: x1 +...+ a1,r+1xr+1 +...+ a1nxn = b1 x2 + a2,r+1xr+1 +...+ a2nxn = b2 ... xr+ ar,r+1xr+1 +...+ arnxn = br
Тогда целевая функция имеет вид: ƒ + Cr+1xr+1 + Cr+2xr+2 -...- Cnxn = C0 Нахождение оптимального плана симплекс-методом включает следующие этапы: 1. Находят опорный план. 2. Составляют симплекс-таблицу. В общем виде:
3. В нижней строчке симплекс-таблицы необходимо отыскать отрицательные числа (не считая коэффициент Со). Если таких чисел нет, то данное базисное решение является оптимальным. 4. Пусть элемент Сj<0,тогда в j-ом столбце необходимо найти положительный элемент. Если все коэффициенты этого столбца отрицательные, то решения не существует. 5. Если положительный коэффициент в j-ом столбце один, то выбранную строку с номером i надо поделить все коэффициенты на число aij.Результат деления записываем в новую симплекс-таблицу. Если же положительных коэффициентов несколько, необходимо составить отношение bi/aij и из полученных значений выбрать наименьшее, соответствующее i-ой строке.
6. В новой симплекс-таблице в столбце базисных неизвестных вместо xi пишется xj. Продолжается заполняться таблица. В столбце с номером j необходимо получить нули(включая строку с целевой функцией). Для этого надо умножить i-ую записанную строку на нужное число и сложить с остальными строками. В результате осуществился переход к новому базису, при этом значение целевой функции увеличилось.
|
||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2017-01-19; просмотров: 361; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.144.25.74 (0.004 с.) |