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

    Введение.

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

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

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

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

 

    

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

 

    Дополнительная  возможность 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 и ведущей будет вторая строка: