90296

Формування виробничого плану випуску продукції

Курсовая

Информатика, кибернетика и программирование

В даному курсовому проекті використовується метод лінійного програмування двоїстий симплекс. Лінійне програмування – розв’язує задачі подані лінійними моделями , тобто ті, які мають лінійну цільову функцію (ЦФ) та лінійну область допустимих рішень (ОДР).

Украинкский

2015-06-02

1.36 MB

1 чел.

Міністерство освіти і науки України

Київський національний університет будівництва і архітектури

Кафедра інформаційних технологій

КУРСОВА РОБОТА

з дисципліни 

«Математичні методи дослідження операцій»

на тему:

«Формування виробничого плану випуску продукції»

Виконала студентка групи ПНК-41

Леонченко А.О.

Керівник роботи:

Бабич В. І.

Київ 2010 р.

Зміст

  1.  


Вступ

Дослідження операцій – це наука про моделі і методи оптимального управління, а також про систему прийняття рішень з допомогою оптимального управління.[1,7]

В даному курсовому проекті використовується метод лінійного програмування двоїстий симплекс.

Лінійне програмування – розв’язує задачі подані лінійними моделями , тобто ті, які мають лінійну цільову функцію (ЦФ) та лінійну область допустимих рішень (ОДР).


1.Постановка задачі      

У районі лісового масиву діють лісопильний завод і фабрика, на якій виготовлюють фанеру. Щоб одержати 2,5 м3 комплектів пиломатеріалів, треба витратити l1 м3 ялинових і 1 м3 пихтових лісоматеріалів. Для готування 100 м2 фанери потрібно l2 м3 ялинових і 2 м3 пихтових лісоматеріалів. Лісовий масив містить E м3 ялинових і Р м3 пихтових лісоматеріалів. Протягом планованого періоду необхідно зробити принаймні Q1 м3 пиломатеріалів і Q2 м3 фанери. 1 м3 пиломатеріалів дає D1 грн., а 100 м2 фанери – D2 грн. прибутку

Яка кількість пиломатеріалів і фанери потрібно зробити, щоб прибуток був максимальним?

Номер варіанта

L1

ρ1

l2

ρ2

Е

P

Q1

Q2

D1

D2

3

2,6

7,5

5,1

8,5

90

200

9

1000

20

50

2. Розробка математичної моделі

- пиломатеріали (м3)

- фанера (м2)

                         


3. Вибір та обґрунтування методів рішення задачі.

Дану задачу можна вирішувати наступними методами:

  •  Двоїстий симплекс-метод (програмую)

Є ряд задач лінійного програмування, які можуть бути розв’язані тільки двоїстим симплекс-методом, наприклад деякі задачі мінімізації. Для кожної моделі існує поняття двоїстої задачі, тобто запис задачі іншими змінними для розв’язання потім іншим методом, який потрібний для перевірки правильності симплекс-методу та інших методів ЛП.

Метод базується на постійному поліпшенні умови недопустимості розв’язку. На його основі створена програма double.exe. Якщо в прямому симплекс-методі алгоритм базується на постійному покращенні значенні цільової функції, тобто значення симплекс-таблиці                        , то в ДСМ алгоритм - на постійному вилученні розв’язку, тобто всі базисні змінні в кінці xn є Bx , xn<=0, стануть позитивними.

  •  Симплекс-метод

Даний метод базується на табличних перетвореннях Джордана-Гауса моделі, поданої в канонічному вигляді. Метод симплекс-таблиць або метод переміщення по кутах (по симплексах) має в основі ітераційний розрахунок з максимально можливою кількістю ітерацій:

С=m!/n!(m-n!)

де C - максимально можлива кількість ітерацій (умова перевірки на зацикленість);

n - кількість рівнянь;

m -  кількість змінних у канонічному вигляді.

Симплекс-метод базується на постійних перетвореннях таблиці:                                        


                                                                                                              

1

2

3

...

n

Cx    Bx   A0       A1   ...   Am

               0     1     ...    m

де:  Bx  - базисні змінні;

 Cx  - коефіцієнти цільової функції при базисних змінних;

- симплекс різниця;

A1 ... Am - коефіцієнти в обмеженнях;

A0 - права частина.

Кожна ітерація полягає в заміні (перерахунку) базисної змінної.


4. Алгоритм двоїстого симплекс-методу рішення задачі та опис програми.

1. Зведення ЦФ до максимуму, а обмежень до рівностей (канонічний вигляд).

2. Запис двоїстої задачі

             

3. Побудова незалежних векторів на підставі рядків ДЗ.

   

4. Вибір спряженого базису:

  •  Довільний вибір m рівнянь;
  •  Розв’язання цієї системи m з рівнянь;
  •  Підстановка розв’язку в кожне із залишених обмежень та перевірка: чи задовольняє спряжений базис;
  •  Якщо спряжений базис задовольняє, то формування псевдолану (розрахунок симплекс-таблиці);
  •  Якщо спряжений базис не задовольняє, то треба обрати новий. Якщо на генерації нових сполучень не буде знайдено спряжений базис, то немає розв’язку.

Спряжений базис (А1А4А5А6)

5. Заповнення симплекс-таблиці.

6. Вибір направляючого елементу.

7. Всі інші симплекс-перетворення в ДСМ аналогічні прямому СМ.

                                                      

