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

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

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой...

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

2017-12-21 325
Сформулировать и доказать критерий оптимальности решения задачи линейного программирования при отыскании максимума линейной функции симплексным методом. 0.00 из 5.00 0 оценок
Заказать работу

Все дв. оценки ≥ 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) окажется несколько нулевых.


Поделиться с друзьями:

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...

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

Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...

Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...



© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!

0.006 с.