Математическое программирование: Линейное программирование, постановка задач, методы решения

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

     Выпуклое  программирование – целевая функция  выпукла (если рассматривается задача ее минимизации) и выпукло множество, на котором решается экстремальная задача.,

     Квадратичное  программирование – целевая функция  квадратична, а ограничениями являются линейные равенства и неравенства.

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

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

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

 

Глава 2. Системный  подход в управлении организацией

     2.1. Общие сведения о линейном программирование

     Линейное  программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина "математическое программирование". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина "линейное программирование" возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

     История линейного программирования в США  уходит корнями в 1947 год, когда Дж.Данциг написал об этом в своей работе. Л.В.Канторович изучал возможность применения математики к вопросам планирования, на основе чего в 1939 году была опубликована его монография "Математические методы организации и планирования производства". Важнейшей находкой (открытием) Л.В.Канторовича явилась возможность четко математически сформулировать важнейшие производственные задачи, что позволяет найти количественный подход к данным задачам, а также их решение численными методами.

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

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

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

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

 •  при наличии математической определенности и количественной ограниченности между изучаемыми переменными величинами и факторами;

  •  при взаимозаменяемости факторов  из-за последовательности расчетов;

  •  в случае совмещения математической  логики с пониманием сущности изучаемых явлений.

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

     В сельском хозяйстве с помощью  этого метода определяют минимальную стоимость кормовых рационов с учетом заданного количества кормов (исходя из видов и содержащихся в них полезных веществ).

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

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

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

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

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

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

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

     Имеются какие-то переменные х = (х1 , х2 , … хn ) и функция этих переменных f(x) = f (х₁ , х₂ , … х_n ), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции f(x) при условии, что переменные x принадлежат некоторой области G.

     В зависимости от вида функции f(x) и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что:

 а)  функция f(x) является линейной  функцией переменных х1 , х2 , … хn

 б)  область G определяется системой  линейных равенств или неравенств.

   Математическая  модель любой задачи линейного программирования включает в себя:

• максимум или минимум целевой функции (критерий оптимальности);
• систему ограничений в форме линейных уравнений и неравенств;
• требование неотрицательности переменных.

2.2. Примеры задач  линейного программирования

     В линейном программировании в основном выделяют следующие виды задач:

1. Задача об использовании ресурсов
2. Задача составления рациона (задача о смесях)
3. Задача об использовании мощностей
4. Транспортная задача

 

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

     1.Задача об использовании ресурсов (задача планирования производства)

       Для изготовления двух видов продукции P₁ и P₂ используют четыре вида ресурсов S₁ S₂ S₃ S₄. Запасы ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице.

Прибыль получаемая от единицы продукции  P₁ и P₂, - соответственно 2 и 3 руб.

Вид ресурса	Запас Ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
		P1	P2
S1	18	1	3
S2	16	2	1
S3	5	-	1
S4	21	3	-

 

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

Решение . Составим экономико-математическую модель задачи.

Обозначим x₁ , x₂  — число единиц продукции соответственно P₁ и P₂ , запланированных к производству. Для их изготовления потребуется

(1· x₁ +3x₂) единиц ресурса S₁ , (2x₁  + 1 · x₂) единиц ресурса S₂ , (1 ·x₂) единиц ресурса S₃  и 3x  единиц ресурса S₄ . Так как потребление ресурсов S₁ , S₂ , S₃  и S₄ не должно превышать их запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

   X₁ +3X₂ ≤ 18   

     2X₁ +X₂ ≤ 16   

     X₂  ≤ 5

     3X₁       ≤   21

По смыслу задачи переменные X1≥0 и X2≥0

Суммарная прибыль F составит 2x₁      руб. от реализации продукции P₁   и 3x₂  руб. — от реализации продукции P₂ , т.е.

F = 2x₁ + 3x₂ → max

Итак, экономико-математическая модель задачи:     найти такой план выпуска продукции  X = (x₁ , x₂ ), удовлетворяющий системе  и условию,  при котором функция  принимает максимальное значение.

     2.Задача составления рациона (задача о смесях)

     Имеется два вида корма I и II, содержащие питательные вещества (витамины) S₁, S₂  и S₃. Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в табл.  (цифры условные).

Питательное вещество(витамин)	Необходимый минимум питательных веществ	Число единиц веществ в 1кг корма
		I	II
S1	9	3	1
S2	8	1	2
S3	12	1	6

 
 

Стоимость 1 кг корма I и II соотвественно равна 4 и 6 руб.

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

      Решение. Составим экономико-математическую модель задачи.  Обозначим x₁, x₂  — количество кормов I и II, входящих в дневной рацион. Тогда этот рацион (см. табл. ) будет включать (3x₁ + 1 · x₂) единиц питательного вещества S₁, (1 · x₁ + 2x₂) единиц вещества S₂  и (1 · x₁  + 6x₂) единиц питательного вещества S₃. Так как содержание питательных веществ S₁, S₂  и S₃  в рационе должно быть не менее соответственно 9, 8 и 12 единиц, то получим систему неравенств: