Методы оптимизации в задачах планирования производства

Введение.

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

Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника; Ганнибалу, чтобы разбить римлян при Каннах, командуя вдвое мень­шей армией, нужно было действовать очень обдуманно.

Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся «на глазок» (те­перь, впрочем, зачастую тоже). В середине XX века был создан специальный математиче­ский аппарат, помогающий это делать «по науке». Соответствующий раздел математики называется математическим программированием. Слово «программирование» здесь и в аналогичных терминах («линейное программирование, динамическое программирование» и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово «планирование».

Что же такое линейное программирование? Этим термином называют колоссаль­ный раздел науки, посвященный линейным оптимизационным моделям, то есть построе­нию, теоретическому и численному анализу и решению задач, в которых требуется найти оптимальное значение, т. е. максимум или минимум, некоторой системы показателей в процессе, поведение и состояние которого описывается той или иной системой линейных неравенств.

Итак, термин в названии восходит к общему смыслу слова ''программа'' - план, ру­ководство к действию и как таковая, дисциплина ''линейное программирование'' представ­ляет собой математическую теорию определения наилучших планов действия в опреде­ленных экономических ситуациях.

Что это за ситуации? В первую очередь их можно охарактеризовать наличием од­ной хорошо определенной цели или критерия. В этом случае не годится стремление ''чтобы все было хорошо'', цель должна измеряться в определенных единицах и однознач­но определяться выбранным планом действий. Более подходящим примером может быть доход от деятельности предприятия, а планом действий в данном случае может быть про­изводственная программа предприятия.

Поэтому, цель данной работы раскрыть не только сущность линейного программи­рования, но и найти возможность его использования в социальной сфере.

Условия задачи:

Дополнительная возможность 1: получение ссуды.

То есть задача формулируется следующим образом:

Строительная фирма имеет возможность постройки двух видов зданий: торговый комплекс или жилой дом. Каждый вид сооружается в течение года. Для сооружения тысячи «торговых» квадратных метров требуется вложить 7 миллионов рублей, задействовать 5 рабочих и затратить 7 тысяч кубометров стройматериалов. Для сооружения тысячи квадратных метров «жилой» площади требуется вложить 10 миллионов рублей, задействовать 6 рабочих и затратить 2 тысячи кубометров стройматериалов. За каждую тысячу квадратных метров торговых площадей фирма получает доход 12 млн. рублей, а за каждую тысячу кв. жилой площади – 14 млн. рублей. На складах фирмы имеется 560 тысяч кубометров стройматериалов, в штате фирмы 700 рабочих, а собственный капитал фирмы составляет 0 рублей. Кроме того, фирма может взять кредит в банке в размере у млн. руб., при этом в конце года фирма платит за кредит процентов годовых, если сумма кредита превышает 50 млн. руб. и процентов годовых, если сумма кредита меньше.

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

РЕШЕНИЕ

Составим экономико-математическую модель задачи. Для этого обозначим х₁ – количество тысяч квадратных метров торговых площадей, а х₂ – количество тысяч квадратных метров жилой площади построенных фирмой. Кредит у (в млн. руб.), полученный фирмой в банке может быть любым неотрицательным числом.

Эта задача является задачей оптимального использования ресурсов. Система ограничений, получаемая из ограниченности ресурсов, имеет вид:

(1)

где справа стоит количество каждого вида ресурса, которое не может быть превышено в процессе деятельности фирмы. Эти ограничения являются нетривиальными.

Далее, х₁ и х₂ являются неотрицательными (нельзя построить отрицательное число квадратных метров зданий), что дает нам тривиальные ограничения задачи:

(2)

Наконец, функция цели (или целевая функция) представляет собой общую стоимость произведенной продукции, и эта функция в поставленных ограничениях оптимизируется на максимум:

(3)

где функция отражает выплаты банку. Она связана с процентной ставкой Р и суммой кредита у следующим соотношением:

Согласно условию задачи получаем:

(4)

Из-за нелинейности функции (4) к данной задаче нельзя применить методы линейного программирования непосредственно. Задача же нелинейно го программирования (1)–(4) достаточно сложна.

Однако данную проблему можно разбить на два этапа. На первом определяем оптимальный план следующей задачи линейного программирования:

(5)

(6)

(7)

рассматривая у как параметр (известную величину). В результате решения задачи (5)–(7) получаем оптимальный план, в котором х₁^*, х₂* и Z* зависят от у.

На втором этапе решаем задачу нелинейного программирования. Ищем у из задачи

(8)

(9)

Задача (8), (9), (4) – одномерная задача, и ее можно легко решить графически с последующим аналитическим уточнением.

ЭТАП 1

Для решения задачи симплекс–методом приведем систему (5)–(7) к каноническому виду, введя дополнительные балансовые переменные х₃, х₄, х₅, которые означают неиспользованное количество денег, рабочих и стройматериалов соответственно. При этом неравенства (6) преобразуются в уравнения:

(10)

По смыслу балансовые переменные здесь также неотрицательны, поэтому тривиальная система неравенств принимает вид:

для всех j = 1,5. (11)

Введем балансовые переменные и в целевую функцию с коэффициентами равными нулю:

(12)

Задача в форме (12), (10), (11) имеет канонический вид. Соответствующая ей векторная форма записи будет такова:

Здесь векторы Р₃, Р₄ и P₅ имеют базисный вид, т.е. являются единичными в одном из компонентов и нулевыми во всех остальных компонентах. Их и возьмем в качестве первоначальных базисных векторов. Данная задача является классической задачей оптимального использования ресурсов, и поэтому ней всегда имеется возможность выделить первоначальные базисные вектора.

Составим первоначальную симплексную таблицу:

Таблица 1.

Ведущим столбцом будет второй столбец, так как ему в индексной строке соответствует самое отрицательное число. При определении ведущей строки среди симплексных отношений а_iр, полученных в последнем столбце, нужно выбрать наименьшее. Очевидно, что а₃₂, > a₂₂ при любых значениях у. Соотношение между а₁₀ и а₁₂ зависит от у.

1. Рассмотрим случай у/10?700/6. Тогда у?3500/3 и ведущей строкой будет вторая строка:

Таким образом, в базис входит вектор Р₂, а покидает его Р₄.

Пересчитаем таблицу по всем правилам пересчета симплексных отношений. Получаем новую симплексную таблицу:

В индексной строке есть отрицательный элемент, поэтому проведём следующую итерацию:

Так как в индексной строке все элементы неотрицательны, то данный план является оптимальным. Таким образом, при у?3500/3 план х₁* = 245/4, x₂* = 525/8, х₃* = (у–1085), х₄* = 0, х₅* = 0, а значение функции равно Z* = 6615/4.

2. Теперь рассмотрим случай у < 3500/3. Тогда в таб. 1 ведущей строкой будет первая строка:

В базис входит вектор Р₂, а покидает его Р₃. Пересчитывая, получаем новую симплексную таблицу:

Таблица 2.

Ведущим столбцом будет второй, так как ему в индексной строке соответствует единственное отрицательное число. При определении ведущей строки среди симплексных отношений a_ip, полученных в последнем столбце, нужно выбрать наименьшее. Все они зависят от у. Определим, в каких интервалах изменения у минимально каждое из чисел a_jp. Для этого рассмотрим три неравенства:

Проанализировав результат, приходим к следующим выводам:

а₁₁ = у/7 меньше остальных симплексных отношений при у ? 560;

а₂₁ = 875–3у/4 меньше остальных отношений при у > 1085;

а₃₁ = 100–у/28 меньше остальных отношений при 560 < у < 1085.

Рассмотрим все три случая с учетом условий у < 3500/3 и у ? 0.

2.1. 0 ? у ? 560. Тогда в таб. 2 ведущей строкой будет первая строка.

В базис входит вектор Р₁, а покидает его Р₂. Пересчитывая, получаем новую симплексную таблицу:

Так как в индексной строке все элементы неотрицательны, то полученный план является оптимальным. Таким образом, при 0 ? у ? 560 оптимален план: х₁* = у/7, х₂*=0, х₃*=0, х₄*=(700–5у/7), х₅* = (560–у), а значение целевой функции равно Z* = 12у/7.

2.2. 1085 ? у < 3500/3. Тогда в таб. 2. ведущей строкой будет вторая строка:

В базис входит вектор Р₁, а покидает его Р₄,. Пересчитывая, получаем новую симплексную таблицу:

Ведущим столбцом будет третий столбец, так как ему в индексной строке соответствует отрицательное число.

Так как в индексной строке все элементы неотрицательны, то полученный план является оптимальным. Таким образом, при 1085 ? у < 3500/3 оптимален план: х₁* = (245/4), х₂*=(525/8), х₃*= у–1085, х₄*=0, х₅* =0, а значение целевой функции равно Z* = 6615/4.

2.3. 560 < у < 1085. Тогда в таб. 2. ведущей строкой будет третья строка:

В базис входит вектор P₁, а покидает его P₅. Пересчитывая, получаем новую симплексную таблицу:

Так как в индексной строке все элементы неотрицательны, то полученный план является оптимальным. Таким образом, при 560 < у < 1085 оптимален план х₁* = (100–у/28), х₂*=(у/8–70), х₃*=0, х₄*=(620–4у/7), х₅*=0, а значение целевой функции равно Z* = (37у/28+220).

Объединяя случаи 1, 2.1, 2.2, 2.3 решение можно записать в виде:

(13)

(14)

(15)

Представим эти результаты на графиках с использованием офисной программы MS Excel (Рис.1,2).

В частности, для построения графика функции Z(у) используем следующую таблицу:

где в ячейку В2 введена формула:

=ЕСЛИ(А2<560;(12/7)*А2;ЕСЛИ(А2<1085;(37/28)*А2+220;ЕСЛИ(А2<(3500/3);6615/4; 6615/4))),

и распространена на ячейки ВЗ–В6.

Значения в столбце А для краткости и наглядности выбраны соответственно рубежным значениям формул (12)–(15). Последнее значение (1300) может быть выбрано любым большим 3500/3.

Очевидно, что сумма кредита не должна превышать 3500/3 млн., так как все средства, большие 3500/3 млн. руб. при оптимальном плане не используются.

ЭТАП 2

Задачу нелинейного программирования предварительно решим графически с использованием офисной программы MS Excel.

Построим сначала графики функции Р(у) и f(y). Последнее значение берется тем же, что и для первого этапа.

Фрагмент таблицы выглядит так:

где в столбце В, в строках 2 и 3 введено число 18,56, а в 4-й строке записана формула:

=20-0,03*А4+0,000025*СТЕПЕНЬ(А4;2),

и распространена на ячейки В5–В28. В ячейку С2 введена формула:

=А2*(1+В2/100), и распространена на ячейки СЗ–С28.

Полученные графики приведены на рис. 3,4.

Объединим полученные результаты. Для этого добавим во вторую таблицу столбец с вычислением функции Z(у) из первой Excel-таблицы. После этого составим разность значений Z'(y) и f(y).

Фрагмент итоговой таблицы выглядит так:

График разности функций Z*(y) и f(y) приведен на рис. 5.

Как видно из графика и по таблице, оптимальное значение прибыли достигается при сумме кредита, лежащей между 900 и 1050 млн. руб. Для получения точного значения, проведем аналитическое исследование прибыли на этом интервале.

Согласно формуле (15), сумма оптимального дохода на интервале 560 ? у < 1085, в который попадает и наш исследуемый интервал, задается формулой:

(16)

Тогда из формул (4) и (16) получаем, что на интересующем нас интервале прибыль равна

Раскрывая скобки, получаем

Исследуем эту функцию на максимум на интервале 560 ? у < 1085. Первая и вторая производные исследуемой функции равны:

(17)

(18)

Приравнивая первую производную нулю, из (18) получаем квадратное уравнение:

Для удобства умножим все уравнение на –10⁸. Получим:

Корни этого уравнения определяем по формуле:

Второй корень лежит вне исследуемого промежутка, и его рассматривать не будем.

Найдем из (19) значение второй производной при у = у_х = 967:

Так как вторая производная отрицательна, то точка у = 967 является точкой максимума (что было видно и по графику). Таким образом, оптимальная сумма кредита равна 967 млн. руб.

Из формул (13), (14), (17) определяем оптимальный план строительства и значение прибыли при найденной оптимальной сумме кредита:

(млн. руб.).

ВЫВОД: Для оптимизации прибыли строительной фирме нужно взять кредит в размере 967 млн. рублей и построить 65,5 тыс. кв. метров торговых площадей и 50,9 тыс. кв. метров жилых площадей. При этом фирма получит прибыль около 391,9 млн. руб.

Заключение.

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

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

Кроме того, в данной работе не только исследована, на и доказана выгодность про­ведения расчётов задач линейного программирования с использованием компьютерной техники и, в частности, электронных таблиц Excel.

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