ні

 так 

                                                                              

 Рис. 1 Алгоритм двоїстого симплекс-методу


5. Ітерації програмного рішення задачі.

(

c) Leonchenko Anna .... PNK-41

Условие считывается из файла <in.txt>

Вывод выполняется в файл <out.txt>

Размерность задачи 4x6:

max(20x1+0.50x2+0x3+0x4+0x5+0x6)

{1}  1x1+0.05x2+1.04x3+0x4+0x5+0x6=86.53

{2}  0x1-0.06x2-3.12x3+1x4+0x5+0x6=-59.60

{3}  0x1+0.05x2+1.04x3+0x4+1x5+0x6=77.59

{4}  0x1-1x2+0x3+0x4+0x5+1x6=-1000

Iteracija #   1

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  20    0.50       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     20     X1   86.53       1    0.05    1.04       0       0       0

      0     X4  -59.60       0   -0.06   -3.12       1       0       0

      0     X5   77.59       0    0.05    1.04       0       1       0

      0     X6   -1000       0      -1       0       0       0       1

------------------------------------------------------------------

R  1730.60       0    0.48   20.80       0       0       0

-------------------------------------------------------------------

Iteracija #   2

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  20    0.50       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     20     X1   37.53       1       0    1.04       0       0    0.05

      0     X4    2.40       0       0   -3.12       1       0   -0.06

      0     X5   28.59       0       0    1.04       0       1    0.05

   0.50     X2    1000       0       1       0       0       0      -1

------------------------------------------------------------------

R  1250.60       0       0   20.80       0       0    0.48

-------------------------------------------------------------------

Rishennja znajdeno!!! Param-pam-pam

Z= 1250.60

X = (37.53  1000  0  2.40  28.59  0  )


Опис процедур програми:

Function value – “,” міняє на “.”;

Procedure prov – Обрізання пробілів на початку та в кінці рядку;

Procedure error -  недопустимий символ;

Function ReadData – зчитування з файлу;

Function Druk – перетворює real в integer, знаходить дробову частину, перетворює число в рядок;

Procedure WriteUmovu- вивід даних зчитаних з вхідного файлу;

Procedure vivod вивід ітерацій;

Procedure RozDelta – розрахунок дельта та запис в симплекс-таблицю;

Function napr_str визначення спрямовуючого рядка;

Function napr_st визначення спрямовуючого стовпчика;

Procedure pererah – перерахунок симплекс-таблиці за формулою прямокутника;

Function simpl -  перевірка.


6. Алгоритм методу симплекс-таблиць рішення задачі.

 

1. Визначення спрямовуючого стовпчика j*

Якщо    відсутнє, то розв’язок  знайдено: базисні змінні дорівнюють, а небазисні – 0

2. Визначення спрямовуючого рядка і*

Якщо і*   відсутнє, тобто в стовпчику знаходиться значення не більше 0, то розв’язок відсутній (ОДР не обмежена зверху), інакше фіксуємо спрямовуючий елемент: (2   1)=1

3. Перерахунок таблиці (власне заміна базисних змінних):

  •  ділення значень спрямовуючого рядка на спрямовуючий елемент:

  •  обнулення спрямовуючого стовпця, крім спрямовуючого елемента:

  •  перерахунок решти значень за формулою прямокутників:

4. Перевірка ітерації:

  •  цільова функція має не зменшуватися;
  •  номер ітерації має не перевищувати їхню максимальну кількість:

  •  базисні змінні мають мати одиничний вектор;
  •  розрахунок   має співпадати як за формулою спрямовуючого стовпчика, так і за формулою «прямокутника».

Розв’язок знайдено, тому що всі     0. Після розрахунку потрібно виконати наступну перевірку:

  •  чи всі М-змінні дорівнюють 0 якщо ні, то розв’язок відсутній або ж вибрано занадто малий коефіцієнт m.
  •  Значення Z має дорівнювати значенню  Ci Xi

   Рис.2 Алгоритм симплекс-методу

Канонічна форма, розмірність 4*8


Ітерації рішення задачі вручну.

Размерность задачи НЛП - 4 х 8

max( 20X1 +0.5X2-200X6-200X8 )

{1}  1.04X1 + 0.051X2 + 1X3   = 90

{2}  3X1 + 0.085X2 + 1X4   = 200

{3}  1X1 + -1X5 + 1X6   = 9

{4}  1X2 + -1X7 + 1X8   = 1000

И  т  е  р  а  ц  и  я________1

=================================================================

Цел.ф.           20    0.5   0     0     0     -200  0     -200  

-----------------------------------------------------------------

     Bx  A0    A1    A2    A3    A4    A5    A6    A7    A8    

0     X3  90    1.04  0.051 1     0     0     0     0     0     

0     X4  200   3     0.085 0     1     0     0     0     0     

-200  X6  9     1     0     0     0     -1    1     0     0     

-200  X8  1000  0     1     0     0     0     0     -1    1     

-----------------------------------------------------------------

Разница   -2.0E+05 -220  -200  0     0     200   0     200   0     

=================================================================

               3->1                                            

Вводится в базис переменная Х1     вместо  Х6

И  т  е  р  а  ц  и  я________2

=================================================================

Цел.ф.           20    0.5   0     0     0     -200  0     -200  

-----------------------------------------------------------------

     Bx  A0    A1    A2    A3    A4    A5    A6    A7    A8    

