Сущность линейного программирования и его использования в социальной сфере

Содержание

 

 

Введение                                                                                                                      2

Условия задачи. Решение. Этап 1 Этап 2 Заключение. Список используемых источников.

3 4 5 10 14 15

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение.

 

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

Наши средства и ресурсы всегда ограничены. Жизнь  была бы менее интересной, если бы это  было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем  у противника; Ганнибалу, чтобы разбить  римлян при Каннах, командуя вдвое  меньшей армией, нужно было действовать очень обдуманно.

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

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

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

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

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

 

 

1. Условия задачи.

 

 

DT	RT	VT	Dж	Rж	Vж	BD	ВR	BV	ST	Sж	P0	P1	P2
7	5	7	10	6	2	0	700	560	12	14	20	0,03	200

 

Дополнительная возможность 1: получение ссуды.

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Решение.

 

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

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

 (1)

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

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

 (2)

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

 (3)

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

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

 (4)

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

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

 (5)

 (6)

 (7)

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

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

 (8)

 (9)

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

 

ЭТАП 1

 

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

 (10)

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

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

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

 (12)

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

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

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

 

Таблица 1.

СБ	Б	0	12	14	0	0	0
			Р0	Р1	Р2	Р3	Р4		Р5
0	Р3	у	7	10	1	0	0	у/10
0	Р4	700	5	6	0	1	0	700/6 = 117
0	Р5	560	7	2	0	0	1	560/2 = 280
		0	–12	–14	0	0	0

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

 

1. Рассмотрим случай у/10≥700/6. Тогда у≥3500/3 и ведущей строкой будет вторая строка:

СБ	Б	0	12	14	0	0	0
			Р0	Р1	Р2	Р3	Р4		Р5
0	Р3	у	7	10	1	0	0	у/10
0	Р4	700	5	6	0	1	0	700/6 = 117
0	Р5	560	7	2	0	0	1	560/2 = 280
		0	–12	–14	0	0	0

 

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

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

СБ	Б	0	12	14	0	0	0
			Р0	Р1	Р2	Р3	Р4		Р5
0	Р3	у–3500/3	–4/3	0	1	–5/3	0
14	Р2	350/3	5/6	1	0	1/6	0	140
0	Р5	980/3	16/3	0	0	–1/3	1	61
		4900/3	–1/3	0	0	7/3	0