Решение транспортной задачи

Три поставщика одного и того же продукта располагают в планируемый период следующими запасами этого продукта: первый- 120 условных единиц, второй- 100 и третий 80 единиц. Этот продукт должен быть перевезен к трем потребителям, спросы которых соответственно равны 90, 90 и 120 условных единиц. Приведенная ниже таблица содержит показатели затрат, связанных с перевозкой продукта из i-ro пункта отправления в j-й пункт потребления.

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

Поставщики	Потребители и их спрос их спрос	Запасы
А	Б	В
I
II
III
Спрос

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

7·х₁₁+6·х₁₂+4·х₁₃+3·х₂₁+8·х₂₂+5·х₂₃+2·х₃₁+3·х₃₂+7·х₃₃ → min,

Ограничения имеют вид:

х₁₁+х₁₂+х₁₃=120,

х₂₁+х₂₂+х₂₃=100,

х₃₁+х₃₂+х₃₃=80,

х₁₁+х₂₁+х₃₁=90,

х₁₂+х₂₂+х₃₂=90,

х₁₃+х₂₃+х₃₃=120,

.

Искомые значения х_ij находятся в блоке ячеек B4:D6. Адрес данного блока входит в поле ввода. Изменяя ячейки в окне «Поиск решения» (показано на рис. 2.4). Требования к ограничениям по спросу и запасам представлены соответственно в ячейках B7:D7 и Е4:Е6. Коэффициенты ЦФ, означающие затраты на доставку, расположены в блоке ячеек B12:D14.

Формулы целевой функции и ограничений находятся соответственно в ячейке F8 и ячейках B8:D8 (ограничения по спросу), F4:F6 (ограничения по запасам) (см. рис. 2.4 и 2.6). Вид электронной таблицы в режиме отображения формул представлен на рис. 2.5.

Рис. 2.4. Окно "поиск решения"

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

Рис. 2.5. Окно «поиск решения»

Результаты поиска решения представлены на рис. 2.6.

Рис. 2.6. Окно «результаты поиска решения»

7. Анализ в задачах симплексного типа

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

Основные блоки исследуемой информации:

1. Собственно оптимальное решение – значения базисных переменных (переменные, не попавшие в базис равны нулю).

2. Значение целевой функции.

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

4. Коэффициенты замещения.

Интерпретация оптимального решения:

1. Значение целевой функции показывает, соответственно, минимально достижимые затраты или максимально достижимый доход.

2. Основные переменные, попавшие в базис характеризуют эффективные отрасли. Соответственно не базисные переменные характеризуют отрасли, развитие которых нецелесообразно.

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

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

5. Избыточные переменные, попавшие в базис, характеризуют перевыполнение плана по соответствующему виду продукции.

6. Избыточные переменные, не попавшие в базис, показывают, что план производства (строительства и т. п.) строго выполняется (без перевыполнения). Это обусловлено дополнительными ограничениями при постановке начальных условий задачи (например строительство не менее определённого количества зданий в определённом районе). Дальнейшее снижение расходов (рост доходов), без изменения первоначальных условий, возможно только при отмене дополнительных условий. Или, что менее вероятно, именно такой объём производства является оптимальным.

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

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

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

· Оптимальное решение - значение в столбце А_i0, базисных переменных (небазисные переменные равны пулю);

· Оптимальное значение целевой функции, находящееся в индексной строке в том же столбце: Z_max = 495909;

· Коэффициенты замещения (Коэффициенты структурных сдвигов), расположенные в столбцах небазисных переменных;

· Элементы индексной строки, соответствующие небазисным переменным.

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

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

Таблица 1

№п/п	Б	№ огр-я	Аi0	X4 (Осн.)	Х5(Изб.)	Х6(Ост.)	Х8 (Ост.)
	Х1		409,1	-2,05	1,25	-0,023	0,023
	Х2		590,9	2,05	-0,25	0,023	-0,023
	Х7	(3)		-64,64	2,65	-0,775	0,525
	Х3			2,00	-0,10	0,02	0,02
				775,00	60,00	10,7	5,2

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

площадь пашни под зерновыми товарными культурами Х1= 409,1 га;

площадь пашни под кормовыми культурами Х2= 590,9 га;

поголовье коров Х3= 700 голов.

2. Основные переменные, не попавшие в базис, характеризуют неэффективные отрасли хозяйства, которые развивать нецелесообразно. В рассматриваемом примере к ним относится Х4=0.

3. Экстемальное значение целевой функции показывает максимально возможный чистый доход хозяйства, достигаемый при оптимальном сочетании отраслей хозяйства (Zmax= 495909руб.). Любое другое сочетание отраслей в условиях ограниченности ресурсов, в том числе развитие неэффективных отраслей, будет приводить к ухудшению оптимального плана.

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

недоиспользованные денежно-материальные ресурсы Х7=92520 руб.

5. Остаточные переменные, не попавшие в базис, характеризуют полностью исчерпанные, то есть дефецитные, ресурсы. Всякое увеличение дефицитного ресурса обеспечивает дополнительное развитие эффективных отраслей и увеличение дохода хозяйства. Поскольку в число базисных не вошли остаточные переменные Х5, Х6, Х8., то к дефицитным ресурсам относятся:

