Оптимизация плана производства

1. Постановка основной задачи линейного программирования

1.1    Линейное программирование

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

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

Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:

·        задача об оптимальном использовании ресурсов при производственном планировании;

·        задача о смесях (планирование состава продукции);

·        задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или);

·        транспортные задачи (анализ размещения предприятия, перемещение грузов).

Линейное программирование - наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:

·        математические модели большого числа экономических задач линейны относительно искомых переменных;

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

·        многие задачи линейного программирования, будучи решенными, нашли широкое применение;

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

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

В общем виде модель записывается следующим образом:

целевая функция

 (1.1)

при ограничениях

 (1.2)

требования неотрицательности

 (1.3)

где x_j - переменные (неизвестные);

 - коэффициенты задачи линейного программирования.

Задача состоит в нахождении оптимального значения функции (1.1) при соблюдении ограничений (1.2) и (1.3).

Систему ограничений (1.2) называют функциональными ограничениями задачи, а ограничения (1.3) - прямыми.

Вектор, удовлетворяющий ограничениям (1.2) и (1.3), называется допустимым решением (планом) задачи линейного программирования. План, при котором функция (1.1) достигает своего максимального (минимального) значения, называется оптимальным.

1.2 Симплекс метод решения задач линейного программирования

Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.

Двумерные задачи линейного программирования решаются графически. Для случая N=3 можно рассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.

Допустимым решением (допустимым планом) задачи ЛП, данной в стандартной форме, называется упорядоченное множество чисел (х1, х2, …, хn), удовлетворяющих ограничениям; это точка в n-мерном пространстве.

Множество допустимых решений образует область допустимых решений (ОДР) задачи ЛП. ОДР представляет собой выпуклый многогранник (многоугольник).

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

Базисным называется решение, при котором все свободные переменные равны нулю.

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

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

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

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

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

В основу симплексного метода положена идея последовательного улучшения получаемого решения.

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

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

Процесс применения симплексного метода предполагает реализацию трех его основных элементов:

1.       способ определения какого-либо первоначального допустимого базисного решения задачи;

2.       правило перехода к лучшему (точнее, не худшему) решению;

.        критерий проверки оптимальности найденного решения.

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

1.3. Двойственная задача линейного программирования

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

Под двойственной задачей понимается вспомогательная задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными. Трудоёмкость вычислений при решении ЗЛП в большей степени зависит от числа ограничений, а не от количества переменных.

Дадим определение двойственной задачи по отношению к прямой задаче линейного программирования, состоящей, в нахождении максимального значения функции

функции

f =c₁x₁ + c₂x₂ + … + c_nx_n→max                          (1.4)

при условиях:

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n ≤ b₁₂₁x₁ + a₂₂x₂ + … + a_2nx_n ≤ b₂

…                                                              (1.5)_m1x₁ + a_m2x₂ + … + a_mnx_n ≤ b_mj ≥ 0 (j = 1, 2,… m, m ≤ n).

Задача, состоящая в нахождении минимального значения функции

f*=b₁y₁ + b₂y₂ + … + b_my_m→min               (1.6)

при условиях:

a₁₁y₁ + a₁₂y₂ + … + a_m1y_m ≥ c₁₁₂y₁ + a₂₂y₂ + … + a_m2y_m ≤ c₂

…                                                              (1.7)_1ny₁ + a_2ny₂ + … + a_mny_m ≤ c_mi ≥ 0 (i = 1, 2, … k ≤ m)

называется двойственной по отношению к задаче (1.4) - (1.5). Задачи (1.4) - (1.5) и (1.6) - (1.7) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

Целевая функция исходной задачи задается на максимум, а целевая функция двойственной - на минимум.

1.  Матрица

                                (1.8)

2.  составленная из коэффициентов при неизвестных в системе ограничений (1.5) исходной задачи, и аналогичная матрица

                              (1.9)

в двойственной задаче получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов - строками).

3.  Число переменных в двойственной задаче равно числу ограничений в системе (1.5) исходной задачи, а число ограничений в системе (1.7) двойственной задачи - числу переменных в исходной задаче.

4.       Коэффициентами при неизвестных в целевой функции (1.6) двойственной задачи являются свободные члены в системе (1.5) исходной задачи, а правыми частями в соотношениях системы (1.7) двойственной задачи - коэффициенты при неизвестных в целевой функции (1.4) исходной задачи.

