Основы построения автоматизированных информационных систем - Гвоздева В. А.
ISBN 978-5-8199-0315-5
Скачать (прямая ссылка):
п
(2.1)
при условиях ограничении:
104
п
HaUxJ
<bh і = ІД;
(2.2)
./=1
(2.3)
X1 > OJ = \,e, n;
(2.4)
ay, bj, Cj—заданные постоянные величины.
Стандартной задачей линейного программирования называют задачу, которая состоит в определении максимального (минимального) значения целевой функций (2.1), при выполнении условия (2.2) и (2.4), где к = 0 и е = п.
Канонической (или основной) задачей линейного программирования называют задачу, которая состоит в определении максимального (минимального) значения целой функции при выполнении условий (2.3) и (2.4).
Совокупность чисел X = (X1,X2,—,X11), удовлетворяющих ограничениям, называется допустимым решением (или планом).
План X* = (X1*, X2*,Xn*), при котором целевая функция задачи принимает max(min), называется оптимальным.
В случае, когда требуется найти min функции F(x) =
= (с,л-, +с2х2 +... + C11Xn), можно перейти к нахождению max функции
Ограничение — неравенство исходной ЗИП, имеющее вид «<», преобразуется в ограничение равенства с добавлением левой части дополнительной неотрицательной переменной. Ограничение-неравенство вида «>» преобразуется в ограничение-равенство вычитанием из левой части дополнительной неотрицательной переменной.
Если ограничение задачи отражает наличие и равенство производственных ресурсов, то значение дополнительной переменной в плане задачи, записанной в форме основной, равно объему неиспользуемого соответствующего ресурса.
F1 (х) = -F(x) = -C1A1 - с2х2 -... - спхп; так как min F(x) = - max F1 (х).
105
Запишем в ОЗЛП ограничения (2.3) в векторной форме.
Xx Ii +X2A2 + ...+X11An = В, (2.5)
где А\, Аг,An и В m-мерные векторы-столбцы, составленные при неизвестных и свободных членах системы уравнений задачи. План X -(X1, X2,.-,Xn)называется опорным планом ОЗЛП,
если система векторов Aj, входящих в разложение (2.5) с положительными коэффициентами Xj, линейно независима. Так как
векторы Aj являются m-мерными, то из определения опорного плана следует, что число его положительных компонентов может превысить га.
Опорный план называется невырожденным, если он содержит ровно га положительных компонентов.
Если в опорном плане число положительных компонентов меньше га, то план является вырожденным.
Часто в практике рыночных условий приходится решать задачи оптимизации объемов выпуска продукции и расширения ее номенклатуры для сохранения достигнутого уровня прибыли в условиях насыщения рынка. Часто необходимо принимать управляющие решения по выбору направлений деятельности предприятий, обеспечивающие max прибыль при ограниченных ресурсах. В этих целях применяют как простые способы (например, построение графиков, см. пример 1), так и более сложные, используя расчеты (см. примеры 2 и 3).
Пример 1. На предприятии выпускают два вида продукции: мотоциклы и велосипеды. Исходя из возможностей сборочного цеха, в нем могут собирать или 25 мотоциклов в день, или 100 велосипедов в день, либо комбинацию тех и других, определяемую приемлемыми трудозатратами. Склад может принять не более 70 изделий любого вида в сутки. Мотоцикл стоит в 2 раза дороже велосипеда. Требуется определить такой план выпуска продукции, который обеспечил бы предприятию наибольшую выручку.
Обозначим:
X— число выпускаемых мотоциклов в день.
Y— число выпускаемых велосипедов в день.
Т\ — время (в часах) производства одного мотоцикла.
T2 — время (в часах) производства одного велосипеда.
106
Из условия задачи следует, что T1 = 4T2.
Если завод работает круглосуточно, то при одновременном выпуске обоих изделий
TxX + T2Y 24 или AT2X + T2Y < 24;
AX + Y < 2AIT2, но 24/Г2 — max число производимых велосипедов, равное 100. Итак: AX+ Y < 100.
Еще одно условие — ограниченная емкость склада
X + Y < 70.
Обозначим цену мотоцикла щ (руб.), цену велосипеда — а2 (руб.). По условию: а\ = 2а2.
Следовательно, общая цена дневной продукции S
S = axX+ Q2Y = Ia2X + a2Y = а2(2Х + Y).
Поскольку а2 — заданная положительная константа, то наибольшего значения следует добиваться от величины F = IX + Y.
Учитывая все условия задачи, приходим к ее математической модели: среди неотрицательных целочисленных решений системы линейных неравенств
4X+К*? 100;
(*)
X + Y<70;
найти такое, которое соответствует максимуму линейной функции F = 2Х + Y. (**)
Проще всего задачу решить геометрически (см. рис. 2.15). Построим на плоскости (х, у) область, соответствующую неравенствам (*) и условию не отрицательности х и у. Эта область M выделена жирной линией. Всякая ее точка удовлетворяет условию (*) и условию неотрицательности переменных. Пунктирные линии — семейство прямых, удовлетворяющее уравнению (**) (с разными значениями константы с). Вполне очевидно, что наибольшему возможному (max) значению F, вместе с предыдущими условиями, соответствует пунктирная линия, соприкасающаяся с областью M в точке Р. Этой линии соответствует F = 80. Пунктирные линии правее и левее не имеют общих точек с жирной линией. Координаты точки Р(10; 60) — искомый оптимальный план производства.
107
Рис. 2.15. Графическое решение задачи примера 1