0     X3  80.64 0     0.051 1     0     1.04  -1.04 0     0     

0     X4  173   0     0.085 0     1     3     -3    0     0     

20    X1  9     1     0     0     0     -1    1     0     0     

-200  X8  1000  0     1     0     0     0     0     -1    1     

-----------------------------------------------------------------

Разница   -2.0E+05 0     -200  0     0     -20   220   200   0     

=================================================================

                     4->2                                      

Вводится в базис переменная Х2     вместо  Х8

И  т  е  р  а  ц  и  я________3

=================================================================

Цел.ф.           20    0.5   0     0     0     -200  0     -200  

-----------------------------------------------------------------

     Bx  A0    A1    A2    A3    A4    A5    A6    A7    A8    

0     X3  29.64 0     0     1     0     1.04  -1.04 0.051 -0.0  

0     X4  88    0     0     0     1     3     -3    0.085 -0.0  

20    X1  9     1     0     0     0     -1    1     0     0     

0.5   X2  1000  0     1     0     0     0     0     -1    1     

-----------------------------------------------------------------

Разница   680   0     0     0     0     -20   220   -0.5  200.5

=================================================================

                                       1->5                    

Вводится в базис переменная Х5     вместо  Х3

И  т  е  р  а  ц  и  я________4

=================================================================

Цел.ф.           20    0.5   0     0     0     -200  0     -200  

-----------------------------------------------------------------

     Bx  A0    A1    A2    A3    A4    A5    A6    A7    A8    

0     X5  28.5  0     0     0.962 0     1     -1    0.049 -0.0  

0     X4  2.5   0     0     -2.88 1     0     0     -0.0  0.062

20    X1  37.5  1     0     0.962 0     0     0     0.049 -0.0  

0.5   X2  1000  0     1     0     0     0     0     -1    1     

-----------------------------------------------------------------

Разница   1250  0     0     19.23 0     0     200   0.481 199.5

=================================================================

Р е ш е н и е   н а й д е н о

X = ( 37.5 1000 0 2.5 28.5 0 0 0  )

Z = 1250

 

  1.  
    Висновок та дослідження на чутливість моделі.

Модифікація вхідних значень

Пошукові

xі

Цільова функція

Z

Примітка

1

Лісовий масив складається з Е=100м3

Р=250м3

L1=2,6

L2=5,1

P1=7,5

P2=8,5

E=100

P=250

Q1=9

Q2=1000

D1=20

D2=0,5

1520

Зі збільшенням площі лісового масиву  сумарний прибуток заводу збільшуються.

2

Прибуток приносять:

Пиломатеріали D1=30грн

Фанера D2=2грн

L1=2,6

L2=5,1

P1=7,5

P2=8,5

E=100

P=250

Q1=9

Q2=1000

D1=30

D2=3

3125,90

Сумарний прибуток збільшуються.

3

Якщо використовувати менше ялинових лісоматеріалів 1=2,5м3

L1=2,5

L2=5,1

P1=7,5

P2=8,5

E=100

P=250

Q1=9

Q2=1000

D1=20

D2=0,5

1830,60

Сумарний прибуток  збільшуються, так як матеріал використовується менше.

Рішення інших задач

Приклад№1

Вхідний файл:

4 6

20 0.5 0 0 0 0

1 0.049 1.04 0 0 0 = 100

0 -0.062 -3.12 1 0 0 = -40

0 0.049 1.04 0 1 0 = 77.59

0 -1 0 0 0 1 = -1000

Вихідний файл:

(c) Leonchenko Anna .... PNK-41

File dlja zchityvannja <in1.txt>

Vivid vukon v file <out1.txt>

Rozmirnist zadachi 4x6:

max(20x1+0.50x2+0x3+0x4+0x5+0x6)

{1}  1x1+0.05x2+1.04x3+0x4+0x5+0x6=100

{2}  0x1-0.06x2-3.12x3+1x4+0x5+0x6=-40

{3}  0x1+0.05x2+1.04x3+0x4+1x5+0x6=77.59

{4}  0x1-1x2+0x3+0x4+0x5+1x6=-1000

Iteracija #   1

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  20    0.50       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     20     X1     100       1    0.05    1.04       0       0       0

      0     X4     -40       0   -0.06   -3.12       1       0       0

      0     X5   77.59       0    0.05    1.04       0       1       0

      0     X6   -1000       0      -1       0       0       0       1

------------------------------------------------------------------

R     2000       0    0.48   20.80       0       0       0

-------------------------------------------------------------------

Iteracija #   2

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  20    0.50       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     20     X1      51       1       0    1.04       0       0    0.05

      0     X4      22       0       0   -3.12       1       0   -0.06

      0     X5   28.59       0       0    1.04       0       1    0.05

   0.50     X2    1000       0       1       0       0       0      -1

------------------------------------------------------------------

R     1520       0       0   20.80       0       0    0.48

-------------------------------------------------------------------

Rishennja znajdeno!!! Param-pam-pam

Z=    1520

X = (51  1000  0  22  28.59  0  )

Приклад№2

Вхідний файл:

4 6

30 2 0 0 0 0

1 0.049 1.04 0 0 0 = 86.53

0 -0.062 -3.12 1 0 0 = -59.6

0 0.049 1.04 0 1 0 = 77.59

