Решение задачи

Куренкова В.В. ИСУ ПМИ 3-1

Контрольная работа N 1

Построение оптимального плана жилищного строительства

В а р и а н т N 14

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

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

Известно, сколько и каких квартир должно быть в постро­енных домах (потребность в квартирах).

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

Типы квартир	Количество квартир в одном доме	Требуется квартир (не менее,чем)
А1	А2	А3	А4
Однокомнатные
Двухкомнатные
Трехкомнатные
Сметная стоимость 1 дома (млн.долл.)	3.0	4.2	6.0	9.0

Т р е б у е т с я

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

2. Указать, какие дома и в каких количествах входят в оптималь­ный план и какие не входят.

3. Определить, будут ли согласно оптимальному плану построены какие-либо квартиры СВЕРХ необходимых потребностей. Если ДА, то ка­кие и сколько.

4. Определить, на сколько возрастет общая стоимость строительст­ва, если потребуется ввести в строительную программу одно здание из числа тех, которые НЕ ВХОДЯТ в оптимальный план.

5. Определить (используя двойственные оценки оптимального пла­на):

5.1 на сколько возрастет стоимость строительства при увеличении потребностей в трехкомнатных квартирах на 10%;

5.2 на сколько снизится стоимость строительства при уменьшении потребностей в однокомнатных квартирах на 20%;

5.3 изменится ли стоимость строительства при изменении потреб­ностей в двухкомнатных квартирах; если ДА, то на сколько - в расчете на 1 двухкомнатную квартиру.

1)

Решение задачи

Обозначим через

х1 - количество домов серии А1, включаемых в план строительства,

х2 - количество домов серии А2, включаемых в план строительства

х3 - количество домов серии А3, включаемых в план строительства,

х4 - количество домов серии А4, включаемых в план строительства

Тогда требование удовлетворения потребности в квартирах запишется в виде:

по однокомнатным квартирам: 4х₁+6х₂+ 9х₄ ≥ 600

по двухкомнатным квартирам: 2х₁+12х₂+8х_З+ 18х₄ ≥ 360

по трёхкомнатным квартирам: 2х₁+ 8х_З+12х₄ ≥ 360

Требования неотрицательности: х₁≥0, х₂≥0, х₃≥0, х₄≥0

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

Общая стоимость строительства составит F=3х₁ + 4,2х₂ + 6х₃ + 9х₄=>min

Так как эта задача решается двойственным методом, приведём неравенства к виду. После этого, как и в «прямом» симплексном методе, для превращения неравенств в равенства вводятся дополнительные переменные, в данной задаче – х5, х6, х7.

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

В соответствии с обычными правилами заполняем начальную симплексную таблицу. Выбираем ключевую строку. Выберем в качестве ключевой первую строку (Х₀ – х₅= -600, это самое большое по величине отрицательное значение из трех).

Таблица № 1.

Далее вычисляем строку δ.

Выбираем ключевой столбец – по минимальному δ=0,7 в столбце Х₂.

После этого вычисляем столбец β, обычным образом выполняем преобразование Жордана-Гаусса и получаем таблицу № 2.

Таблица № 2.

В таблице № 2 всего одно отрицательное значение в столбце Х₀ – х₇= - 360. Третью строку поэтому принимаем в качестве ключевой и вычисляем «δ».

Минимальное δ=0,1 в столбце Х1, который и принимаем в качестве ключевого.

Выполняем преобразование и получаем таблицу № 3.

Таблица № 3.

Среди х -ов по-прежнему находится отрицательный: х₂= -20 в первойстроке.

Принимаем эту строку в качестве ключевой и вычисляем «δ».

Минимальное δ =0,6 в столбце Х4, который принимаем в качестве ключевого. Выполняем симплексное преобразование и получаем таблицу № 4.

Таблица № 4.

В таблице № 4 в столбце Х₀ отрицательных значений нет.

Все двойственные оценки ≤0 (0, -0.6, -3.6, 0, -0.6, -0.3), что в задаче на минимум свидетельствует об оптимальности плана.

2)

В базисный набор последней симплексной таблицы входят «основные переменные» х₁=132 и х4=8. Это означает, что оптимальный план предусматривает строительство

132 домов серии А1 и

8 домов серии А4.

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

Это значит, что дома серий А2 и А3 по оптимальному плану строиться не должны. Общая стоимость строительства (минимальная) составляет 468 млн.руб.

3)

Проверим, выполняются ли потребности в квартирах.

Однокомнатные: 4*132 + 9*8 = 600 – требование выполнено

Двухкомнатные: 2*132 + 18*8 = 408 – сверх необходимых потребностей (требуется 360)

Трёхкомнатные: 2*132 + 12*8 = 360 – требование выполнено

4)

Отрицательные двойственные оценки в столбцах Х2 и Х3 показывают, что если потребовать, чтобы х₂ = 1 или х₃=1, то значение целевой функции увеличится соответственно на –d2= 0,6 или на –d3= 3,6. Тем самым при вводе в план строительства одного дома серии А2 общая стоимость строительства возрастет на 0,6 млн.руб.(600 тыс. руб.), а дома серии А3 – на 3,6 млн.руб.(360 тыс. руб.)

5)

5.1. На сколько возрастет стоимость строительства при увеличении потребностей в трехкомнатных квартирах на 10%(=36 квартир)?

Возьмём х₇ = 36. Тогда

Двойственная оценка d7=-0,3 показывают, что при увеличении потребностей в трёхкомнатных квартирах на 36, общая стоимость строительства увеличится на 10,8 млн.руб.

5.2. На сколько снизится стоимость строительства при уменьшении потребностей в однокомнатных квартирах на 20%(=120 квартир)?

Возьмём х₅ = - 120. Тогда

Двойственная оценка d5=-0,6 показывают, что при уменьшении потребностей в однокомнатных квартирах на 120, общая стоимость строительства уменьшится на 72 млн.руб.

5.3. Изменится ли стоимость строительства при изменении потреб­ностей в двухкомнатных квартирах; если ДА, то на сколько - в расчете на 1 двухкомнатную квартиру.

Не изменится, так как двойственная оценка d6 =0.