Читать курсовая по информатике, вычислительной технике, телекоммуникациям: "Симплексный метод решения ЗЛП" Страница 3

(Назад) (Cкачать работу)

Линейное программирование — решение линейных уравнений (уравнений первой степени) посредством составления программ и применения различных методов их последовательного решения, существенно облегчающих расчеты и достижение искомых результатов.

Условия задачи на оптимум и цель, которая должна быть достигнута, могут быть выражены с помощью системы линейных уравнений. Поскольку уравнений меньше, чем неизвестных, задача обычно имеет не одно, а множество решений. Найти же нужно одно, согласно терминологии математиков, экстремальное решение.В задаче по оптимизации выпуска фанеры Канторович представил переменную, которую следовало максимизировать в виде суммы стоимостей продукции, производимой всеми станками. Ограничители были представлены в форме уравнений, устанавливающих соотношения между всеми затрачиваемыми в производстве факторами (древесиной, клеем, электроэнергией, рабочим временем) и количеством выпускаемой продукции (фанеры) на каждом из станков. Для показателей факторов производства были введены коэффициенты, названные разрешающими множителями, или мультипликаторами. С их помощью разрешается поставленная задача. Если известны значения разрешающих множителей, то искомые величины, в частности, оптимальный объем выпускаемой продукции, могут быть сравнительно легко найдены.

.Для любой задачи линейного программирования существует сопряженная ей, или двойственная, задача. Если прямая задача заключается в минимизации целевой функции, то двойственная — в максимизации.Двойственные оценки дают принципиальную возможность соизмерять не только ценовые, затратные показатели, но и полезности. При этом двойственные, взаимосвязанные оценки соответствуют конкретным условиям. Если изменяются условия, то изменяются и оценки. В известной мере поиск оптимума — это определение общественно необходимых затрат, учитывающих, с одной стороны, трудовые, стоимостные затраты, а с другой стороны, общественные потребности, полезности продукта для потребителей.

1.2 Общий вид задач линейного программирования В общем случае задача линейного программирования может быть записана в таком виде(формула 1.1) Z(X)=c1x1+c2x2+…+cnxn→ max(min),(1.1)

a11x1+a12x2+…+a1nxn=b1,

…………………………

ai1x1+ai2x2+…+ainxn=bi,

a(i+1)1x1+a(i+1)2x2+…+a(i+1)nxn≤bi+1 (1.2)

………………………..

am1x1+am2x2+…+amnxn≤bm xj≥0, j=1,2,…,t; t≤n. (1.3)

Данная запись означает следующее: найти экстремум целевой функции (1.1) и соответствующие ему переменные X=(X1, X2,...,Xn) при условии, что эти переменные удовлетворяют системе ограничений (1.2) и условиям неотрицательности (1.3).

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X1, X2,...,Xn), удовлетворяющий системе ограничений и условиям неотрицательности.

Множество допустимых решений (планов) задачи образует область допустимых

Похожие работы