0 -1 0 0 0 1 = -1000

Вихідний файл:

(c) Leonchenko Anna .... PNK-41

File dlja zchityvannja <in2.txt>

Vivid vukon v file <out2.txt>

Rozmirnist zadachi 4x6:

max(30x1+2x2+0x3+0x4+0x5+0x6)

{1}  1x1+0.05x2+1.04x3+0x4+0x5+0x6=86.53

{2}  0x1-0.06x2-3.12x3+1x4+0x5+0x6=-59.60

{3}  0x1+0.05x2+1.04x3+0x4+1x5+0x6=77.59

{4}  0x1-1x2+0x3+0x4+0x5+1x6=-1000

Iteracija #   1

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  30       2       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     30     X1   86.53       1    0.05    1.04       0       0       0

      0     X4  -59.60       0   -0.06   -3.12       1       0       0

      0     X5   77.59       0    0.05    1.04       0       1       0

      0     X6   -1000       0      -1       0       0       0       1

------------------------------------------------------------------

R  2595.90       0   -0.53   31.20       0       0       0

-------------------------------------------------------------------

Iteracija #   2

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  30       2       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     30     X1   37.53       1       0    1.04       0       0    0.05

      0     X4    2.40       0       0   -3.12       1       0   -0.06

      0     X5   28.59       0       0    1.04       0       1    0.05

      2     X2    1000       0       1       0       0       0      -1

------------------------------------------------------------------

R  3125.90       0       0   31.20       0       0   -0.53

-------------------------------------------------------------------

Rishennja znajdeno!!! Param-pam-pam

Z= 3125.90

X = (37.53  1000  0  2.40  28.59  0  )

Приклад№3

Вхідний файл:

4 6

20 0.5 0 0 0 0

1 0.02 1.04 0 0 0 = 86.53

0 -0.062 -3.12 1 0 0 = -59.6

0 0.049 1.04 0 1 0 = 77.59

0 -1 0 0 0 1 = -1000

Вихідний файл:

(c) Leonchenko Anna .... PNK-41

File dlja zchityvannja <in4.txt>

Vivid vukon v file <out4.txt>

Rozmirnist zadachi 4x6:

max(20x1+0.50x2+0x3+0x4+0x5+0x6)

{1}  1x1+0.02x2+1.04x3+0x4+0x5+0x6=86.53

{2}  0x1-0.06x2-3.12x3+1x4+0x5+0x6=-59.60

{3}  0x1+0.05x2+1.04x3+0x4+1x5+0x6=77.59

{4}  0x1-1x2+0x3+0x4+0x5+1x6=-1000

Iteracija #   1

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  20    0.50       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     20     X1   86.53       1    0.02    1.04       0       0       0

      0     X4  -59.60       0   -0.06   -3.12       1       0       0

      0     X5   77.59       0    0.05    1.04       0       1       0

      0     X6   -1000       0      -1       0       0       0       1

------------------------------------------------------------------

R  1730.60       0   -0.10   20.80       0       0       0

-------------------------------------------------------------------

Iteracija #   2

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                  20    0.50       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6   

     20     X1   66.53       1       0    1.04       0       0    0.02

      0     X4    2.40       0       0   -3.12       1       0   -0.06

      0     X5   28.59       0       0    1.04       0       1    0.05

   0.50     X2    1000       0       1       0       0       0      -1

------------------------------------------------------------------

R  1830.60       0       0   20.80       0       0   -0.10

-------------------------------------------------------------------

Rishennja znajdeno!!! Param-pam-pam

Z= 1830.60

X = (66.53  1000  0  2.40  28.59  0  )

8.Дослідження розробленої програми для великих розмірностей

(c) Leonchenko Anna .... PNK-41

File dlja zchityvannja <dat2.txt>

Vivid vukon v file <vvv.txt>

Rozmirnist zadachi 5x11:

max(-17x1-20x2-22x3-25x4-28x5-30x6+0x7+0x8+0x9+0x10+0x11)

{1}  -33x1+0x2-43x3+0x4-60x5+0x6+1x7+0x8+0x9+0x10+0x11=-1050

{2}  0x1-28x2+0x3-40x4+0x5-50x6+0x7+1x8+0x9+0x10+0x11=-600

{3}  1x1+1x2+0x3+0x4+0x5+0x6+0x7+0x8+1x9+0x10+0x11=5

{4}  0x1+0x2+1x3+1x4+0x5+0x6+0x7+0x8+0x9+1x10+0x11=15

{5}  0x1+0x2+0x3+0x4+1x5+1x6+0x7+0x8+0x9+0x10+1x11=15

Iteracija #   1

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

      0     X7   -1050     -33       0     -43       0     -60       0       1       0       0       0       0

      0     X8    -600       0     -28       0     -40       0     -50       0       1       0       0       0

      0     X9       5       1       1       0       0       0       0       0       0       1       0       0

      0     X10      15       0       0       1       1       0       0       0       0       0       1       0

      0     X11      15       0       0       0       0       1       1       0       0       0       0       1

------------------------------------------------------------------

R        0      17      20      22      25      28      30       0       0       0       0       0

-------------------------------------------------------------------

