Симплекс-метод. 2

    Введение.

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

    Целью математического программирования является создание, где это возможно, аналитических методов определения решения, а при отсутствии таких методов – создание эффективных вычислительных способов получения приближенного решения.

    Наконец, заметим, что наименование предмета – “математическое программирование” – связано с тем, что целью решения задач является выбор программы действий.

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

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

    Дополнительная  возможность 2: нанять новых рабочих.

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

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

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

    РЕШЕНИЕ 

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

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

      (1)

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

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

      (2)

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

      (3)

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

      (4)

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

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

      (5)

      (6)

      (7)

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

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

      (8)

      (9)

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

    ЭТАП 1 

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

      (10)

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

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

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

      (12)

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

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

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

    Таблица 1.

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

    1. Рассмотрим случай k/5≥80. Тогда k≥400 и ведущей строкой будет третья строка:

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

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

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

    1.1. Рассмотрим случай 7k/32–175/2≥35. Тогда k≥560 и ведущей будет вторая строка:

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

    Так как в индексной строке все  элементы неотрицательны, то данный план является оптимальным. Таким образом, при k≥560 план х₁* = 70, x₂* = 35, х₃* = (k–560), х₄* = 0, х₅* = 0, а значение функции равно Z* = 630. 

    1.2. Рассмотрим случай когда 400≤k<560. Ведущей будет первая строка:

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

    Так как в индексной строке все  элементы неотрицательны, то данный план является оптимальным. Таким образом, при 400≤k<560 план х₁* = (105–k/16), x₂* = (7k/32–175/2), х₃*=0, х₄*=(980–7k/4), х₅* = 0, а значение функции равно Z* = (7k/16+385). 

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

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

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

    Объединяя случаи 1.1, 1.2, 2 решение можно записать в виде:

      (13)

      (14)

      (15)

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

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

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

    =ЕСЛИ(А2<400;(7/5)*А2;ЕСЛИ(А2<560;(7/16)*А2+385;630)),

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

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

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

    ЭТАП 2 

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

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

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

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

    =0,2+(А4/300)-КОРЕНЬ(А4/600),

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

    =А2*В2, и распространена на ячейки СЗ–С14.

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

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

    График  разности функций Z'(k) и W’(k) приведен на рис. 4.

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

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

      (16)

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

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

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

      (17)

      (18)

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

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

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

    Найдем  значения прибыли:

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

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

    Так как вторая производная отрицательна, то точка k = 352 является точкой максимума. Таким образом, оптимальное количество рабочих равно 352 чел.

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

    ВЫВОД: Для оптимизации прибыли строительной фирме нужно нанять новых рабочих в количестве 352 чел. и построить 70,4 тыс. кв. метров торговых площадей. При этом фирма получит прибыль около 279 млн. руб.