площадь пашни

трудовые ресурсы

общий запас кормов.

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

Двойственные задачи линейного программирования. Экономическая интерпретация значений двойственных переменных (двойственных оценок)

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

Особенности анализа прямой задачи с помощью решения двойст­венной рассмотрим на примере упрощенной демонстрационной задачи Дз-5. Это простейший случай, так как задача содержит огра­ничения только типа «≥» и, соответственно, все дополнительные переменные являются остаточными.

Итак, пусть дана задача линейного программирования (в нека-ноническом представлении):

Х1 ≤1500 (1)

5*Х1+50*Х2 ≤12000 (2)

-10*Х1+80*Х2 ≤2000 (3)

Х2 ≤110 (4)

Z=150*Х1+800*Х2→ max (5)

Xij ≥0, j=1,2. (6)

Общее структурное представление этой же задачи имеет вид:

∑Aij*Xij ≤Bi, i=1,...,4

Z= ∑Cj*Xj → max

Xj ≥ 0, j=1,2.

Соответствие между символами Aij, Bi, Cj и числовыми коэффициентами в соотношениях (1),….(5) достаточно очевидно.

При постановке двойственной здачи вводят двойственные переменные – Y1,...,Y4. Каждая переменная сопоставляется одному ограничению прямой задачи. Структурный вид обратной задачи таков:

∑Aij*Yi ∑Cj, j=1,2.

Z’= ∑ Bi*Yi → min,

Yi ≥ 0, i=1,...,4.

Соответствующая развернутая запись имеет вид:

Y1+5 *Y2- 10*Y3 150 (1)

50*Y2+80*Y3+Y4 800 (2)

Z’= 1500*Y1+ 12000*Y2+2000*Y3+110*Y4 → min (3)

Yi≥0, i=1,...,4.

Обратите внимание на то, что по сравнению с прямой задачей поменялись знаки ограничений - вместо «≤» используется «≥» и целевая функция Z' подвергается минимизации, а не максимизации. (Отметим, что для прямых задач других видов - с ограни­чениями типа «≥», на минимизцию целевой функции - правила построения обратных задач отличаются от рассмотренных).

Задачу (1д),...,(4д) можно рассматривать как обычную задачу линейного программирования и решать ее симплекс-методом. Такое решение представлено в таблице 30.

Таблица 30

Последняя симплекс-таблица для задачи, обратной к задаче Дз-5

Z'min= 297000

Сравнивая результаты решения прямой и обратной задач табл.28 и 30), можно установить следующие факты:

1) оптимальное (максимальное) значение целевой функции Z прямой задачи совпадает с оптимальным (минимальным) значением целевой функции Z' обратной задачи;

2) значения основных переменных обратной задачи Y1,...,Y4 (см. табл.30) совпадают с элементами индексной строки., соответ­ствующими остаточным переменным Х3,...,Х6 в последней сим-плекс-таблице прямой задачи (см. табл.28).

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

Zmax=Z’min=∑ Bi*Yi

Проанализируем размерности величин, входящих в это выражение. Слева стоит значение целевой функции Z, выражающее в рассматриваемом примере доход хозяйства, измеряемый в тыс.руб. Спра­ва - произведения ресурсов хозяйства на двойственные перемен­ные. Для того, чтобы размерность правой части совпадала с раз­мерностью левой, необходимо, чтобы каждая двойственная пере­менная Yi имела размерность (тыс.руб.)/(ед. измерения i-го ресурса). Например, для ресурса В1 размерность соответстующей переменной Y1 должна быть руб./га. С учетом изложенного, основные двойственные переменные могут интерпретироваться как показатели ценности различных ресурсов прямой задачи с точки зрения достижения поставленной цели - достижения мак­симума доходов хозяйства. В связи с этми основные двойственные переменные обычно называют скрытыми (или теневыми) ценами ресурсов или оценками ресурсов.

Что дает знание скрытых цен ресурсов?

Рассмотрим подробнее выражение (7). Оно позволяет утверждать следующее: если какой-нибудь ресурс Вi увеличить на единицу, то значение целевой функции Z в оптимуме возрастет на Yi. Так, например, если к ресурсу пашни добавить ∆В1 = 1 га, то доход хозяйства возрастет на величину

∆Z= ∆B1*Y1=1*70=70 руб.

Соответственно, при уменьшении ресурса пашни целевая функция будет уменьшаться.

Здесь уместно вспомнить введенное в п.2.4.2 деление ресурсов на дефицитные и недифицитные. Было показано, что пашня явля­ется дефицитным ресурсом, что именно ограниченность площади пашни сдерживает дальнейший рост доходов хозяйства. Установленное свойство двойственных переменных полностью согласуется с этим утверждением: увеличение ресурса пашни привело к увели­чению доходов хозяйства. В то же время, если какая-либо двой­ственная переменная в оптимуме равна нулю, то есть скрытая це­на соответствующего ресурса равна нулю, то дальнейшее увеличение этого ресурса не имеет смысла. Например, основная двойственная переменная Y4 равна нулю, то есть скрытая цена ресурса мест для содержания коров равна нулю, а значит увеличение чис­ла таких мест не приведет к увеличению доходов хозяйства. Этот же факт мы установили в п.2.4.2, анализируя геометрическую интерпретацию прямой задачи.

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

