Математическое моделирование

Задача  №7: 

      Дано:

      Аудитории и лаборатории университета рассчитаны на не более чем 5000 студентов. Университет  принимает не более 4000 студентов  своей страны и разрешает прием  любого количества иностранных студентов.

      Персонал  университета составляет 440 человек. Для  обучения 12 студентов своей страны и 10 иностранных требуется один преподаватель.

Необходимо, чтоб   40 % студентов своей страны и 80 % иностранных студентов могли разместиться в аудиториях одновременно, где имеется 2800 мест . Университет получает 2000 условных единиц в год от правительства за каждого студента своей страны и по 3000 ед. с одного иностранного студента.

      Найти:

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

Решение: 

Решаем задачу максимизации прибыли, используя симплекс-алгоритм.

Найдем функцию  цели:  

, где   х₁ – количество отечественных студентов

          х₂ – количество иностранных  студентов

Определим ограничения:

 (по общему количеству мест)

(по  количеству преподавателей для своих студентов)

(по  количеству преподавателей  для иностранных   студентов)

  (по количеству мест в аудиториях)

(по  количеству отечественных  студентов)

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

   Обозначим функцию цели через z, ограничения преобразуем в равенства путём ввода свободных переменных. Тогда в стандартной форме с неотрицательными свободными переменными  X₃, X₄,  X₅, Х₆, X₇  получим систему уравнений, имеющую  вид:

   

   Или в виде удобном для решения  в программе:

   

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

   

   Приведем  текст программы и ответ

Текст программы:

10 REM Симплекс-метод  (минимизация)

15 REM с заданным  базисным допустимым решением

20 REM Ввести количество ограничений и переменных

30 READ m, n

40 m1 = m + 1

50 DIM a(m1, n), bs(m), nb(n), v(m1)

60 PRINT "Линейное  программирование"

100 REM Ввести коэфф. для ограничений и целевой

105 REM функции построчно

110 FOR i = 1 TO m1: FOR j = 1 TO n

120 READ a(i, j)

130 NEXT j: NEXT i

150 REM Ввести начальные значения базисных переменных

155 REM целевой  функции в массив a(i,0)

160 FOR i = 1 TO m1: READ a(i, 0): NEXT i 

200 REM Ввести базисные переменные: BS-метка базисной

205 REM переменной  в ограничении i

210 FOR i = 1 TO m: READ bs(i): NEXT i 

250 REM Пометить небазисные переменные

255 REM если j-небазисная  переменная, то nb(j)=0

260 FOR i = 1 TO m: nb(bs(i)) = 1: NEXT i 

290 REM Напечатать таблицу

300 PRINT "Первоначальная  таблица"

310 GOSUB 3000: STOP 

400 zero = 1E-08 

490 REM Найти наименьший коэфф. в строке z, т.е. в строке m1

500 min = -zero: s = 0

510 FOR j = 1 TO n

520 IF nb(j) = 1 THEN GOTO 550

530 IF a(m1, j) >= min THEN GOTO 550

540 min = a(m1, j): s = j

550 NEXT j

560 REM если s=0, то  все коэфф. положительны

565 REM и минимум найден

570 IF s = 0 THEN GOTO 2000 

740 REM Найти строку переменных, которую следует

745 REM исключить  из базиса по условию минимума b(i)/a(i,s)

750 min = 1E+20: r = 0

760 FOR i = 1 TO m

770 IF a(i, s) <= zero THEN GOTO 810

780 rt = a(i, 0) / a(i, s)

790 IF rt >= min THEN GOTO 810

800 r = i: min = rt

810 NEXT i 

890 REM если r=0, то  имеет место решение без ограничений

900 IF r = 0 THEN GOTO 1800

910 PRINT "Ведущий  элемент находится в строке"; r; "столбца"; s

920 PRINT "" 

990 REM Разделить ведущую строку на ведущий элемент

1000 pv = a(r, s)

1010 FOR j = 0 TO n: a(r, j) = a(r, j) / pv: NEXT j 

1040 REM Вычислить новую каноническую форму,

1045 REM запомнив, ведущий столбец до его изменения

1050 FOR i = 1 TO m1: v(i) = a(i, s): NEXT i

1070 FOR i = 1 TO m1

1080 IF i = r THEN GOTO 1120

1090 FOR j = 0 TO n

1100 a(i, j) = a(i, j) - v(i) * a(r, j)

1110 NEXT j

1120 NEXT i 

1150 REM Переназначить и повторно пометить базисные

1155 REM и небазисные  переменные

1160 nb(bs(r)) = 0: nb(s) = 1: bs(r) = s