Iteracija #   2

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

    -17     X1   31.82       1       0    1.30       0    1.82       0   -0.03       0       0       0       0

      0     X8    -600       0     -28       0     -40       0     -50       0       1       0       0       0

      0     X9  -26.82       0       1   -1.30       0   -1.82       0    0.03       0       1       0       0

      0     X10      15       0       0       1       1       0       0       0       0       0       1       0

      0     X11      15       0       0       0       0       1       1       0       0       0       0       1

------------------------------------------------------------------

R  -540.91       0      20   -0.15      25   -2.91      30    0.52       0       0       0       0

-------------------------------------------------------------------

Iteracija #   3

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

    -17     X1   31.82       1       0    1.30       0    1.82       0   -0.03       0       0       0       0

    -20     X2   21.43       0       1       0    1.43       0    1.79       0   -0.04       0       0       0

      0     X9  -48.25       0       0   -1.30   -1.43   -1.82   -1.79    0.03    0.04       1       0       0

      0     X10      15       0       0       1       1       0       0       0       0       0       1       0

      0     X11      15       0       0       0       0       1       1       0       0       0       0       1

------------------------------------------------------------------

R  -969.48       0       0   -0.15   -3.57   -2.91   -5.71    0.52    0.71       0       0       0

-------------------------------------------------------------------

Iteracija #   4

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

    -17     X1   31.82       1       0    1.30       0    1.82       0   -0.03       0       0       0       0

    -20     X2  -26.82       0       1   -1.30       0   -1.82       0    0.03       0       1       0       0

    -30     X6   27.02       0       0    0.73    0.80    1.02       1   -0.02   -0.02   -0.56       0       0

      0     X10      15       0       0       1       1       0       0       0       0       0       1       0

      0     X11  -12.02       0       0   -0.73   -0.80   -0.02       0    0.02    0.02    0.56       0       1

------------------------------------------------------------------

R  -815.09       0       0    4.02    1.00    2.91       0    0.42    0.60   -3.20       0       0

-------------------------------------------------------------------

Iteracija #   5

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

    -17     X1    5.00       1       1       0       0       0       0       0       0       1       0       0

    -22     X3   20.58       0   -0.77       1       0    1.40       0   -0.02       0   -0.77       0       0

    -30     X6   12.00       0    0.56       0    0.80       0       1       0   -0.02       0       0       0

      0     X10   -5.58       0    0.77       0       1   -1.40       0    0.02       0    0.77       1       0

      0     X11    3.00       0   -0.56       0   -0.80       1       0       0    0.02       0       0       1

------------------------------------------------------------------

R  -897.79       0    3.08       0    1.00   -2.70       0    0.51    0.60   -0.12       0       0

-------------------------------------------------------------------

Iteracija #   6

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

    -17     X1    5.00       1       1       0       0       0       0       0       0       1       0       0

    -22     X3      15       0       0       1       1       0       0       0       0       0       1       0

    -30     X6   12.00       0    0.56       0    0.80       0       1       0   -0.02       0       0       0

    -28     X5    4.00       0   -0.55       0   -0.72       1       0   -0.02       0   -0.55   -0.72       0

      0     X11   -1.00       0   -0.01       0   -0.08       0       0    0.02    0.02    0.55    0.72       1

------------------------------------------------------------------

R  -887.00       0    1.60       0   -0.93       0       0    0.47    0.60   -1.60   -1.93       0

-------------------------------------------------------------------

Iteracija #   7

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

    -17     X1  -95.00       1       0       0   -8.33       0       0    1.67    2.00   56.00   71.67   100.00

    -22     X3      15       0       0       1       1       0       0       0       0       0       1       0

    -30     X6  -44.00       0       0       0   -3.87       0       1    0.93    1.10   30.80   40.13   56.00

    -28     X5   59.00       0       0       0    3.87       1       0   -0.93   -1.10  -30.80  -40.13  -55.00

    -20     X2   100.00       0       1       0    8.33       0       0   -1.67   -2.00  -55.00  -71.67  -100.00

------------------------------------------------------------------

R -1047.00       0       0       0  -14.27       0       0    3.13    3.80   86.40  112.73  160.00

-------------------------------------------------------------------

Iteracija #   8

--------------------------------------------------------------------

--------------------------------------------------------------------

Cil. funk                 -17     -20     -22     -25     -28     -30       0       0       0       0       0

------------------------------------------------------------------

            Bx     A0       A1       A2       A3       A4       A5       A6       A7       A8       A9       A10       A11   

    -25     X4   11.40   -0.12       0       0       1       0       0   -0.20   -0.24   -6.72   -8.60  -12.00

    -22     X3    3.60    0.12       0       1       0       0       0    0.20    0.24    6.72    9.60   12.00

    -30     X6    0.08   -0.46       0       0       0       0       1    0.16    0.17    4.82    6.88    9.60

    -28     X5   14.92    0.46       0       0       0       1       0   -0.16   -0.17   -4.82   -6.88   -8.60

    -20     X2       5       1       1       0       0       0       0       0       0       1       0       0

------------------------------------------------------------------

R  -884.36   -1.71       0       0       0       0       0    0.28    0.38   -9.47   -9.96  -11.20

-------------------------------------------------------------------

Rishennja znajdeno!!! Param-pam-pam

Z= -884.36

X = (0  5  3.60  11.40  14.92  0.08  0  0  0  0  0  )

Найбільша розмірність, яка може бути вирішена даним програмним продуктом складає матрицю розміром 50*50.