Второй из отмеченных выше фактов позволяет опрделить скры­тые цены без решения двойственной задачи непосредственно из последней симплекс-таблицы прямой задачи.

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

Рассмотрим, например, спучай уменьшения доли зерна, идущего на продажу, с 60% до З0% (в задаче Дз-5). Анализируя соответствующую последнюю синплекс-таблицу (табл.31), придем к выводу о принципиальном изменении скрытых цен: скрытая цена пашни стала равной нулю, а скрытая цена мест для содержания коров возросла с нуля до 50 тыс.руб./гол. Соответственно можем ут­верждать, что дефицитными стали места для содержания коров (вместо пашни), (В геометрической интерпретации это соответст­вует переходу оптимкма из вершины Е а вершину D - см. рис. 2).

Таблица 31

• Последняя симплекс-таблица для измененной задачи Дз-5 (доля зерна на продажу уменьшена с 60% до З0%)

Все сказанное выше относилось к случаю, когда в прямой задаче все ограничения являются огранячениями типа «≤». В том случае, если в прямую задачу линейного программирования входит ограничение типа «≥» и, следовательно, среди дополнительных переменных есть избыточная, то соответствующий этой переменной элемент индексной строки, взятый с обратным знаком, также может интерпретироваться как «скрытая це­на» планового задани, стоящего в правой части соответствующего ограничения. Например, в демонстрационной задаче Дз-5 для избыточной переменной Х6 соответствующее значение элемента индексной строки равно 2.385 (см. табл.29), то есть скрытая цена плана по свинине равна -2.385 тыс.руб./кг. Это значит, что увеличение планового задания по производству свинины на 1кг уменьшит значение целевой функции (дохода хозяйства) на 2.385 тыс.руб.:

Zнов= Zopt+1*(-2,385) =240536 тыс.руб.

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

1.4.3. Преобразование оптимального решения с помощью коэффициентов замещения послдней симплекс-таблицы

Рассмотрим следующую задачу (близкую к задаче Дз-4): Денонстрационная задача Дз-6:

В хозяйстве сложились пять основных отраслей: производство товарного зерна (X1,га), молочное скотоводство (Х2,гол), свиноводство (X3,гол), кормопроизводство (Х4,га) и производ­ство сахарной свеклы (Х5,га). Урожайность свеклы- 240 ц/га,

трудозатраты при ее выращивании - 400 чел.-ч/га, денежные

затраты - 500 тыс.руб./га, чистый доход - 0.5 тыс.руб./ц.

Другие исходные данные аналогичны данным задачи Дз-4.

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

обеспечивающеемаксимум чистого дохода.

Обозначим через Х6 общие денежные расходы хозяйства. Система ограничения и выражение для целевой функции задачи имеют вид (см. порядок составления ограничений задачи Дз-4):

Ограничение по площади пашни:

X1 + Х4 +Х5 ≤ 900 (1)

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

5*Х1+50*Х2+100*Х3+50*Х4+400*Х5≤ 40000 (2)

Ограничение по денежным ресурсам:

Х6≤90000 (3)

Баланс всех кормов по всем видам животных:

-2,5*Х1+80*Х2+40*Х3- 50*Х4≤1000 (4)

Баланс концентратов по всем видам животных:

-2,5*Х1 + З0*Х2 + 10*ХЗ ≤ 0 (5)

Баланс всех кормов по свиньям:

-2.5*Х1 + 40*ХЗ +50*Х4≤0 (6)

Ограничение по поголовью коров:

Х2≤110 (7)

Ограничение по гарантированному производству свинины:

100*Х3≥ 3000 (8)

Уравнение для расчета общих денежных затрат:

70*Х1+ 25*Х2 + 100*ХЗ + 300*Х4 + 500*Х5=Х6 (9)

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

Z= 225*Х1+800*Х2+100*Х3+120*Х5 → max, (10)

Условии неотрицательности основных переменных:

X ij ≥ 0, j=1,…,6.

Оптимальное решение задачи представлено в таблице 32.

Таблица 32

Анализ табл. 32 доказывает, что производство сахарной свеклы хозяйству невыгодно: соответствующая основная переменная Х5 не попала в базис, то есть в оптимальном сочетании отраслей площадь пашни под свеклу Х5=0.

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

240*Х5 = 4800,

что соответствует требованию отвести под свеклу

Х5 =4800/240= 20 га.

Возникает естественный вопрос, можно ли, не провод полного решения задачи симплекс-методом с учетом указанного ограниче­ния, а только используя уже полученное решение (табл.32), най­ти, тем не менее, новое оптимальное решение.

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

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

Z’=Zmax -149*20=240538-2980=237558 тыс.руб.

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

Новое значение любой базисной переменной из последней симрлекс-таблицы (табл.32) может быть опредепено по формуле:
X’jб=Xjб-К*Х5,

