Материал: Методы оптимизации. методические указания для организации самостоятельной работы по курсу «Высшая математика». Пантелеев И.Н
|
Находим разрешающий элементx1 |
и меняемx2 « x4 . |
||||||||||
Заполним новую таблицу. |
|
|
|
|
|
|
|
|||||
|
|
|
|
bi |
|
x1 |
|
|
x4 |
|
x3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L1 |
|
96 |
|
-12 |
-6 |
-8 |
-8 |
-6 |
|
||
|
|
|
|
120 |
|
|
|
-6 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
|
12 |
|
1 |
1 |
-1 |
-1 |
0 |
|
||
|
|
|
|
12 |
|
|
|
0 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x5 |
|
-8 |
|
-1 |
1 |
0 |
0 |
-1 |
|
||
|
|
|
|
-8 |
|
|
|
-1 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x6 |
|
8 |
|
1 |
0 |
-1 |
-1 |
-1 |
|
||
|
|
|
|
0 |
|
|
|
1 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Далее заменим x3 « x5 |
|
|
|
|
|
|
|
||||
|
|
|
|
bi |
|
x1 |
|
|
x4 |
|
x5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L1 |
|
|
144 |
|
-6 |
|
|
-8 |
|
-6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
|
|
12 |
|
1 |
|
|
-1 |
|
0 |
|
|
x3 |
|
|
8 |
|
1 |
|
|
0 |
|
-1 |
|
|
x6 |
|
|
0 |
|
0 |
|
|
-1 |
|
1 |
|
|
Так как |
в первой |
строке |
все свободные переменны |
||||||||
отрицательны, то L1min = 144 при x1 = 0 , x2 |
= 12 , x3 = 8 . |
|||||||||||
|
Математическая модель относительно |
оси y |
запишется в |
|||||||||
виде |
L2 = 10 y1 + 8 y2 + 6 y3 +10 y4 ; |
|
|
|
||||||||
|
|
|
|
|
|
|
||||||
|
y1 + y4 |
³ 15; y1 + y3 |
³ 10; |
y2 + y3 ³ 6; y2 + y4 ³ 11. |
||||||||
|
Через базисные переменные |
|
|
|
|
|
|
|||||
L2 = 0 - (-10 y1 - 8 y2 - 6 y3 -10 y4 ),
y5 = -15 - (-y1 - y4 ); y6 = -10 - (-y1 - y3 ); y7 = -6 - (-y2 - y3 ); y8 = -11 - (-y2 - y4 ).
Составим таблицу
9
|
|
|
bi |
|
|
|
y1 |
|
y2 |
y3 |
|
y4 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L2 |
0 |
|
-10 |
-10 |
|
-8 |
-8 |
|
-6 |
|
|
-10 |
|
||
|
|
100 |
|
|
|
|
|
4 |
|
-10 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y5 |
-15 |
|
-1 |
-1 |
|
0 |
0 |
|
0 |
|
|
-1 |
|
||
|
|
-5 |
|
|
|
|
|
1 |
|
-1 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y6 |
-10 |
|
-1 |
-1 |
|
0 |
0 |
|
-1 |
|
|
0 |
|
||
|
|
10 |
|
|
|
|
|
1 |
|
0 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y7 |
-6 |
|
0 |
0 |
|
-1 |
-1 |
|
-1 |
|
|
0 |
|
||
|
|
-6 |
|
|
|
|
|
-1 |
|
0 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y8 |
-11 |
|
0 |
0 |
|
-1 |
-1 |
|
0 |
|
|
-1 |
|
||
|
|
-11 |
|
|
|
|
|
0 |
|
-1 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Делаем замену y1 |
« y6 |
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
bi |
|
|
|
y6 |
|
y2 |
|
y3 |
|
|
y4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
L2 |
|
100 |
|
-10 |
0 |
-8 |
-8 |
|
4 |
|
-10 |
|
|||
|
|
|
150 |
|
|
|
|
-6 |
|
-10 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
y5 |
|
-5 |
5 |
|
-1 |
1 |
0 |
0 |
|
1 |
|
-1 |
|
||
|
|
|
|
|
|
|
|
|
-1 |
|
-1 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
y1 |
|
10 |
|
|
-1 |
-1 |
0 |
0 |
|
1 |
|
0 |
|
||
|
|
|
10 |
|
|
|
|
1 |
|
0 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
y7 |
|
-6 |
-6 |
0 |
0 |
-1 |
-1 |
|
-1 |
|
0 |
|
|||
|
|
|
|
|
|
|
|
-1 |
|
0 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
y8 |
|
-11 |
-6 |
0 |
1 |
-1 |
-1 |
|
0 |
|
-1 |
|
|||
|
|
|
|
|
|
|
|
-1 |
|
-1 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10
Еще раз заменяем y4 « y5
|
|
bi |
|
y6 |
y2 |
|
y3 |
|
|
y5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
L2 |
|
150 |
|
0 |
-8 |
-2 |
-6 |
6 |
-10 |
|
|
|
|
186 |
|
0 |
|
|
|
-10 |
|
||
y4 |
|
5 |
|
1 |
0 |
1 |
-1 |
-1 |
-1 |
-1 |
|
|
|
11 |
|
1 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
y1 |
|
10 |
|
-1 |
0 |
-1 |
1 |
1 |
0 |
0 |
|
|
|
4 |
|
-1 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
y7 |
|
-6 |
|
0 |
-1 |
1 |
-1 |
-1 |
0 |
0 |
|
|
|
6 |
|
0 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
y8 |
|
-6 |
|
1 |
-1 |
0 |
-1 |
1 |
-1 |
-1 |
|
|
|
0 |
|
1 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
Отсюда |
имеем: |
L = 186 |
при y1 = |
4; y2 |
= 0; |
|
y3 = 6; |
|
|||
y4 = 11. |
Следовательно, минимум |
пробега |
транспорта в |
||||||||
горизонтальном и |
вертикальном |
направлениях |
составляет |
||||||||
L = 144 +186 = 330 км.
3. РАСЧЕТ ОПТИМАЛЬНОГО ЧИСЛА РАБОТНИКОВ НА ПРЕДПРИЯТИИ
1 °. Характерной особенностью ряда предприятий является неравномерность поступления нагрузки по часам суток, дням
недели и месяцам года. В условиях постоянного штата необходимо, с одной стороны, обеспечить выполнение всей работы, а с другой— обеспечить выполнение работы минимальным количеством работников.
Обозначим через x j — число работников, работающих
по j - му графику, |
bi - нагрузку в i - й |
рабочий день, |
||
выраженную |
в |
числе |
требуемых |
работников; a - |
|
|
|
|
ij |
11
коэффициент, равный единице, если по j - му графику предусматривается работа в i - й день, и нулю, если в тот день предусматривается выходной. Задача может быть сформулирована так: требуется найти минимум целевой функции L = x1 + x2 + ... + xn при выполнении следующих ограничений
a11 x1 + a12 x2 + ... + a1n xn ³ b1 ;
a21 x1 + a22 x2 + ... + a2n xn ³ b2 ;
……………………………….
am1 x1 + am 2 x2 + ... + amn xn ³ bm .
|
2°. Для |
простоты |
вычислений |
рассмотрим |
|
пример |
||||
четырехдневной |
рабочей |
недели |
с |
двумя |
выходным, |
|||||
исходные данные для которого приведены в таблице |
|
|
||||||||
|
Число |
|
|
|
Дни недели |
|
|
|
||
|
работников |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
2 |
|
3 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
|
В |
|
В |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 |
|
|
|
|
|
В |
В |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x3 |
|
В |
|
|
|
|
В |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x4 |
|
|
|
В |
|
В |
|
|
|
|
x5 |
|
В |
|
|
|
В |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x6 |
|
|
|
В |
|
|
В |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bi |
|
100 |
|
80 |
|
40 |
60 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Запишем задачу линейного программирования следующим образом
12
|
|
|
|
L = x1 + x2 + x3 + x4 + x5 + x6 |
|
|
|||||||
|
при следующих ограничениях |
|
|
|
|
|
|||||||
|
|
|
|
x2 + x4 + x6 ³ 100; x2 |
+ x3 + x5 |
³ 80; |
|
||||||
|
|
|
x1 + x3 + x6 |
³ 40; x1 + x4 |
+x5 ³ 60; |
x j |
³ 0. |
|
|||||
|
Введем базисные переменные и перепишем ограничения в |
||||||||||||
виде, удобном для использования симплекс-метода |
|
||||||||||||
|
y1 = -100 - (-x2 - x4 |
- x6 ); |
y2 = -80 - (-x2 |
- x3 - x5 ); |
|
||||||||
|
|
y5 = -40 - (-x1 - x3 - x6 ); y4 = -60 - (x1 - x4 - x5 ); |
|
||||||||||
|
|
|
|
L = 0 - (-x1 - x2 - x3 - x4 - x5 - x6 ). |
|
||||||||
|
Запишем решение в виде таблицы |
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bi |
|
x1 |
|
x2 |
|
x3 |
|
|
x4 |
x5 |
x6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
-1 |
|
-1 |
|
-1 |
|
-1 |
|
-1 |
-1 |
L |
|
60 |
|
0 |
|
-1 |
|
|
-1 |
|
-1 |
0 |
-1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-100 |
|
0 |
|
0 |
|
-1 |
|
-1 |
|
0 |
-1 |
y1 |
|
-40 |
|
1 |
|
0 |
|
|
-1 |
|
-1 |
0 |
-1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-80 |
|
0 |
|
-1 |
|
-1 |
|
0 |
|
-1 |
0 |
y2 |
|
-80 |
|
0 |
|
-1 |
|
|
-1 |
|
0 |
-1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-40 |
|
-1 |
|
0 |
|
-1 |
|
0 |
|
0 |
-1 |
y3 |
|
-40 |
|
-1 |
|
0 |
|
|
-1 |
|
0 |
0 |
-1 |
|
|
-60 |
|
-1 |
|
0 |
|
0 |
|
|
|
-1 |
0 |
y4 |
|
60 |
|
1 |
|
0 |
|
|
0 |
-1 |
1 |
0 |
|
Выбираем разрешающий элемент, находим l = -1и
переводим базисную переменную y4 в разряд свободной
x4 .Перепишем таблицу заменяя y4 « x4 .
13