Поиск оптимальных плановых решений в АСУ можно свести к двум основным постановкам задач:
получение запланированного эффекта при минимуме затрат;
получение максимального эффекта при использовании заданных организацией ресурсов.
Механизм экономических отношений описывается целым рядом взаимосвязанных показателей: товарооборот, рентабельность, избытки обращения, ассортимент товаров, площадь торговых залов и подсобных помещений, количество квалифицированных работников, виды оборудования, товарные запасы, система обработки, система обработки документов, форма обслуживания потребителей и т. д.
На значение этих показателей влияют такие факторы как ритмичность, частота и объемы выпуска продукции, поставка ее заказчикам, ассортимент и качество продукции, наличие и исправность оборудования, количество персонала и т. д.
Все экономические показатели и факторы можно разделить на:
неуправляемые (zi,z2,-,Zi,-,Zm)\
управляемые (xl,x2,--;Xj,...,xn).
На этом основании целевую функцию можно записать в виде уравнения этих показателей с критерием оптимальности (extre-mum).
Постановка задачи завершается переводом задачи планирования с языка экономики на язык математики. Этот процесс связан с построением одного или нескольких математических уравнений или неравенств, которые в совокупности описывают функциональные связи критерия оптимальности с показателями ресурсов, факторами и неизвестными значениями управляемых показателей. Такая запись экономической задачи является экономико-математической.
Для представления экономической постановки задачи в виде математической модели линейного программирования необходимо целевую функцию представить в виде линейной формы, а связь с ограниченными ресурсами описать с помощью линейных уравнений или неравенств. Кроме того, вводится дополнительное ограничение — значения переменных не должны быть отрицательны, т.е. x1>0,x2>0,...,Xj>0,...,xn>0. В целом экономико-математическая формулировка и модель общей задачи линейного программирования (ОЗЛП) имеют следующий вид: найти max(min) линейной целевой функции:
при условиях ограничении:
ay, bj, Cj—заданные постоянные величины.
Стандартной задачей линейного программирования называют задачу, которая состоит в определении максимального (минимального) значения целевой функций (2.1), при выполнении условия (2.2) и (2.4), где к = 0 и е = п.
Канонической (или основной) задачей линейного программирования называют задачу, которая состоит в определении максимального (минимального) значения целой функции при выполнении условий (2.3) и (2.4).
Совокупность чисел Зс = (д:1,А"2,...,jc„), удовлетворяющих ограничениям, называется допустимым решением (или планом).
План х* = (х1*, х2*,хп*), при котором целевая функция задачи принимает max(min), называется оптимальным.
В случае, когда требуется найти min функции F(x) =
= (с,л-, +с2х2 +... + спхп), можно перейти к нахождению max функции
Ограничение — неравенство исходной ЗИП, имеющее вид «<», преобразуется в ограничение равенства с добавлением левой части дополнительной неотрицательной переменной. Ограничение-неравенство вида «>» преобразуется в ограничение-равенство вычитанием из левой части дополнительной неотрицательной переменной.
Если ограничение задачи отражает наличие и равенство производственных ресурсов, то значение дополнительной переменной в плане задачи, записанной в форме основной, равно объему неиспользуемого соответствующего ресурса.
Запишем в ОЗЛП ограничения (2.3) в векторной форме.
Х,А| + Х2А2 + ...+ ХпАп = В, (2.5)
где A\,Ai,...,A„ и В m-мерные векторы-столбцы, составленные при неизвестных и свободных членах системы уравнений задачи. План х-(хх,х2,...,хп)называется опорным планом ОЗЛП,
если система векторов А/, входящих в разложение (2.5) с положительными коэффициентами Xj, линейно независима. Так как векторы Aj являются m-мерными, то из определения опорного плана следует, что число его положительных компонентов может превысить га. Опорный план называется невырожденным, если он содержит ровно га положительных компонентов.
Если в опорном плане число положительных компонентов меньше га, то план является вырожденным.
Часто в практике рыночных условий приходится решать задачи оптимизации объемов выпуска продукции и расширения ее номенклатуры для сохранения достигнутого уровня прибыли в условиях насыщения рынка. Часто необходимо принимать управляющие решения по выбору направлений деятельности предприятий, обеспечивающие max прибыль при ограниченных ресурсах. В этих целях применяют как простые способы (например, построение графиков, см. пример 1), так и более сложные, используя расчеты (см. примеры 2 и 3).
Пример 1.На предприятии выпускают два вида продукции: мотоциклы и велосипеды. Исходя из возможностей сборочного цеха, в нем могут собирать или 25 мотоциклов в день, или 100 велосипедов в день, либо комбинацию тех и других, определяемую приемлемыми трудозатратами. Склад может принять не более 70 изделий любого вида в сутки. Мотоцикл стоит в 2 раза дороже велосипеда. Требуется определить такой план выпуска продукции, который обеспечил бы предприятию наибольшую выручку.
Обозначим:
X— число выпускаемых мотоциклов в день.
Y— число выпускаемых велосипедов в день.
Т\ — время (в часах) производства одного мотоцикла.
Т2— время (в часах) производства одного велосипеда.
Из условия задачи следует, что Т\ = 4Т2.
Если завод работает круглосуточно, то при одновременном выпуске обоих изделий
АХ + Y < 24/Т2, но 24/Т2— max число производимых велосипедов, равное 100. Итак: 4Х+ Y < 100.
Поскольку а2— заданная положительная константа, то наибольшего значения следует добиваться от величины F = 2Х + Y.
Учитывая все условия задачи, приходим к ее математической модели: среди неотрицательных целочисленных решений системы линейных неравенств
найти такое, которое соответствует максимуму линейной функции F = 2Х + Y. (**)
Проще всего задачу решить геометрически (см. рис. 2.15). Построим на плоскости (х, у) область, соответствующую неравенствам (*) и условию не отрицательности х и у. Эта область М выделена жирной линией. Всякая ее точка удовлетворяет условию (*) и условию неотрицательности переменных. Пунктирные линии — семейство прямых, удовлетворяющее уравнению (**) (с разными значениями константы с). Вполне очевидно, что наибольшему возможному (max) значению F, вместе с предыдущими условиями, соответствует пунктирная линия, соприкасающаяся с областью М в точке Р. Этой линии соответствует F = 80. Пунктирные линии правее и левее не имеют общих точек с жирной линией. Координаты точки Р(10; 60) — искомый оптимальный план производства.
Пример 2.АО «Садко» ведет ежедневный учет:
обьемов выпускаемой продукции (кондитерских изделий — кг/сутки);
суммарных затрат на суточный выпуск;
выручки и суточного размера прибыли.
Эти данные по каждому цеху ежедневно представляют руководству в виде компьютерных распечаток.
Объемы выпуска определяются объемами поставок и стремлением получить максимально возможную прибыль при имеющихся мощностях предприятия.
Вопрос: Оптимальны ли сейчас объемы выпуска?
Оптимизация может быть осуществлена на базе модели линейного программирования. В качестве оптимизируемых параметров (управляемых переменных) Х1-Х8 выберем объемы выпуска продукции (в кг) из приведенных восьми переменных Xi. Для построения модели получим на основании данных номенклатуры таблицы удельные показатели производства, рассчитанные на единицу выпуска продукции. Удельная себестоимость определяется как себестоимость/объем, а удельная прибыль как прибыль/объем.
Целевая функция — суммарная себестоимость, которую следует минимизировать:
В такой постановке можно прийти к абсурдному выводу, что для достижения абсолютного минимума себестоимости ничего не надо производить. Поэтому следует ввести разумное ограничение — требование обеспечить достижение уровня суммарной суточной прибыли N = 20 569 руб. Ограничение G\(x) запишется так:
Математическая постановка задачи: найти управляющие переменные X\-Xiy обеспечивающие минимум целевой функции при выполнении ограничения.
Решение этой задачи в Microsoft Excel с помощью инструмента Поиск решения в меню Сервис аналогично приведенному в [11].
Анализируя полученные при расчетах данные, можно определить возможности сбыта.
Можно вычислить и альтернативные варианты сбыта.
Если рынок насыщен, коэффициенты возможного сбыта снижаются. Выход — расширение номенклатуры выпускаемой продукции. Строится модель с дополнительной номенклатурой.
Пример 3.Транспортная задача.
Классическая транспортная задача (задача Хитчкока-Куп-манса) — задача о поставке грузов от поставщиков к потребителям. Является типовой задачей для промышленных фирм, имеющих несколько предприятий, рынков сбыта и оптовых баз. Решение сводится к выбору оптимальных маршрутов, особенно когда фирмы ежемесячно пересматривают свои планы распределения продукции и номенклатура заказов меняется. Если нет других приоритетных целей, то задача состоит в том, чтобы минимизировать транспортные расходы.
Например, сталь вырабатывается на т заводах Р\, Р2, Р„. Ежемесячная выработка аи а2, а,„ (т/мес).Сталь надо доставить на предприятия Q\,Q2, <2ь причем bub2, bk— ежемесячная потребность этих предприятий, с — стоимость перевозки одной тонны стали с завода Р, на предприятие Qj.
Общее производство стали равно суммарной потребности в ней (производство): а\ + а2 + ... + ат = b] + Ь2 + ... + Ьк(потребность).
Необходимо составить план перевозок, при котором:
1) удовлетворялась потребность в стали предприятий <2ь Qi,
.... «2*;
2) с заводов Р„ ...,Ртвывозилась вся сталь;
3) общая стоимость перевозок была минимальной.
Обозначим через Ху количество стали (в тоннах), предназначенной к отправке с завода Р, на предприятие Qj. План перевозок состоит из (т; к) неотрицательных чисел Х{] (i = 1, 2, m; j = 1, 2, к). Схему перевозок стали см. в табл. 2.4.
Первое условие примет вид:
Раз стоимость перевозки одной тонны Р,- в Q, равна Су, то общая стоимость S всех перевозок равна:
Приходим к чисто математической задаче: Дана система т + к линейных алгебраических уравнений (2.6) и (2.7) с mк неизвестными (обычно mк m + к)и линейная функция S (2.8). Требуется среди всех неотрицательных решений данной системы найти такое, при котором функция S минимизируется. Практическое значение этой задачи огромно, ее умелое решение в масштабах страны могло бы экономить ежегодно огромные средства.
Решение транспортной задачи студентам рекомендуется выполнить в качестве самостоятельной работы. Пример выполнения приведен в Приложении 4.