Где К - коэффициент замещения, стоящий на пересечения столбца, соответствующего вводимой переменной, и строке, соответствующей рассматриваемой базисной переменной. Таким образом, если коэффициент замещенияя К, соответствующий данной базисной переменной, отрицателен, то при введении в ппан переменной Х5 базисная переменная будет увеличиваться, в противном случае - уменьшаться. Указанное обстоятельство поз­воляет установить правило определения допустимого предела увеличения переменной Х5: увеличение значения переменной Х5 не должно приводить к отрицательным значениям базисных переменных. Иначе говоря, если рассмотреть базисную переменную, которой соответствует положительный коэффициент замещения, и новое значение базисной переменной X’jб принять равным нулю, то есть минимальному допустимому значению, то из последнего соотношения получим следующее ограничение на величину Х5:

Xjб-Х*Х5=0

Х5max= Xjб/л

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

1. Разделить значения базисных переменных из последней сим­плекс-таблицы на соответствующиеположительные коэффициенты замещения. Для рассматриваемого примера (табл. 32) получим (числа округлены):

Х13: 3810/6.2=614

X9: 28600/390=73

X10: 9120/410=22

X2: 60.2/0.08=753

X1: 842/0.92=915

X4: 581/0.08=7262

Сравнить все полученнне числа и выбрать наименьшее. Это и будет максимально возможное значение вводимой переменной.

Для рассматриваемого примера такое значение равно Х5mах=22. Для понимания влияния полученного ограничения на допустимое значение вводимой переменной необходимо учесть следующее. Именно непревышение ограничения Х5max=22 обеспечивает возмож­ность построения нового оптимального плана из старого (табл.32) без полного решения задачи симплекс-методом. В принципе допус­тимо задать требование, нарушающее указанное ограничение, на­пример, положить Х5=30, но в этом случае придется решать новую задачу (с ограничением Х5=З0) самостоятельно.

(Терминология: иногда отношение, породившее ограничение на допустимые значения вводимой переменной, называют «узким местом»)

2.Расчет новых значение целевой функции и базисных переменных (далее положим, что необходимо ввести в план Х5=20):

Z’=Zmax-(Z5-C5)*X5 (12)

X’jб= Xjб-K*X5 (13)

где (Z5-С5) элемент индексной строки, соответствующий переменной Х5

К - коэффициент замещенея, расположенный в стол­бце, соответствующем небазисной переменной Х5, и в строке, соответствующей базисной переменной Xjб.

Результаты расчета заносят в таблицу следующего вида:

Таблица 33

Введение в оптимальный план задачи Дз-4 основной переменной Х5=20

Подчеркнем, что новый план также можно рассматривать как оптимальный, но для задачи Дз-6 с дополнительным условием Х5=20га.

Сравнивая таблицы 33 и 32, придем к выводу, что требование занять 20 гектаров пашни под сахарную свеклу привело к уменьшению:

- площади зерновых культур (Х1) - на 18.4 га

- ппощади кормовых культур (Х4) - на 1.6 га

- поголовья коров (Х2) - на 2 головы.

При этом поголовье свиней сохранилось, что и должно быть, по-скольку в условиях задачи сформулировано жесткое плановое задание по свинине. Общие денедные расходы хозяйства (Х5) уведичились на 8200 руб., а чистый доход хозяйства (целевая функци) уменьшился на 2980 тыс. руб.

Рассмотрим теперь вопрос о введении в план остаточной переменной.

Прежде чем дать полный аналитический алгоритм этой процедуры, рассмотрим этот вопрос на примере упрощенной демонстрационной задачи (Дз-5). Напомним, что математическая формулировка этой задачи в канонической форме дана в п.2.3.1., геометрическая ин­терпретация - на рис.2, оптимальное решение - в табл.28.

Согласно полученному решению, дефицитными явлются ресурс пашни и трудовые ресурсы, и, соответственно, остаточные пере­менные Х3 и Х4 не попали в базис (см. табл. 26), то есть их значния равны нулю. Какую содержательную интерпретацию можно дать введению в план остаточной переменной Х3 (то есть приданию ей ненулевого значения). Рассмотрим соответствующее кано­ническое ограничение:

X1 + Х3 =1500 (1к)

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

Если переменной ХЗ придать отрицательное значение, например, Х3=-400, то численно это будет означать увеличение основной переменной X1:

X1 = 1500 - Х3 = 1500 - (-400) = 1900

В то же время это действие можно интерпретировать как увеличение ресурса пашни с 1500 до 1900 гектаров. Геометрически это же действие изображается сдвигом грани EF симплекса вправо (сравните рис. 2 и 3). Новое решение будет представлено вершиной Е' симплекса (рис.3), а новое значение целевой функции - линией уровня, касающейся симплекса в этой вершине.

Отметим принципиальные особенности полученного решения:

- во-первых, это решение также оптимально, но только для измененной задачи - с ограничением по площади пашни
не 1500, а 1900 гектаров

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

Каково максимальное (по модулю) допустимое, отрицательное значение

Рис.З. Геометрическое представление задачи Дз-5: случай ввода и оптимальный план переменной Х3=-400, что эквивалентно увеличению ресурса пашни на 420 га. Соответственно оптимальная вершина перенесется в точку Е'.

