Задача 1

ВВЕДЕНИЕ

Большинство задач линейного программирования может быть решено с помощью симплексного метода. Впервые он был предложен американским ученым Данцигом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским ученым Л.В. Канторовичем.

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

В методических указаниях разобраны алгоритмы решения задач симплексным методом средствами табличного редактора Excel.

Методические указания предназначены для студентов и аспирантов экономических специальностей и могут быть использованы при изучении курсов «Компьютерное моделирование в профессиональной деятельности» и «Экономико-математические методы и модели в коммерческой деятельности», а также в научных исследованиях.

АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКСНЫМ МЕТОДОМ

Решение задач на максимум с естественным базисом

Задача 1

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

Имеются следующие ресурсы:

· пашня – 1600 га;

· труд – 27000 чел.-ч.;

· удобрения – 99000 руб.

В структуре посевов площадь под озимой пшеницей должна составлять не более 50%. Критерий оптимальности – максимум производства зерна.

Решение

1 этап – Математическая запись задачи

За неизвестные примем площадь пашни под культурами, га:

Х1 – пшеница

Х2 – ячмень

Х3 – овес

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

Х1+Х2+Х3<=1600 (пашня)

20Х1+15Х2+13Х3<=27000 (труд)

80Х1+50Х2+30Х3<=99000 (удобрения)

Х1<=800 (по площади пшеницы)

В результате получена система четырех линейных неравенств с тремя неизвестными. Требуется найти такие неотрицательные значение этих неизвестных (Х1>=0, X2>=0, X3>=0), которые бы удовлетворяли данной системе неравенств и обеспечивали получение максимального валового сбора зерна:

Fmax=40X1+35X2+30X3

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

Чтобы найти экономический оптимум, надо решить систему неравенств, для чего необходимо привести ее к каноническому виду. В систему неравенств введем дополнительные неизвестные Y1, Y2, Y3, Y4. Дополнительные переменные прибавляются к левой части неравенства типа <= и вычитаются из левой части неравенства типа >=. В первом случае они будут показывать возможное недоиспользование ресурсов, а во втором – избыток производства продукции.

Получим эквивалентную систему уравнений:

Х1+Х2+Х3+Y1=1600 (пашня)

20Х1+15Х2+13Х3+Y2=27000 (труд)

80Х1+50Х2+30Х3+Y3=99000 (удобрения)

Х1+Y4=800 (по площади пшеницы)

Линейная функция запишется следующим образом:

Fmax=40X1+35X2+30X3+0Y1+0Y2+0Y3+0Y4

Дополнительные неизвестные входят в целевую функцию с нулевой оценкой, так как недоиспользование ресурсов не приносит дохода.

В системе уравнений каждое из неизвестных Y1-Y4 входит лишь в одно уравнение. Решим систему уравнений относительно дополнительных неизвестных:

Y1 = 1600 – (Х1+Х2+Х3)

Y2 = 27000 - (20Х1+15Х2+13Х3)

Y3 = 99000 – (80Х1+50Х2+30Х3)

Y4= 800 – (Х1)

Fmax=0 - (-40X1-35X2-30X3)

Неизвестные Y1-Y4, относительно которых будет решена система, называют базисными.

2 этап – нахождение первого базисного (опорного) плана

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

Оформим в EXCEL таблицу и занесем в нее следующие данные:

Первый опорный план

В базис записываются базисные неизвестные, в столбце свободных членов проставляются ресурсы. Базисные неизвестные характеризуют недоиспользование ресурсов в размере, показанном в столбце свободных членов. Значения в столбце свободных членов должны быть положительными либо нулевыми. В случае отрицательного значения обе части уравнения можно умножить на «-1» и заменить знак на обратный.

В целевой строке находятся коэффициенты целевой функции, а строке неизвестных – перечень основных и дополнительных неизвестных. Элементы по их столбцам представляют собой коэффициенты при неизвестных в системе уравнений и означают нормы расхода ресурсов (выхода продукции).

3 этап – исследование плана на оптимальность

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

Следовательно, первый опорный план в данной задаче не оптимален, его надо улучшать.

4 этап – улучшение опорного плана

Решение осуществляется путем замены базисных неизвестных. В соответствии с этим необходимо решить вопрос, какую неизвестную надо ввести в базис, какую вывести из него. Здесь поступают следующим образом. При решении задачи на максимум в базис вводится та неизвестная, у которой в целевой строке среди отрицательных коэффициентов находится наибольший по абсолютному значению (при решении задач на минимум – среди положительных коэффициентов). В данной задаче такой неизвестной является Х1, следовательно, в план вводится пшеница. С экономической точки зрения, это наиболее выгодный вид деятельности (пшеница имеет наибольшую урожайность). Столбец X1 называют разрешающим столбцом.

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

Элемент, стоящий на пересечении разрешающих строки и столбца называется разрешающим элементом. В данной задаче разрешающая строка будет Y4, а разрешающий элемент равен 1. Следовательно, необходимо вывести из базиса Y4, а на ее место ввести Х1.

Первый опорный план

Составляем вторую симплексную таблицу, или второй вариант плана.

Переход от одной таблицы к другой называется шагом. На каждом шаге в базис можно ввести только одно неизвестное и одно вывести. Во второй таблице вместо Y4 заносится Х1. Остальные базисные неизвестные не меняются.

Все коэффициенты второй таблицы рассчитываются на основе первой.

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

НЗ = СЗ/РЭ,

где НЗ – новое значение элемента; СЗ – старое значение элемента, взятое из предыдущей таблицы; РЭ – разрешающий элемент.

Например, B12=B5/$C$5=800/1=800. Далее эта формула копируется в остальные ячейки строки 12.

Далее заполняется по методу прямоугольника:

НЗ = СЗ – ЭРстр*ЭРст/РЭ,

где ЭРстр – элемент, находящийся на пересечении текущего столбца с разрешающей строкой; ЭРст – элемент, находящийся на пересечении текущей строки с разрешающим столбцом.

Например, значение ячейки B9=B2-B$5*$C2/$C$5=1600-800*1/1. Затем эта формула копируется в остальные ячейки таблицы (кроме бывшей разрешающей строки).

Второй опорный план

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

Третий опорный план

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

Четвертый опорный план

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

Пятый опорный план

Вывод. Отсутствие отрицательных величин в индексной строке пятой симплексной таблицы свидетельствует о том, что данный план оптимален. В него вошли две зерновые культуры: пшеница (Х1) – 600 га, ячмень (Х2) – 1000 га. Овес (Х3) выращивать не рекомендуется. При таком сочетании культур и именно в этих размерах обеспечивается максимальное производство зерна – 59000 ц. Любое изменение в соотношении культур при неизменности условий ведет к уменьшению целевой функции. Базисная неизвестная Y1 характеризует использование пашни, которая занята под посевы полностью. Трудовые ресурсы (Y2) также использованы полностью. Удобрения (Y3) остались на сумму 1000 руб.

Коэффициенты целевой строки называют двойственными оценками. Их анализ позволяет оценить отклонение оптимального решения при изменении параметров задачи.

Анализ двойственных оценок

Вывод. При включении в оптимальную структуру посевов овса (Х3), валовой сбор зерна сократится на 3 ц. При увеличении на 1 га площади пашни (Y1) – валовой сбор зерна увеличится на 20 ц, а привлечение дополнительно 1 чел.-ч. трудовых ресурсов приведет к росту валового сбора зерна на 1 ц.