🗊Презентация Линейное программирование

Линейное программирование

Основные идеи линейного программирования возникли во время второй мировой войны в связи с поиском оптимальных стратегий при ведении военных операций. С тех пор они нашли широкое применение в промышленности, торговле и управлении - как в местных, так и в государственных масштабах. Этими методами можно решить многие (хотя не все) задачи, связанные с эффективным использованием ограниченных ресурсов.

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

Термин «линейное программирование» появился в 1951 году в работах американских ученых Дж. Б. Данцига, Тьяллинга Купманса (Koopmans). Слово «программирование» объясняется тем, что набор искомых переменных определяет программу (план) работы некоторого экономического объекта.

Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например: задача об оптимальном использовании ресурсов при производственном планировании; задача о смесях (планирование состава продукции); задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке"); транспортные задачи (анализ размещения предприятия, перемещение грузов).

В общем виде задача линейного программирования может быть сформулирована следующим образом. Дана линейная функция Ф = с1·х1 + с2·х2 + . . . +cj·xj+ . . . + сn·хn (1)

система линейных ограничений a11· x1 + a12·x2 + . . . + a1j·xj + . . . + a1n·xn = b1, a21· x1 + a22·x2 + . . . + a2j·xj + . . . + a2n·xn = b2, . . . . . . . . (2) a i1 · x1+ a i2·x2 + . . . + aij·xj + . . . + a in·xn = bi, . . . . . . . . am1· x1 + am2·x2 + . . .+ amj·xj + . . .+ amn ·xn = bm, и условия неотрицательности переменных xj ≥ 0, j = 1, n (3) где aij, bi и cj - заданные постоянные величины.

Задача об оптимальном использовании ресурсов при производственном планировании Общий смысл задач этого класса сводится к следующему. Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц. Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида (   ).

Прибыль, получаемая предприятием при реализации изделия j-го вида, равна cj. В планируемом периоде значения величин aij, biи cj остаются постоянными. Требуется составить такой план выпуска продукции, при реализации которого прибыль предприятия была бы наибольшей.

пример задачи этого класса Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор - в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В - 72 н-часа и участка С - 10 н-часов. Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?

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

По данному условию сформулируем задачу линейного программирования. Обозначим: x1- количество выпускаемых ежедневно хоккейных клюшек, x2- количество выпускаемых ежедневно шахматных наборов. Формулировка ЗЛП: = 2x1+ 4x2→ max;   4x1+ 6x2≤ 120, 2x1+ 6x2≤ 72, x2≤ 10;   x1≥ 0,   x2≥ 0.  

Каждое неравенство в системе функциональных ограничений соответствует в данном случае тому или иному производственному участку, а именно: первое - участку А, второе - участку В, третье - участку С.

Задача о смесях (планирование состава продукции). На птицеферме употребляются два вида кормов - I и II. В единице массы корма I содержатся единица вещества A, единица вещества В и единица вещества С. В единице массы корма II содержатся четыре единицы вещества А, две единицы вещества В и не содержится вещество C. В дневной рацион каждой птицы надо включить не менее единицы вещества А, не менее четырех единиц вещества В и не менее единицы вещества С. Цена единицы массы корма I составляет 3 рубля, корма II - 2 рубля. Составьте ежедневный рацион кормления птицы так, чтобы обеспечить наиболее дешевый рацион.