переменной Х3? Если постепенно увеличивать модулъ X3, то это будет соответствовать сдвигу грани ЕF вправо. При Х3=900 грань EF смещается еще дальше вправо и «вырождается» в точку E’' - точку пересечения оси X1 и линии, описывающей второе ограничение (по трудозатратам) - см. рис.3. При дальнейшем увеличении модуля Х3 точка пересеченна линии, описывающей первое ограничение (по пашне), с осью X1 - точка F вообще выйдет за пределы симплекса, то есть ограничение по пашне не будет участвовать в формировании области допустимых решений задачи - станет иазбыточным. Соответственно, при Х3<-900 изменится структура оптимального решения.

Итак, мы геометрически установили максимальное по модулю допустимое, отрицательное значение переменное ХЗ, при котором еще сохраняется структура оптимального решения. Это, конечно, нн значит, что переменной ХЗ нельзя присвоить значение ХЗ < -900 (т.е. положить площадь пашни более 2400га.) Это в принципе допустимо, но для получения оптимального решения придется полностью провести решение новой задачи сим­плекс-методом.

Рассуждая аналогичным образом, можно определить максимальное допустимое, положительное значение переменной Х3. Действительно, придание переменной Х3 положительного значе­ния эквивалентно уменьшению ресурса пашни:

X1 = 1500 - Х3.

Геометрически это эквивалентно сдвигу грани EF влево (см. рис. 2). Ясно, что вид симплекса существенно изменится, когда точка Е при движении влево совместятся с точкой D. Это будет соответствовать максимальному допустимому, положительному зна­чению переменной Х3:

ХЗ =200.

Подведем итог сказанному.

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

Аналитический алгоритм преобразования оптимального плана при введении в план остаточной пере­меной заключается в следующем (на примере задачи Дз-5 – см.. табп.28)):

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

Для рассматриваемого примера получим (числа округлены):
Х6: 20/0.1 =+200

Х5: 9800/18 =+544

Х2: 90/(-0.1) =-900

Х1: 1500/1 +1500

Из найденных чисел выбрать неименьшее положительное и наименьшее (по модулю) отрицательное. Тем самым будут установлены пределы, в которых можно изменять значения оотаточной переменной без изменения структуры оптимального решени. Дл рассматриваемого примера допустимые пределы изменения переменной ХЗ составляют (-900,+200).

Рассмотрим далее случай введения в план переменной Х3=-400. 2.Расчет новых значений целевой функции и базисных переменных по формулам анаоргичным (12) и (13)

Z' =Zmax-(Z3-C3)*X3

X’jб=Xjб- K*Х3

где (ZЗ-СЗ) - элемент индексной строки, соотвтствующий переменной Х3

К – коэффициент замещения, расположенный в столб­це, соответствующем небазисной переменкой ХЗ, и в строке, соответствующей базисной пере­менной Хjб.

Напомним, что в предыдущей формуле (ZЗ-СЗ) это скрытая цена ресурса пашни, а знак «-» перед ней обусловлен тем, что увеличению ресура пашни соответствуют отрицательные значения остаточной переменной Х3. Результаты расчета заносят в таблицу специального вида (табл.34).

Таблица 34

Введение в оптимальный план задачи Дз-5 остаточной переменной Х3=-400

Таким образом, в рассмотренном примере введение в план оста­точной переменной Х3=-400, то есть увеличение ресурса пашни на 400 гектаров, приводит к увеличению, площади посевов зерна до 1900 гектаров (Х1) и к уменьшению поголовья коров до 50 голов (Х2). Последний факт достаточно наглядно поясняется геометри­ческой иппюстрацией (см. рис.3): увепичение ресурса пашни при­водит к сдвигу экстремальной вершины Е по линии, порождаемой вторым ограничением (трудовые ресурсы), то есть к уменьшению координаты Х2. Иначе говоря, «ответственным» за столь странное изменение поголовья коров является дефицитность трудовых ресурсов.

В случае введения в план избыточной переменной алгоритм вычислений идентичен рассмотренному. При интерпрета­ции результатов необходимо только учесть, что увеличению правой части соответствующего ограничения, то есть плана производства какой-либо продукции (например, плана производства свинины в задаче Дз-4 - см. ограничения (8) из п.2.1 и (8к) из п.2.2), эквивалентны положительные значения избыточной переменной (Х6 в указанном примере).

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

Во-вторых, сама возможность вычисления нового значения целевой функции с помощью двойственных оценок лри введении в план остаточных и избыточных леременных (то есть при изменении ре­сурсных ограничений и плановых заданий) говорит о том, что двойственные оценки (скрытые цены ресурсов и плановых заданий) относительно устойчивы - сохраняются при изменении ресурсов и плановых заданий в определенных пределах. Для проверки «в лоб» можно, например, просто решить упрощенную демонстрационную задачу (Дз-5), изменив в ней ограничения по пашне (вместо Х1<1500 положить Х1<1900). Получив новое решение, совпадающее с тем, которое мы получали, введя в план остаточную переменную Х3=-400 (см. выше), можно убедиться, что двойственные оценки, соответствующие остаточным переменным ХЗ и X4 будут теми же, что и в исходной задаче, решение которой дано в таблице 28. Пределы устойчивости скрытых цен к изменению ре­сурсных огранячений и плановых заданий те же, что и пределы устойчивости структуры решения к таким изменениям.

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

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

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