Список використаної літератури

1. Бабич В. І.  Конспект лекцій з дисципліни «Математичні методи дослідження операцій»

2. Культин Н. Б.  Программирование в Turbo Pascal 7.0 – Спб.: БХВ – Санкт-Петербург, 1999 – 240 с.

 


Додаток

Лістинг програми

program simplex;

uses crt;

const

 nmax=50;

 mmax=50;

var

 sub, file_input, file_output, iter, zn_max: string;

 it, res,fl: boolean;

 ind, k, n, m, j0, i0, i, j,nom_it: integer;

 c: array [1..mmax] of real;

 a: array [1..nmax,0..mmax] of real;

 b: array [1..nmax] of byte;

 d: array [0..mmax] of real;

 znak: array [1..nmax] of char;

 key: char;

{ x: array [1..mmax] of real; }

function value(var s: string): string;

var

 v: string;

 i: integer;

begin

 v:='';

 repeat

   if s[1]=',' then v:=v+'.' else v:=v+s[1];

   delete(s,1,1);

 until (s[1]=' ') or (s='');

 value:=v;

end;

procedure prov(var s: string);

begin

 if s[1]=' ' then

   repeat

     delete(s,1,1);

   until s[1]<>' ';

 if s[length(s)]=' ' then

   repeat

     delete(s,length(s),1);

   until s[length(s)]<>' ';

end;

procedure error(sub: string);

begin

 write('Недопустимий символ ');

 for i:=1 to length(sub) do

   case sub[i] of

     'A'..'Z','a'..'z': write('Буква  ');

     '0'..'9',',','.':;

   else write('спеціальний символ ');

   end;

 writeln;

end;

function ReadData: boolean;

var

 s: string;

 code, i, j: integer;

