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

Рис. 7

Этап 2.

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

Построим сначала графики функций W(k) и f(k). Последнее значение при шаге 50 и больше максимального рубежного значения возьмем 950.

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

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

=0,3+A4/500-КОРЕНЬ(A4/600),

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

=A2*B2,

и распространена на ячейки С3-С21.

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

Рис. 8

Рис. 9

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

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

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

Рис. 10

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

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

. (16)

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

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

 (17)

Исследуем эту функцию на максимум в интервале .

Первая и вторая производные исследуемой функции равны:

, (18)

. (19)

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

.

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

.

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

.

, .

Первый корень не удовлетворяет условию t ?0, поэтому не будем его рассматривать. Вычислим по второму значению t.

Найдем из (19) значение второй производной при k = k₂ = 576:

.

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

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

;

.

(млн.руб.).

ВЫВОД: Для оптимизации прибыли строительной фирме нужно нанять 576 работников и построить 44,7 тыс.кв.метров торговых площадей и 43,8 тыс.кв.метров жилых площадей. При этом фирма получит прибыль около 392,5 млн.рублей.

ЗАДАЧА №3

Условия задачи представлены в таблице:

Дополнительная возможность 3: покупка стройматериалов.

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

Строительная фирма имеет возможность постройки двух видов зданий: торговый комплекс (Т) или жилой дом (Ж). каждый вид сооружается в течение года. Для сооружения тысячи «торговых» квадратных метров требуется вложить 5 миллионов рублей, задействовать 7 рабочих и затратить 2 тысячи кубометров стройматериалов. Для сооружения тысячи квадратных метров «жилой» площади требуется вложить 2 миллиона рублей, задействовать 6 рабочих и затратить 8 тысяч кубометров стройматериалов. За каждую тысячу квадратных метров торговых площадей фирма получает в конце года доход 8 млн.рублей, а за каждую тысячу кв.метров жилой площади - 7 млн.рублей. на складах фирмы имеется 0 тысяч кубометров стройматериалов, в штате фирмы 880 рабочих, а собственный капитал фирмы составляет 605 млн. рублей. Кроме того, фирма может закупить стройматериалы на условиях оплаты после окончания года. При этом цена тысячи кубометров стройматериалов C (млн.руб.) зависит от объема закупки q (тыс.кубометров) следующим образом: млн.рублей если объем закупки не превышает 50 тыс.кубометров, и , если объем закупок больше.

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

РЕШЕНИЕ:

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

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

(1)

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

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

(2)

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

, (3)

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

.

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

(4)

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

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

, (5)

(6)

, (7)

рассматривая k как параметр (известную величину). В результате решения задачи (5) - (7) получаем оптимальный план, в котором x₁^*, x₂^* и Z^* зависят от q. На втором этапе решаем задачу нелинейного программирования. Ищем q^* из задачи:

, (8)

. (9)

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

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

(10)

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

для всех . (11)

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

, (12)

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

;

; ; ; ; ; .

Здесь векторы имеют базисный вид, т.е. являются единичными в одном из компонентов и нулевыми во всех остальных компонентах. Их и возьмем в качестве первоначальных базисных векторов. Данная задача является классической задачей оптимального использования ресурсов, и поэтому в ней всегда имеется возможность выделить первоначальные базисные вектора. Составим первоначальную симплекс-таблицу:

Таблица 11