Рассмотрим геометрическую интерпретацию этого свойства (на примере упрощенной демонстрационной задачи Дз-5).

Если изменить значение коэффициентов целевой фунциии таким образом, чтобы отношение коэффициентов при переменных Х1 и Х2 отличалось от первоначального отношении, равного:

С1/С2 = 150/800= 0.1875

(см. (5) из п. 2.З), то будет меняться наклон линии уровня це­левой функции. Для оптимального решения это приведет к тому, что соответствующая оптимуму линия уровня будет «вращаться» вокруг точки Е (рис. 4).

Рис.4. Геометрическое представление задачи Дз-5): случай изменения коэффициентов целевой функции. Ориентация линий уровня целевой функции (пунктирные лннии) меняется в зависимости от отноше­ния коэффициентов С1/С2 при переменных X1 и Х2 (линяя уровней «вращается» вокруг экстремальной точки Е).

•сно, что «о тех пор пока линяв уровня не совпадет с гранью DE или EF оптимальное решение будет сохраняться (будет «находиться» в вершине Е). Поскольку известны уравнения линий DE и EF (они непосредственно получаются из неравенств (2) и (1) пункта 2.3 заменой знака «≤» на знак «=»), то нетрудно устано­вить, каковы предельные допустимые изменения отношения коэффи-циентов при переменных X1 и Х2 в целевой функции. Наименьшее значение, согласно уравнению для линии DE, равно

А21/А22 = 5/50 = 0.1,

а наибольшее, согласно уравнению для линии ЕF, стремится в бесконечность. Таким образом, при

С1/С2 > 0.1

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

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

Для иллюстрации алгоритма рассмотрим оптимальное решение де­монстрационной задачи Дз-6 (табл.32).

Необходимо рассмотреть два существенно различных случая.

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

Пусть коэффициент при переменной Хi в целевой функции изменяется следующим образом:

С1' = С1 + dc,

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

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

(Zj-Cj)' = (Zj-Сj) + А6j*dc, (14)

где A6j –коэффициенты замещения, расположенные в последней симплекс-таблице в строке, соответствующей переменной Х1(см. 6-ю строку табл.32).

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

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

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

Следовательно, для любого такого элемента должно выполняться условие:

(Zj-Cj)+A6j*dc≥0 (15)

В соответствии с этим условием алгортим определения допустимых значений вариации dс таков (рассмотрим его на примере задачи Дз-6 табл.32).

Для выбранной базисной переменной (например, Х1) переберем все ненулевые коэффициенты замещения, стоящие в столбцах, со-ответствующихх небазисным переменным. Делим соответствующие элементы индексной строки на выбранныее коэффициенты замещения и результатыделения берем с обратным знаком:

Х5: -221/0.92 =-250

X7: -2.39/0.0025 =-955

X8: -269/0.92 =-292

X11: -5.39/0.018 =-299

X12: -12.3/(-0.049) =+251.

Из полученныхх чисел выбираем наименьшие по модулю отрицательные и положительные числа. Они и задают диапазон допустимых значений вариации dс. Для рассмотренного примера этот диапазон составляет (-240,+251).

В. Изменение коэффициента в целевой функции при пе­ременной, не входящей в базис оптимального решения.

Дпя данного случая, не приводя подробного описания алгори­тма, отметим только, что если, например, коэффициент при небазисной переменной Х5 (см. табл.32) изменить по формуле:

С5' = С5 + dc, (16)

то ато приведет к изменению только элемента индекс­ной строки, соответствующего этой переменной:

(Z5-С5)' =- (Z5-С5) - dс. (17)

Обратите внимание на то, что знаки при dс в (16) и (17) противоположны. Потребовав, чтобы новое значение элемента ин­дексной строки не было отрицательным, получим следующее огра­ничение на значение вариации dс (для случая максимизации целевой функции):

dc ≤ (Z5-C5).

8. Пример решения задачи линейного программирования симплекс-методом с помощью MS Excel

Задача.

Населенный пункт N предполагает осуществить значительные капитальные вложения в расширение застройки с целью получения в дальнейшем max дохода от сдачи помещений и сооружений различного вида в аренду. При этом надо учесть, что площадь под жилыми коттеджами не должна превышать 30% от площади под жилыми многоэтажными зданиями; а площадь под магазинами и складскими помещениями должна составлять 10% от площади под жилыми многоэтажными зданиями (причем площадь под складскими помещениями должна составлять 35% от площади под магазинами); площадь под заправочными станциями не должна превышать 500 га.

Определить оптимальное сочетание направлений застройки. Задачу решить симплексным методом

Исходные данные.

	Жилые многоэтажные здания	Жилые коттеджи	Магазины	Складские помещения	Заправочные станции	Ресурсы населенного пункта
Общая площадь выделяемых земель, га						10 000
Дополнительные затраты на 1м2 площади, тыс.руб	4,3	10,5	5,8	3,6	7,5	450 000
Трудовые затраты на 1 м2 (чл.дн)	1,8	3,2	1,9	1,5	2,1	33 000
Чистый доход, получаемый от использования 1 м2, тыс.руб

