Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Топ:
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Интересное:
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Дисциплины:
2017-12-21 | 328 |
5.00
из
|
Заказать работу |
|
|
Все дв. оценки ≥ 0. Но дв. оценки – это взятые с противоположным знаком коэффициенты выражения ц.ф. через свободные неизвестные. Значит, сами эти коэффициенты ≤ 0. Поэтому, как только любая из свободных неизвестных примет положительное значение – целевая функция уменьшается. А это и означает, что она максимальна при нулевых значениях св.неизвестных, т.е. для данного базисного решения. + 22 вопрос, тока min меняем на max
22)Сформулировать и доказать критерий оптимальности решения задачи линейного программирования при отыскании минимума линейной функции симплексным методом. В частном случае общей задачи ЛП система уравнений имеет предпочитаемый вид, при этом правые части всех уравнений неотрицательны.
Допустим необходимо минимизировать целевую функцию L=c1x1+c2x2+...cnxn (1), при условиях:
x1 + g1,m+1xm+1 +... + g1nxn = h1,
x2 + g2,m+1 xm+1 +... + g2nxn = h2, (2)
............
xm + gm,m+1 xm+1 +... + gmnxn = hm
и xj≥0, j = 1,2,...n (3).
Для решения такой задачи применяется симплексный метод линейного программирования.
Одним из допустимых решений задачи ЛП будет базисное неотрицательное решение системы (2): x1=h1, x2=h2,...xm=hm, xm+1=0,...xn=0 (4), ему соответствует значение целевой ф-ии равное:
L0=c1h1+c2h2+...cmhm+cm+1*0+...+cn*0 = ci hi (5).
Надо исследовать, является ли базисное неотрицательное решение (4) оптимальным,т.е. является ли значение (5) наименьшим из всех возможных значений целевой ф-ии (1), отвечающих различным неотрицательным решениям системы (2).
Учитывая, что система уравнений (2) имеет предпочитаемый вид, находим для нее общее решение: xi=hi-gi,m+1xm+1-...-ginxn, i=1,2,...,m (6). Если свободным неизвестным придавать какие-нибудь неотрицательные значения, то будем получать различные решения системы (2), среди которых нас интересуют только неотрицательные. Подставляя их компоненты в линейную форму (1), можно подсчитать соответствующие значения целевой функции. Очевидно, чтобы легче было следить за поведением целевой функции, целесообразно выразить ее только через свободные неизвестные.
|
Если переписать выражение (1) в виде:
- L+c1x1+c2x2+...cmxm+ cm+1xm+1+...+cnxn=0 (7). Для того чтобы исключить базисные неизвестные из этого уравнения, достаточно умножить первое уравнение системы (2) на c1, второе на c2 и т.д., сложить полученные произведения и из результата вычесть уравнение (7). Получим L+∆m+1xm+1+...+∆nxn=L0 (8), где ∆j = c1g1j + c2g2j +... + cmgmj - cj, j=1,2,...n (9) или ∆j = zj - cj, zj= cigij, j=1,2,...n (9a).
Из выражения следует, что базисное решение x1=h1, x2=h2,...xm=hm, xm+1=0,...xn=0 (2) является оптимальным решением задачи ЛП
Базисное решение является оптимальным решением задачи ЛП тогда и только тогда, когда в уравнении среди коэффициентов при неизвестных нет ни одного положительного, т. е. условие оптимальности имеет вид ∆j≤0, j=1,2,…,n.
Если же хотя бы один из коэффициентов при свободных неизвестных равен нулю, то будут и небазисные оптимальные решения. Очевидно, оптимальных решений будет еще больше, если среди коэффициентов при свободных неизвестных в уравнении (8) окажется несколько нулевых.
|
|
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!