.        Если i-е соотношение в системе (1.5) исходной задачи является неравенством, то j-я переменная двойственной задачи y_j ≥ 0. В противном случае переменная у_j может принимать как положительные, так и отрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (1.5) прямой задачи и соотношения (1.7) двойственной задачи являются неравенствами вида «». Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (1.5) прямой задачи и соотношения (1.7) двойственной задачи являются неравенствами вида «». Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

Если одна из задач двойственной пары (1.4) - (1.5) или (1.6) - (1.7) имеет оптимальный план, то и другая имеет оптимальный план, и значения целевых функций задач при их оптимальных планах равны между собой, т.е. f max = f*min.

2. Построение модели и решение задачи определения оптимального плана производства в ООО «Мельник»

Фабрика ООО «Мельник» специализируется на выпуске двух сортов теста: бисквитное и песочное. Для изготовления теста используются такие ингредиенты как яйца и сахар, так же затрачивается и ресурсы труда. Для изготовления бисквитного теста требуется 5 штук яиц и 0,3 килограмма сахара, для изготовления затрачивается 15 минут. А для изготовления песочного теста потребуется 2 яйца, 0,25 килограмма сахара и 30 минут затраченного времени. Стоимость 1 кг бисквитного теста 30 руб., а песочного 20 руб. Общий запас яиц равен 1000 шт., 75 кг сахара и 125 часов трудовых ресурсов.

2.1 Построение экономико-математической модели

. Переменные задачи.

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

х₁ - суточный объем производства бисквитного теста, (кг);

х₂ - суточный объем производства песочного теста, (кг).

. Целевая функция.

В условии задачи сформулирована цель - добиться максимального дохода от реализации продукции, т.е. критерием эффективности служит параметр суточного дохода, который должен стремиться к максимуму. Чтобы рассчитать величину суточного дохода от продажи продукции обоих видов, необходимо знать объемы производства, т.е. x₁ и х₂ кг продукции в сутки, а также цены на продукцию бисквитного и песочного теста - согласно условию 30 и 20 руб. за 1 кг продукции соответственно. Таким образом, доход от продажи суточного объема производства продукции бисквитного теста равен 30х₁ руб. в сутки, а от продажи песочного теста - 20х₂ тыс. руб. в сутки. Поэтому запишем целевую функцию в виде суммы дохода от продажи продукции бисквитного и песочного теста.

 (руб.).

. Ограничения.

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

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

объем производства продукции не может быть выражен отрицательными значениями.

Запишем эти ограничения в математической форме.

Ограничение по расходу яиц имеет вид:

(т/сутки).

Левая часть ограничения - это расчет расхода яиц на производство теста обоих видов. Расход яиц на производство 1 кг бисквитного теста - 5 шт.; на производство 1 кг песочного теста - 2 шт. Тогда на производство х₁ кг бисквитного теста и х₂ кг песочного теста потребуется (5х₁ + 2x₂) шт. яиц. Правая часть ограничения - это величина запаса яиц на складе - 1000 шт.

Аналогична запись ограничения по расходу сахара:

(кг).

Так же ограничение по трудовым ресурсам имеет вид:

(чел.-ч.)

Неотрицательность объемов производства задается как

Таким образом, математическая модель задачи имеет вид:

;

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

2.2 Определение оптимального плана производства симплексным методом

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

В качестве базисных переменных возьмем х₃, х₄, х₅, тогда небазисные - х₁, х₂. Полагаем х₁ = х₂ = 0, тогда х₃ =1000, х₄=75, х₅ =125.

-я итерация.

Составляем первую симплексную таблицу, соответствующую исходному опорному решению (таблица 3):

или

Таблица 3

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

 и т.д.

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

, т.е. k =1.

За разрешающую строку принимаем строку переменной х₃:

, т.е. s =1.

Разрешающим является элемент а₁₁=5, т.е. вводим в базис переменную х₁, выводим х₃.

-я итерация.

Формируем следующую симплексную таблицу (таблица 4)

Таблица 4

Из таблицы 4 находим опорный план:

,

В индексной строке таблицы 4 имеется одна отрицательная оценка. Полученное решение можно улучшить. Разрешающим элементом является а₂₂=0,13

-я итерация.

Формируем следующую симплексную таблицу (таблица 5).