begin

 readdata:=true;

 assign(input,file_input);

 reset(input);

 if ioresult<>0 then

 begin

   writeln('Файл'<+file_input+'>не найдено');

   halt;

 end;

 readln(s);

 prov(s);

 sub:=value(s);

 val(sub, n, code);

 if code<>0 then

 begin

   writeln('Помилка: рядок 1-й число 1-ше ');

   readdata:=false;

   error(sub);

 end;

 prov(s);

 sub:=value(s);

 val(sub, m, code);

 if code<>0 then

 begin

   writeln(' Помилка: рядок 1-й число 2-ге ');

   readdata:=false;

   error(sub);

 end;

 if (n>nmax) or (m>mmax) then begin

   writeln('Указана розмірність задачі не підходить обмеженням задачі');

   readdata:=false;

 end;

 readln(s);

 prov(s);

 for j:=1 to m do

 begin

   sub:=value(s);

   val(sub, c[j], code);

   if code<>0 then

   begin

     writeln(Помилка: рядок 2-й' , j, 'число);

     readdata:=false;

     error(sub);

   end;

   prov(s);

 end;

 zn_max:=value(s);

 for i:=1 to n do

 begin

   readln(s);

   prov(s);

   for j:=1 to m do

   begin

     sub:=value(s);

     val(sub,a[i,j],code);

     if code<>0 then

     begin

       writeln('Помилка: рядок',i+2,'-число ',j,');

       readdata:=false;

       error(sub);

     end;

     prov(s);

   end;

   znak[i]:=s[1];

   delete(s,1,1);

   if (znak[1]<>'>') and (znak[1]<>'<') and (znak[1]<>'=') then begin

     writeln('Ошибка: рядок  ',i+2,'- й: не вірно вказаний знак');

     readdata:=false;

   end;

   prov(s);

   sub:=value(s);

   val(sub,a[i,0], code);

   if code<>0 then

   begin

     writeln('Ошибка: рядок ',i+2,'- й',m+1,'оє:');

     readdata:=false;

     error(sub);

   end;

 end;

end;

procedure kanon;

var

 max: real;

begin

 max:=1;

 for i:=1 to m do

   if max<c[i] then max:=c[i];

 max:=10*max;

 if (length(zn_max)=3) and ((zn_max[2]='I') or (zn_max[2]='i')) and ((zn_max[3]='N') or (zn_max[3]='n')) then

   for i:=1 to m do

     c[i]:=-c[i];

 repeat

 for i:=1 to n do

   if a[i,0]<0 then

   begin

     for j:=0 to m do

       a[i,j]:=-a[i,j];

     res:=false;

     case znak[i] of

       '>': znak[i]:='<';

       '<': znak[i]:='>';

     end;

     break;

   end

   else if (a[i,0]=0) and (znak[i]='<') then

   begin

     for j:=1 to m do

       a[i,j]:=-a[i,j];

     znak[i]:='>';

     res:=false;

     break;

   end

   else

   begin

     case znak[i] of

       '>': begin

         inc(m);

         c[m]:=0;

         a[i,m]:=-1;

         for j:=1 to n do

           if i<>j then

             a[j,m]:=0;

       end;

       '<':begin

         inc(m);

         c[m]:=0;

         a[i,m]:=1;

         for j:=1 to n do

           if i<>j then

             a[j,m]:=0;

       end;

       '=':begin

         inc(m);

         c[m]:=0;

         a[i,m]:=1;

         for j:=1 to n do

           if i<>j then

             a[j,m]:=0;

       end;

     end;

     res:=true;

     znak[i]:='^';

   end;

 until (res=true);

end;

function druk(b: real; im: boolean): string;

var

 s, s1: string;

 cel, i, j: integer;

begin

 s:='';

 cel:=trunc(b);

 i:=1;

 if b<0 then

 begin

   inc(i);

   cel:=abs(cel);

 end;

 while cel div 10 >0 do

 begin

   cel:=cel div 10;

   inc(i);

 end;

 if frac(b)<>0 then

 begin

   i:=i+3;

   str(b:4:2,s);

 end

 else  str(trunc(b), s);

 if im then

 begin

   i:=8-i;

   s1:='';

   for j:=1 to i do

     s1:=s1+' ';

   s:=s1+s;

 end;

 druk:=s;

end;

procedure vivod;

var i,j:integer;

begin

writeln('Iteracija #',nom_it:4);

writeln('--------------------------------------------------------------------');

writeln('--------------------------------------------------------------------');

write('Cil. funk            ');

for i:=1 to m do

write(druk(c[i],true));

writeln('');

write('------------------------------------------------------------------');

writeln('');

 write('             Bx ');

 for j:=0 to m do

 write('    A',j,'   ');

 writeln('');

 for i:=1 to n do

 begin

 write(druk(c[b[i]],true));

 write('     X',b[i]);

 write(druk(a[i,0],true));

 for j:=1 to m do

  write(druk(a[i,j],true));

  writeln(' ');

 end;

 writeln('------------------------------------------------------------------');

 write('R ');

 for i:=0 to m do

 write(druk(d[i],true));

 writeln(' ');

 writeln('-------------------------------------------------------------------');

 writeln('');

 nom_it:=nom_it+1;

end;

procedure WriteUmovu;

var

 i, j: integer;

begin

 clrscr;

 writeln('(c) Leonchenko Anna .... PNK-41');

 writeln;

 writeln('File dlja zchityvannja <'+file_input+'>');

 if file_output='con' then

   writeln('Vivid vukon na ekran')

 else writeln('Vivid vukon v file <'+file_output+'>');

 Writeln('Rozmirnist zadachi ', n, 'x', m, ':');

 writeln;

 write('max(');

 for j:=1 to m do

   if (c[j+1]>=0) and (j<>m) then write(druk(c[j],false),'x', j,'+')

     else write(druk(c[j],false),'x',j);

 writeln(')');

 for i:=1 to n do

 begin

   write('{',i,'}  ');

   for j:=1 to m do

   begin

     write(druk(a[i,j],false),'x',j);

     if (a[i,j+1]>=0) and (j<>m) then write('+');

   end;

   writeln('=',druk(a[i,0],false));

 end;

 if file_output='con' then

   repeat

     key:=readkey

   until key=#13;

end;

procedure RozDelta; {rozraxynok delta}

var

 i, j, k: integer;

 pr: boolean;

begin

 for i:=1 to n do     {zapisyemo ne 0 elementu}

   for j:=1 to m do

     if a[i,j]=1 then

     begin

       pr:=false;

       for k:=1 to n do

         if (i<>k) then

           if (a[k,j]=0) then pr:=true

           else begin pr:=false; break; end;

       if pr then

       begin b[i]:=j; break; end;

     end;

 for j:=0 to m do {podchet delta}

 begin

   if j=0 then d[j]:=0 else d[j]:=-c[j];

   for i:=1 to n do

     d[j]:=d[j]+a[i,j]*c[b[i]];

 end;

end;

function napr_str(var i0: integer): boolean; {vuznachennja napr-j stroku}

var

 value1: real;

 i: integer;

begin

 napr_str:=false;

 value1:=0;

 i0:=0;

 for i:=1 to n do

   if (a[i,0]<value1) then

   begin

     value1:=a[i,0];

     i0:=i; {nomer napr-j stroku}

     napr_str:=true;

   end;

end;

function napr_st(i0: integer; var j0: integer): boolean; {viznachennja napr-go stovbchika}

var

 value1: real;

 j: integer;

begin

 napr_st:=false;

 value1:=0;

 j0:=0;

 for j:=1 to m do

   if (a[i0,j]<0) and (abs(d[j]/a[i0,j])>value1) then

   begin

     value1:=abs(d[j]/(a[i0,j]));

     j0:=j; {zapusyemo nomer stovbchika}

     napr_st:=true;

   end;

end;

procedure pererah; {pererahovyemo matrucy}

var

 i, j: integer;

begin

 for j:=0 to m do

 if j<>j0 then

 begin

   for i:=1 to n do

     if i<>i0 then

     a[i,j]:=a[i,j]-(a[i0,j]*a[i,j0]/a[i0,j0]);

   d[j]:=d[j]-(a[i0,j]*d[j0]/a[i0,j0]);

 end;

 for j:=0 to m do

   if j<>j0 then a[i0,j]:=a[i0,j]/a[i0,j0]; {rozrahynok napr. stoku}

 for i:=1 to n do

   if i<>i0 then a[i,j0]:=0; {rozrahynok napr. stovb.}

 d[j0]:=0;

 a[i0,j0]:=1;

 b[i0]:=j0; {zapis nomera stovb.}

end;

function simpl: boolean; {}

begin

 simpl:=true;

 while napr_str(i0) do

   if napr_st(i0,j0) then

    begin

     Pererah;

     vivod;

    end

   else

   begin

     simpl:=false;

     break;

   end;

end;

BEGIN

 {file_input:='in.txt';

 file_output:='out.txt';

 it:=true;  }

 file_input:=paramstr(1);

 file_output:=paramstr(2);

 iter:=paramstr(3);

 readkey;

 if (file_input='') or (file_output='') then

 begin

   writeln('Vvedit pravilno dani');

   writeln('DUOSIMPL.exe inputfile outputfile/con [Y/y]');

   exit;

 end;

 if (iter='Y') or (iter='y') then it:=true;

 if file_output<>'con' then

 begin

   assign(output,file_output);

   rewrite(output);

 end;

 res:=true;

 if not ReadData then halt;

 {Kanon; }

 writeln;

 WriteUmovu;

 writeln;

 RozDelta;

 nom_it:=1;

 vivod;

 if not simpl then {nema rishennja}

 begin

   writeln('Rishen nemaje');

   halt;

 end

 else

 begin

 writeln('Rishennja znajdeno!!! Param-pam-pam');

 writeln('Z=',druk(d[0],true));

 write('X = (');

 for i:=1 to m do

 begin

 fl:=false;

 for j:=1 to m do

 if b[j]=i then begin write(druk(a[j,0],false),'  '); fl:=true; end;

 if fl=false then write('0  ');

 end;

 writeln(')');

 end

END.


 

А также другие работы, которые могут Вас заинтересовать

85563. Автоматизация системы управления запасами на шахте “Самсоновская-Западная” 784.5 KB
  Применение современных персональных микроЭВМ в качестве технического средства АРМ управленческого работника приводит одновременно с организацией децентрализованной системы обработки данных к интеграции информационной базы данных учета.
85564. Экономические и правовые аспекты страхования ЗАО «Страховая компания «Инкомстрах» 394.5 KB
  Страховая компания Инкомстрах есть страхование и перестрахование имущественных интересов физических и или юридических лиц резидентов и или нерезидентов Украины которые не противоречат действующему законодательству Украины связанных: со здоровьем трудоспособностью и дополнительной пенсией...
85565. РЕАЛИЗАЦИЯ ИНФОРМАЦИОННОЙ МОДЕЛИ БАЗЫ ДАННЫХ В СИСТЕМЕ СОЦИАЛЬНОЙ ЗАЩИТЫ ГОСУДАРСТВА 472 KB
  Финансовый контроль по своей экономической сути это функция управления которая включает совокупность наблюдений проверок по деятельности объекта управления с целью оценки обоснованности и эффективности принятия решений и результатов их выполнение.
85566. Создание программного обеспечения для автоматизации ассортимента продукции на МЧП «Инвикта» 1.5 MB
  Ассортимент является важным элементом деятельности предприятия. Создание информационной системы для определения оптимального ассортимента товаров позволит постоянно отслеживать ситуацию на рынке, оценить факторы, обеспечивающие успех фирмы, сделать максимально эффективными продажи товара.
85567. МЕТОДЫ ПЛАНИРОВАНИЯ ХОЗЯЙСТВЕННОЙ ДЕЯТЕЛЬНОСТИ ОАО «ТРЕСТ КРАСНОДОНШАХТОСТРОЙ» 698 KB
  Первый состоит в минимизации затрат при достижении заданного результата; второй заключается в максимизации результатов при заданных затратах ресурсах. Расчетноаналитические нормы разрабатываются на основе анализа техники технологии и организации производства в заданных или запроектированных условиях. Опытноэкспериментальные нормы устанавливаются на основе опытных или экспериментальных данных полученных в реально существующих условиях производства. Интегрированная автоматизированная система Современные персональные компьютеры...
85568. СОВЕРШЕНСТВОВАНИЕ СИСТЕМЫ УПРАВЛЕНИЯ КАДРОВЫМ СОСТАВОМ НА ПРЕДПРИЯТИИ С УЧЕТОМ ЭКОНОМИЧЕСКИХ ФАКТОРОВ 821.5 KB
  В работе рассмотрены основные функции и задачи организации и основные функции службы кадров, исследована информационная среда организации, проведен анализ существующей модели прогнозирования, дана характеристика сетевого управления предприятием с описанием его аппаратного и программного обеспечения.
85569. РАЗРАБОТКА СИСТЕМЫ МОДЕЛИРОВАНИЯ ЭВОЛЮЦИИ ПОПУЛЯЦИЙ 687 KB
  Разработаны различные модели управления системой формализована процедура анализа параметров системы и приведены математические методы ее решения; разработана компьютерная реализация информационно-вычислительной системы для исследования экосистем.
85570. Компьютеризация экономического мониторинга реализации инвестиционных проектов в регионе 1.08 MB
  В данной бакалаврской работе разработана система, автоматизирующая поступление отчетов от хозяйствующих субъектов на территориях приоритетного развития и, заносящая их в базу данных. Система ориентирована на работу с непрограммирующими пользователями и не предусматривает процедуры дополнительного...
85571. Система оценки банковской ликвидности как важнейшего показателя надежности банка 512.5 KB
  Данная работа посвящена проблеме оценки банковской ликвидности как важнейшего показателя надежности банка. В ней рассмотрена система нормативных показателей ликвидности НБУ прогнозирование прибыли банка с помощью многофакторного прогнозирования социально-экономических явлений на основании регрессионного...