1170 REM Счетчик  итераций

1180 k = k + 1

1190 REM Напечатать новую таблицу

1200 PRINT "итерация"; k; ""

1210 GOSUB 3000: STOP

1240 REM Повторить итерационную процедуру

1250 GOTO 500 

1800 PRINT "Переменная s не имеет ограничений"

1810 GOSUB 3000: STOP

1820 GOTO 2500 

2000 PRINT "Окончательное  решение"

2010 PRINT "Ограничение   Базис    Значение"

2020 pb = 144

2030 FOR i = 1 TO m

2040 PRINT " "; i; "          "; bs(i);

2050 pa = a(i, 0): GOSUB 9000: PRINT ""

2060 NEXT i 

2090 PRINT "Минимум функции z равен "; -a(m1, 0)

2100 GOSUB 3000

2500 END 

3000 PRINT "Базис  Значение";

3010 FOR j = 1 TO n: PRINT "   Х"; j; "  "; : NEXT j

3020 PRINT ""

3030 pb = 133

3040 FOR i = 1 TO m1

3050 IF i = m1 THEN PRINT " -z"; : GOTO 3080

3060 PRINT " "; bs(i);

3080 FOR j = 0 TO n

3090 pa = a(i, j): GOSUB 9000

3100 NEXT j

3110 PRINT ""

3120 NEXT i: PRINT ""

3200 RETURN 

4001 DATA 5,7

4002 DATA 1,1,1,0,0,0,0

4003 DATA 0.0833,0,0,1,0,0,0

4004 DATA 0,0.1,0,0,1,0,0

4005 DATA 0.4,0.8,0,0,0,1,0

4006 DATA 1,0,0,0,0,0,1

4007 DATA -2000,-3000,0,0,0,0,0

4011 DATA 5000,440,440,2800,4000,0

4012 DATA 3,4,5,6,7 

9000 pc = INT(pb / 100)

9010 p$ = "         "

9020 IF pc = 0 THEN PRINT "": GOTO 9040

9030 PRINT LEFT$(p$, pc);

9040 pc = pb - 100 * pc

9050 pd = INT(pc / 10): pc = pc - 10 * pd

9060 IF pd = 0 THEN pd = 1

9070 IF pa < 0 THEN p$ = p$ + "-"

9080 pe = ABS(pa)

9090 pe = pe + 5 * 10 ^ (-1 - pc)

9100 IF pe >= 10 ^ pd THEN PRINT "   "; pa; : RETURN

9110 p$ = p$ + MID$(STR$(INT(pe)), 2, pd)

9120 PRINT RIGHT$(p$, pd + 1);

9130 IF pc = 0 THEN RETURN

9140 PRINT ".";

9150 pe = INT((pe - INT(pe)) * 10 ^ pc)

9160 p$ = "000000000"

9170 p$ = p$ + MID$(STR$(pe), 2, pc)

9180 PRINT RIGHT$(p$, pc); : RETURN 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Результат: 

     Ответ:

Оптимальное значение функции цели равно:

Z_opt = 12∙10⁶ (условных единиц)

При количестве студентов своей страны равным:

Х₁=3000 (человек)

И при количестве иностранных студентов равным:

Х₂=2000 (человек)

      Запишем для нашей  задачи  двойственную, которая получается с помощью следующих преобразований исходной задачи:

     1. j-столбец ограничений исходной задачи становится j-той строкой ограничений двойственной задачи.

     2. Свободный столбец ограничений  исходной задачи становится коэффициентами  целевой функции двойственной  задачи.

     3. Коэффициенты целевой функции  исходной задачи становятся свободным  столбцом ограничений двойственной  задачи.

     4. Знаки ограничений меняют значения  на противоположные. Требование максимизации исходной задачи заменяется в двойственной требованием минимизации.  

     Получим:

     

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

     Оптимальное  значение функции цели двойственной задачи равно значению прямой : 12∙10⁶  (условных единиц). 
 

     При значениях  у равных:

     Так как лимит учебных мест использован  полностью и при этом количество задействованных преподавателей  равно:

      ,

      То есть при 3000 своих студентах и 2000 иностранных необходимо 250 преподавателей, значит 190 преподавателей еще не задействовано, следовательно, ввод дополнительного числа преподавателей, с экономической точки зрения, не требуется. 

     Окончательно  получим, оптимальное число студентов при данных ограничениях, своей страны равно 3000 человек, иностранных - 2000  человек, что приносит университету максимальное значение прибыли равное  12∙10⁶  (условных единиц). Дополнительный ввод преподавателей не требуется.