За неизвестные примем площади застройки по видам:

X1 – жилые многоэтажные здания;

X2 – жилые коттеджи;

X3 – магазины;

Х4 – складские помещения;

Х5 – заправочные станции.

Для построения экономико-математической модели задачи необходимо учесть все условия. В данном случае, по этим условиям можно составить пять ограничений:

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

1) Х1+Х2+Х3+Х4+Х5<=10000

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

2) Х5<=500

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

3) Х2<=2850;

4) Х4<=332.5.

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

5) 1,8Х1+3,2Х2+1,9Х3+1,5Х4+2,1Х5<=33 000

6) 4,3Х1+10,5Х2+5,8Х3+3,6Х4+7,5Х5<=450000

В результате получена система шести линейных неравенств с пятью неизвестными. Требуется найти такие неотрицательные значения этих неизвестных Х1>=0; Х2>=0; Х3>=0; Х4>=0; Х5>=0, которые бы удовлетворяли данной системе неравенств и обеспечивали получение максимума прибыли от аренды застройки в целом:

Z_max = 22Х1+15Х2+44Х3+32Х4+77Х5

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

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

Рисунок 1.

Вся разработанная информация сводится в развернутую экономико-математическую модель и заносится в рабочий лист MS Excel. (Рис. 2.)

Рисунок 2.

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

Рисунок 3.

В столбцы А («№»), В («Ограничения»), С («Единицы измерения») и J («Тип ограничений») вводятся соответствующие данные непосредственно в модель (рис.1). Они не используются в расчетах и служат для информативности и облегчения понимания содержания модели. В столбец I («Объем ограничений») вводятся ссылки на ячейки, содержащие соответствующую названию столбца информацию (значения правых частей построенных ранее неравенств).

Для искомых величин переменных Х1, Х2, Х3, Х4, Х5 нами были оставлены пустые ячейки - соответственно D4, E4, F4, G4, H4. Изначально пустые ячейки программа MS Excel воспринимает как ячейки, значение которых равно нулю. Столбец I, названный нами «Сумма произведений», предназначен для определения суммы произведений значений искомых неизвестных (ячейки D4, E4, F4, G4, H4) и технико-экономических коэффициентов по соответствующим ограничениям (строки 5-10) и целевой функции (строка 11). Таким образом, в столбце I определяется:

- количество используемых ресурсов (ячейка I5 общей площади выделяемых земель; I6 – площади, которая может быть использована под посевы заправочные станции, I7 – коттеджи; I8 – складские помещения);

- трудовые затраты (ячейка I9);

- дополнительные затраты (ячейка I10)

- величина прибыли (ячейка I 11).

На рисунке 2 показано, как в ячейке I11 реализуется запись суммы произведений значений переменных (площадей застройки - ячейки D4, E4, F4, G4, H4) на соответствующие прибыли с 1 га их посева(ячейки D11, E11, F11, G11, H11)с помощью функции MS Excel «СУММПРОИЗВ». Так как при написании данной формулы использованы абсолютные адресации на ячейки от D4 до H4,эта формула может быть скопирована в другие ячейки от I5 до I10.

Таким образом, построен опорный план (рис. 2) и получено первое допустимое решение. Значения неизвестных Х1, Х2, Х3, Х4, Х5 равны нулю (ячейки D4, E4, F4, G4, H4 -пустые ячейки), ячейки столбца I «Сумма произведений» по всем ограничениям (строкам 5-10) и целевой строке (строка 11) также имеют нулевые значения.

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

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

После выбора данной команды появится диалоговое окно (рис. 4).

Рисунок 4.

Поскольку в качестве критерия оптимизации нами выбрана максимизация прибыли, в поле Установить целевую ячейку введите ссылку на ячейку, содержащую формулу расчета прибыли. В нашем случае это ячейка $I$11. Чтобы максимизировать значение конечной ячейки путем изменения значений влияющих ячеек (влияющими, в данном случае это и изменяемые ячейки, являются ячейки, которые предназначены для хранения значений искомых неизвестных), переключатель установите в положение максимальному значению;

