Эксперт по сдаче вступительных испытаний в ВУЗах
ПРАКТИЧЕСКАЯ РАБОТА №2.
ОПТИМИЗАЦИЯ ПЛАНА ВЫПУСКА ПРОДУКЦИИ МЕТОДОМ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Линейное программирование (ЛП), изучает методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием оптимальности.
Экономико-математическая модель любой задачи линейного программирования включает:
целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать;
ограничения в виде системы линейных уравнений или неравенств;
требование неотрицательности переменных.
В общем виде модель записывается следующим образом:
целевая функция:
F = c1х1 + c2х2+……cnхn → max (min) (2.1)
ограничения:
a11x1 + a12x2 + … + a1nxn {≤ = ≥} b1
a21x1 + a22x2 + … + a2nxn {≤ = ≥} b2,
………………………………. (2.2)
am1x1 + am2x2 + … + amnxn {≤ = ≥} bm;
требование неотрицательности:
xi ≥ 0, i = 1,n (2.3)
При этом
aij, bi, cj ( ) — заданные постоянные величины.
Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3). Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) — прямыми.
Вектор , удовлетворяющий ограничениям (2.2) и (2.3), называется
допустимым решением (планом) задачи линейного программирования. План
, при котором функция (2.1) достигает своего максимального (минимального) значения, называется
оптимальным.
Матричная запись задачи ЛП имеет вид:
Ах {≤ = ≥} в
х ≥ 0
F = c x → max (min)
Здесь
А – матрица коэффициентов,
х – столбец переменных,
в— столбец правых частей,
с — строка коэффициентов целевой функции.
С каждой задачей линейного программирования тесно связана другая задача линейного программирования — двойственная задача (их так и называют — пара двойственных задач):
Прямая задача Двойственная задача
а11х1 + а12х2+……а1nхn ≤ в1 а11у1 + а21у2+……аm1ym ≥ c1
а21х1 + а22х2+……а2nхn ≥ в2 а12y1 + а22y2+……аm2ym ≥ c2
…………………………… …………,,,,,,,,,,,,,……, (2.4)
аm1х1 + аm2х2+……аmnхn ≤ вm а1ny1 + а2ny2+……аmnyn ≥ cn
xi ≥ 0, i = 1,n yi ≥ 0, i = 1,m
F = c1х1 + c2х2+……cnхn → max G = b1y1 + b2y2+……bm→ min
Как было сказано выше, вектор
х, удовлетворяющий ограничениям задачи, называют
планом и совокупность таких векторов —
множеством планов. План называется
опорным , если он обращает в равенство хотя бы
n независимых ограничений
(2.2)—
(2.3) (в вершине пересекаются хотя бы
n граничных гиперплоскостей). Понятие опорного плана в задаче ЛП является очень важным поскольку как следует из теории
оптимальный план всегда является опорным.
На этом свойстве основан основной метод решения задачи ЛП — симплексный метод. Суть его состоит в упорядоченном переборе опорных планов. Алгоритм сводится к следующему:
- выбирается первоначальное опорное решение;
- выбранный план проверяется на оптимальность;
- если план не оптимален, осуществляется переход к лучшему плану;
- процедура повторяется до тех пор, пока не будет найдено оптимальное решение, либо определено что оптимального решения нет.
Алгоритм симплекс-метода реализован в среде Microsoft Excel, меню Сервис-Поиск решения. В соответствующих ячейках задаются коэффициенты целевой функции, ограничений и указывается, какая задача решается (max или min). Форма представления исходных данных и результатов решения приведены в прил. 3.
Менеджеру производственной фирмы требуется составить оптимальный по прибыли план выпуска запчастей двух видов, используя для этого ресурсы трех типов. Их запасы ограничены значениями
в1, в2, в3 соответственно. Пусть
а11, а12 количество ресурсов первого типа, расходуемых на запчасти каждого вида, соответственно. Аналогичный смысл имеют символы
а21, а22 и
а31, а32.
Ожидаемая прибыль от реализации одной запчасти каждого вида составляет
с1, с2 условных единиц, соответственно.
Требуется:
а) записать условия задачи в таблицу стандартной формы;
б) решить задачу графоаналитическим способом (на миллиметровке);
в) решить задачу табличным симплекс- методом
г) решить задачу в среде EXCEL
д) составить и решить двойственную задачу, указать дефицитные ресурсы, выяснить, как изменится оптимальная прибыль при увеличении запасов каждого из дефицитных ресурсов на 5 единиц, соответственно.
Исходные данные:
в1 = 300 — 5V,
в2 = 120-2V,
в3 = 252- V,
с1= 30,
с2 = 40,
а11= 12,
а12= 4,
а21 = 4,
а22 = 4 ,
а31 =3,
а3 2= 12.