В поле Изменяя ячейки введите ссылки на изменяемые ячейки, разделяя их запятыми; либо, если ячейки находятся рядом, указывая первую и последнюю ячейку, разделяя их двоеточием ($D4:$H$4.

В поле Ограничения введите все ограничения, накладываемые на поиск решения. Добавление ограничения рассмотрим на примере добавления первого ограничения по общей площади пашни.

В разделе Ограничения диалогового окна Поиск решения нажмите кнопку Добавить. Появится следующее диалоговое окно (рис. 5)

Рисунок 5.

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

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

В поле Ограничение введите ссылку на ячейку, в которой находится значение наличия площади пашни в хозяйстве, либо ссылка на это значение. В нашем случае, это ячейка $K$6

В результате диалоговое окно примет следующий вид (рис. 6).

Рисунок 6.

Чтобы принять ограничение и приступить к вводу нового, нажмите кнопку Добавить. Аналогично вводятся и другие ограничения. Чтобы вернуться в диалоговое окно Поиск решения, нажмите кнопку OK.

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

Рисунок 7.

Для изменения и удаления ограничений в списке Ограничения диалогового окна Поиск решения укажите ограничение, которое требуется изменить или удалить. Выберите команду Изменить и внесите изменения либо нажмите кнопку Удалить.

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

Рисунок 8.

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

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

- чтобы восстановить исходные данные, выберите вариант Восстановить исходные значения.

Рисунок 9.

Для того чтобы прервать поиск решения, нажмите клавишу ESC.

Лист Microsoft Excel будет пересчитан с учетом найденных значений влияющих ячеек. В результате решения и сохранения результатов поиска на листе модель примет следующий вид (табл. 10).

Рисунок 10.

В ячейках D4 - H4 получены значения искомых неизвестных, в ячейках I 5 - I10 определены объемы используемых ресурсов. При всех этих значениях величина прибыли достигает 456500 тыс. руб. (ячейка I11).

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

Рисунок 11.

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

Если ограничений в модели очень много, то визуально достаточно трудно сравнивать и проверять на верность каждую строку. Для облегчения рекомендуется добавить в модель еще один столбец «Проверка», где с помощью функций MS Excel «ЕСЛИ» и «ОКРУГЛ» можно организовать автоматическую проверку (рис. 12).

Рисунок 12.

Примеры градостроительных задач.

Задача 1

Определение видов и объемов продаж объектов недвижимого имущества

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

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

Таблица 1

Информация о ресурсах и нормах ежегодных затрат на эксплуатацию объектов недвижимого имущества.

№№ п\п	Виды условий	Объекты недвижимого имущества	Ресурсы
Жилой фонд, м2	Земельные участки, га	гаражи	Нежилые помещения, м2
Квар-тиры	Дома
	По площади жилого фонда, м2
	По состоянию площади жилого и нежилого фонда, м2	-0,1	-0,1			0,9
	Площадь зем. участков, га
	По эксплуатационным затратам, руб./ед.измер.
	По зем. платежам, руб. \ га
	По количеству гаражей, ед.
Выручка от продажи, руб.						max

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

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

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

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

Пример: Студент имеет шифр 99148. Вместо оценок чистого дохода в последней строке таблицы равных 10, 15, 50, 32, 70 исходными значениями станут оценки равные 58, 63, 98, 80, 118. Общая площадь выделяемых под застройку земель будет равна 10 000+99148=109 148га.

Основные переменные:

Х1 – количество жилого фонда, размещенного в квартирах, м²;

Х2 – количество жилого фонда, размещенного в домах, м²;

Х3 – площадь земельных участков, га;

Х4 – количество гаражей, ед;

Х5 – площадь нежилых помещений, м².

Дополнительные переменные:

Х6 – неиспользованный ресурс по площади жилого фонда, м²;

Х7 – неиспользованный ресурс привлекательности жилого и нежилого фонда, м²;

Х8 – неиспользованная площадь земельных участков, га;

Х9 – неиспользованные денежные средства на эксплуатационные затраты, руб;

Х10 – неиспользованные денежные средства на земельные платежи, руб;

Х11 – остаточные ресурсы для гаражного строительства, ед.

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

Порядок выполнения работ.

Запись экономико-математической модели.

Запись расширенной модели задачи.

Решение задачи симплексным методом.

Запись ответа и расшифровка базисных переменных по последней симплексной таблице.

Задача 2

Определение направлений и площади застройки городских земель.

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

Таблица 2

Исходные данные о ресурсах и затратах на строительство населенного пункта

Условия	Жилые многоэтажные здания, м2	Жилые коттеджи, м2	Магазины, м2	Складские помеще-ния, м2	Заправочные станции, м2	Ресурсы населен-ного пункта
Общая площадь выделяе-мых земель, га	0,0001	0,0001	0,0001	0,0001	0,0001	20,0
Инвести-ционные вложения на 1м2 площади, тыс. руб.	0,5	1,0	0,5	0,2	0,3
Трудовые затраты на 1м2,(чел. дн.)
						max

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

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

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

Пример: Студент имеет шифр 99148. Вместо оценок чистого дохода в последней строке таблицы равных 10, 15, 50, 32, 70 исходными значениями станут оценки равные 58, 63, 98, 80, 118. Общая площадь, выделяемых под застройку земель будет равна 10 000+99148=19 148га.

Основные переменные:

Х1 – количество м² в жилых многоэтажных зданиях;

Х2 – количество м² в жилых коттеджах;

Х3 – площадь магазинов, м²;

Х4 – площадь складских помещений, м²;

Х5 – площадь под заправочными станциями, м².

Дополнительные переменные:

Х6 – неиспользованный ресурс по общей площади выделяемых земель, м²;

Х7 – неиспользованные средства инвестиционных вложений, м²;

Х8 – неиспользованные трудовые ресурсы, чел/дн.

Порядок выполнения работ.

1. Запись экономико-математической модели.

2. Запись расширенной модели задачи.

3. Решение задачи симплексным методом.

4. Запись ответа и расшифровка базисных переменных по последней симплексной таблице.

Задача 3

Определение объемов и ассортиментов продажи продуктов питания торгового предприятия

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

Исходные данные приведены в таблице.

Таблица 3

Информация о ресурсах и затратах торгового предприятия