Находження оптимального рішення прямої і двоїстої задач.

озділ 4. Побудова математичної моделі. Рішення завдання.

обудова математичної моделі.

Математична модель прямої і двоїстої задачі будуть має наступний вигляд:

Найменування показників Норма витрати ресурсів на одиницю продукції Наявність ресурсів
A B C D
Ресурс R1
Ресурс R2
Ресурс R3
Прибуток від реалізації одиниці продукції  

ряма задача

Z = 3x1+8x2+9x3+5x4 находження оптимального рішення прямої і двоїстої задач. - student2.ru

4x1+2x2+x3+4x4≤506

2x1+…+2x3+3x4≤206

2x1+3x2+x3 +….≤546

2) Двоїста задача

находження оптимального рішення прямої і двоїстої задач. - student2.ru

4y1+2y2+2y3 находження оптимального рішення прямої і двоїстої задач. - student2.ru 3

2y1+… + 3y3 находження оптимального рішення прямої і двоїстої задач. - student2.ru 8

y1+2y2+y3 находження оптимального рішення прямої і двоїстої задач. - student2.ru 9

4y1+3y2+… находження оптимального рішення прямої і двоїстої задач. - student2.ru 5


находження оптимального рішення прямої і двоїстої задач.

Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці.

Визначимо максимальне значення цільової функції F (X) = 3x1+8x2+9x3+5x4 за таких умов-обмежень.

4x1+2x2+x3+4x4≤506

2x1+2x3+3x4≤206

2x1+3x2+x3≤546

Для побудови першого опорного плану систему нерівностей наведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми).

В 1-ій нерівності (≤) вводимо базисну змінну x5. В 2-ій нерівності (≤) вводимо базисну змінну x6. В 3-ій нерівності (≤) вводимо базисну змінну x7.

4x1 + 2x2 + x3 + 4x4 + x5 = 506

2x1 + 2x3 + 3x4 + x6 = 206

2x1 + 3x2 + x3 + x7 = 546

Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:

Вирішимо систему рівнянь відносно базисних змінних:

x5, x6, x7,

Вважаючи, що вільні змінні рівні 0, отримаємо перші опорний план:

X1 = (0,0,0,0,506,206,546)

Сб ОП x1 x2 x3 x4 x5 x6 x7
x5
x6
x7
z-c -10 -5 -4 -8

Переходимо до основного алгоритму симплекс-методу.

Ітерація №0.

Поточний опорний план не є оптимальним, тому що в індексному рядку знаходяться негативні коефіцієнти.

В якості ведучого виберемо стовбець, відповідний зміної x1, тому що це найбільший коефіцієнт за модулем.

Обчислимо значення Di по рядках як частка від ділення: bi / ai1

і з них виберемо найменше:

min(506/2, 206/2, 546/2) = 103

Отже, 2-й рядок є рішуючим.

Сб ОП x1 x2 x3 x4 x5 x6 x7 Q
x5
x6
x7
z-c -10 -5 -4 -8

Після перетворень одержуємо нову таблицю:

Сб ОП x1 x2 x3 x4 x5 x6 x7
x5 -3 -2 -2
x1 1.5 0.5
x7 -1 -3 -1
z-c -8 -6 -0.5 1.5

Ітерація №1.

Поточний опорний план не є оптимальним, тому що в індексному рядку є негативні коефіцієнти.

В якості ведучого виберемо стовпець, відповідний змінної x2, тому що це найбільший коефіцієнт за модулем.

Обчислимо значення Di по рядках як частка від ділення: bi / ai2

і з них виберемо найменше. Отже, 1-ий рядок є провідним.

Сб ОП x1 x2 x3 x4 x5 x6 x7 Q
x5 -3 -2 -2
x1 1.5 0.5 -
x7 -1 -3 -1
z-c -8 -6 -0.5 1.5

Після перетворень одержуємо нову таблицю:

Сб ОП x1 x2 x3 x4 x5 x6 x7
x2 -1.5 -1 0.5 -1
x1 1.5 0.5
x7 3.5 -1.5
z-c -18 -3,5 -8

Ітерація №2.

Поточний опорний план не є оптимальним, тому що в індексному рядку є негативні коефіцієнти.

В якості ведучого виберемо стовпець, відповідний змінної x3, тому що це найбільший коефіцієнт за модулем.

Обчислимо значення Di по рядках як частка від ділення: bi / ai3

і з них виберемо найменше. Отже, 3-й рядок є ведучим.

Сб ОП x1 x2 x3 x4 x5 x6 x7 Q
x2 -1.5 -1 0.5 -1 -
x1 1.5 0.5 51.5
x7 3.5 -1.5 99.5
z-c -18 -8,5 -8  

Після перетворень одержуємо нову таблицю:

Сб ОП x1 x2 x3 x4 x5 x6 x7
x2 52.5 -0.14 -0.14 0.43
x1 3.5 1.5 0.43 -0.0714 -0.29
x3 99.5 -0.43 0.57 0.29
F(X3) 7.5 1.12 0.86 5.18

Кінець ітерацій: індексний рядок не містить негативних елементів - знайдений оптимальний план.

Оптимальний план можна записати так:

X*=(3.5, 52.5, 99.5, 0)

F(X) = 3*3.5 + 8*52.5 + 9*99.5 = 1326

З останньої симплексної таблиці нескладно знайти оптимальний план і двоїстої задачі. Він матиме вигляд:

находження оптимального рішення прямої і двоїстої задач. - student2.ru

При цьому F min = 506*y1+206*y2+546*y3=1326

Легко побачити що Z max = F min = 1326

Економічний аналіз оптимальних планів прямої і двоїстої задач наступний.

Оптимальний план прямої задачі передбачає виробництво лише трьох видів продукції A, B, C у кількості виробництва A=3.5 (ум.од), B=52.5 (ум.од), C=99.5 (ум.од). Випуск продукції D(x4=0) не передбачається.

За такого оптимально плану виробництво продукції та використання ресурсів підприємство отримає найбільший дохід у розмірі 1326 умовних одиниць.

План двоїстої задачі дає оптимальну систему оцінок ресурсів, що використовуються у виробництві. Так з того, що находження оптимального рішення прямої і двоїстої задач. - student2.ru (значення більші нуля), випливає, що ресурси 1-го, 2-го і 3-го видів ресурсу використовуються повністю. Ці висновки аналогічні отриманим на основі попереднього аналізу додаткових змінних оптимального плану прямої задачі.

Статус ресурсів прямої задачі можна визначити так:

Перший спосіб – підстановкою. Якщо обмеження виконується як рівняння, то відповідний ресурс дефіцитний, інакше – недефіцитний

Для розглядуваного прикладу матимемо:

4*3.5 +2*52.5 +1*99.5 +4*0=218.5 (ресурс A дефіцитний)

2*3.5 + 2*99.5 + 3*0=206 (ресурс B дефіцитний)

2*3.5 + 3*52.5 +1*99.5 +0*0=264 (ресурс C дефіцитний)

Другий спосіб – за допомогою двоїстих оцінок. Якщо у не дорівнює 0, то ресурс дефіцитний, якщо ж у=0, то ресурс недефіцитний.

находження оптимального рішення прямої і двоїстої задач. - student2.ru
находження оптимального рішення прямої і двоїстої задач. - student2.ru

Визначаємо далі інтервали стійкості двоїстих оцінок відносно зміни запасів дефіцитних ресурсів.

Якщо запас першого дефіцитного ресурсу збільшити на одну умовну одиницю (b1=506+1=507), то цільова функція Z max збільшиться на находження оптимального рішення прямої і двоїстої задач. - student2.ru ум.од. і становитиме Z max=1327.57.

Отже збільшення запасу першого дефіцитного ресурсу за інших умов приводить до падіння виробництва продукції х1 з 3.5 ум.од. до 3.37 ум. од., продукції х1 зросте від 52.5 ум.од до 52.8, а продукції С від 99.5 ум.од до 100.1 ум.од.

Якщо запас другого дефіцитного ресурсу збільшити на одну умовну одиницю (b2=206+1=207), то цільова функція Z max збільшиться на находження оптимального рішення прямої і двоїстої задач. - student2.ru ум.од. і становитиме Z max=1327.57.

Отже збільшення запасу другого дефіцитного ресурсу за інших умов приводить до падіння виробництва продукції х2 з 52.5 ум.од. до 53.57 ум. од., продукції х1 впаде від 3.5 ум.од до 2.43, а продукції С зросте від 99.5 ум.од до 100.7 ум.од.

Якщо запас третього дефіцитного ресурсу збільшити на одну умовну одиницю (b3=546+1=547), то цільова функція Z max збільшиться на находження оптимального рішення прямої і двоїстої задач. - student2.ru ум.од. і становитиме Z max= 1327.29.

Отже збільшення запасу третього дефіцитного ресурсу за інших умов приводить до зростання виробництва продукції х3 з 99.5 ум.од. до 99.79 ум. од., продукції х1 впаде від 3.5 ум.од до 3.21, а продукції С зросте від 99.5 ум.од до 99.79 ум.од.

Після проведення аналізу постає логічне запитання, чи збережуться встановлені пропорції, якщо запас дефіцитного ресурсу змінити не на одиницю, а на 10 умовних одиниць. Щоб відповісти необхідно розрахувати інтервали можливої зміни обсягів дефіцитних ресурсів, у межах яких двоїсті оцінки (у) залишаються на рівні оптимальних значень

Приріст (зміну) запасу ресурсу 1 позначимо через ∆b1. Тоді якщо находження оптимального рішення прямої і двоїстої задач. - student2.ru то новий оптимальний план буде таким

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Єдина вимога, що можна поставити, до можливих нових оптимальних значень - це умова невід’ємності тобто:

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Це означає, що коли запас ресурсу 1 збільшиться на 350 умовних одиниць або зменшиться на 8,14 умовні одиниці, то оптимальною двоїстою оцінкою ресурсу 1 залишиться находження оптимального рішення прямої і двоїстої задач. - student2.ru . Отже, запас ресурсу 1 може змінюватись у межах:

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

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

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Аналогічно розраховуємо інтервал стійкості двоїстої оцінки для у2 та у3

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Отже, якщо запас ресурсу 2 може збільшиться на 350 ум.од або зменшиться на 174.56 ум.од, то оптимальною двоїстою оцінкою ресурсу 2 залишиться 1,57.

Отже запас ресурсу 2 може змінюватись у межах:

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

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

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Приріст (зміну) запасу ресурсу 3 позначимо через ∆b3. Тоді якщо находження оптимального рішення прямої і двоїстої задач. - student2.ru то новий оптимальний план буде таким

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Єдина вимога, що можна поставити, до можливих нових оптимальних значень - це умова невід’ємності тобто:

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Це означає, що коли запис ресурсу 3 збільшиться на 12.06 умовні одиниці або зменшиться на 343.1 умовні одиниці, то оптимальною двоїстою оцінкою ресурсу 3 залишиться 1,29. Отже, запас ресурсу 3 може змінюватись у межах:

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

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

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Визначені інтервали мають місце лише в тих випадках, коли змінюється тільки один ресурс, а запаси всіх інших фіксовані, тобто за інших однакових умов. У разі одночасної зміни обсягів усіх або кількох ресурсів підхід до визначення нового оптимального плану буде інший.

находження оптимального рішення прямої і двоїстої задач. - student2.ru находження оптимального рішення прямої і двоїстої задач. - student2.ru Змінимо обсяги всіх 3х ресурсів наступним чином:

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Матрицю можна отримати з останньої симплекс-таблиці. Вона має наступний вигляд:

Сб ОП x1 x2 x3 x4 x5 x6 x7
x2 62.1 -0.14 -0.14 0.43
x1 4.7 1.5 0.43 -0.0714 -0.29
x3 93.2 -0.43 0.57 0.29
F(X4) 7.5 1.07 0.24 4.77

Новий оптимальній план буде таким:

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Усі находження оптимального рішення прямої і двоїстої задач. - student2.ru і тому оптимальний план двоїстої задачі залишиться колишнім

Загальний максимальний дохід підприємства зміниться на 22.7 і становитиме 1349.7.

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

Підставимо находження оптимального рішення прямої і двоїстої задач. - student2.ru у систему обмежень двоїстої задачі. Якщо вартість ресурсів на одиницю продукції(ліва частина) перевищує ціну цієї продукції(праву частину), то виробництво такої продукції для підприємства недоцільне. Якщо ж співвідношення виконується як рівняння, то продукція рентабельна.

4*1,57+2*1,57+2*1,29=12 (продукція А рентабельна)

2*1,57+3*1,29=7 (продукція В рентабельна)

1*1,57+2*1,57+1*1,29=6 (продукція С рентабельна)

4*1,57+3*1,57=11>10 (продукція D нерентабельна)

Аналогічні результати можна дістати, проаналізувавши двоїсті оцінки додаткових змінних, значення яких показують, на скільки вартість ресурсів перевищує ціну одиниці відповідної продукції. Тому, якщо додаткова змінна двоїстої задачі дорівнює нулю, то продукція рентабельна.

Додаткові змінні двоїстої задачі розміщуються в оцінковому рядку останньої симплекс таблиці у стовпчиках. Їх оптимальні значення

у1=1,57 у2=1,57 у3=1,29 у4=0

Тому продукції А, В, С рентабельні, а продукція D нерентабельна.

Під впливом різних обставин ціна одиниці продукції на підприємстві може змінюватись(збільшуватись чи зменшуватись). І тому завжди важливо знати, у межах яких замін ціни продукції кожного виду оптимальний план її виробництва залишається незмінним, тобто для розглядуваного прикладу рівним

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Для визначення інтервалів зміни коефіцієнтів цільової функції скористаємось тим, що при цьому симплекс-таблиця, яка відповідає оптимальному плану, зберігає свій вигляд за винятком елементів оцінкового ряду. Нові оцінки находження оптимального рішення прямої і двоїстої задач. - student2.ru мають задовольняти умову оптимальності задачі максимізації, тобто бути невід’ємними.

Зміну коефіцієнта находження оптимального рішення прямої і двоїстої задач. - student2.ru позначимо через находження оптимального рішення прямої і двоїстої задач. - student2.ru . Оскільки х4 є небазисною змінною, то в симплекс-таблиці зміниться лише відповідна оцінка

находження оптимального рішення прямої і двоїстої задач. - student2.ru

За умови находження оптимального рішення прямої і двоїстої задач. - student2.ru дістанемо нерівність находження оптимального рішення прямої і двоїстої задач. - student2.ru тобто находження оптимального рішення прямої і двоїстої задач. - student2.ru

Це означає, що коли ціна одиниці продукції D за інших однакових умов зросте не більш ніж на 7.5 ум.од., то оптимальним планом виробництва продукції на підприємстві все одно залишиться находження оптимального рішення прямої і двоїстої задач. - student2.ru . Лише максимальний дохід зміниться на находження оптимального рішення прямої і двоїстої задач. - student2.ru

Складніше розраховуються інтервал зміни коефіцієнтів для базисного стовпчика. У цьому разі зміни відбуваються також у стовпчику находження оптимального рішення прямої і двоїстої задач. - student2.ru симплекс-таблиці, а це у свою чергу стосується всіх ненульових оцінок ( находження оптимального рішення прямої і двоїстої задач. - student2.ru ).

Так для базисної змінної находження оптимального рішення прямої і двоїстої задач. - student2.ru зміна коефіцієнта на находження оптимального рішення прямої і двоїстої задач. - student2.ru приведе до таких оцінок:

Сб ОП x1 x2 x3 x4 x5 x6 x7
x2 62.1 -0.14 -0.14 0.43
x1 4.7 1.5 0.43 -0.0714 -0.29
x3 93.2 -0.43 0.57 0.29
F(X4) 7.5 1.07 0.24 4.77

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Нові значення оцінок мають задовольняти умову оптимальності, тобто находження оптимального рішення прямої і двоїстої задач. - student2.ru . Тому інтервал для находження оптимального рішення прямої і двоїстої задач. - student2.ru визначається з такої системи нерівностей:

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Отже ціна одиниці продукції С може змінюватись в межах

находження оптимального рішення прямої і двоїстої задач. - student2.ru , тобто находження оптимального рішення прямої і двоїстої задач. - student2.ru

Звідси находження оптимального рішення прямої і двоїстої задач. - student2.ru

Таким чином, ціна одиниці продукції продукції С1 може збільшуватись на 54.28 та зменшуватись на 86 ум.од., і перебувати в межах від -83 до 57.28 ум.од.

Аналогічно для базисної змінної находження оптимального рішення прямої і двоїстої задач. - student2.ru зміна коефіцієнта на находження оптимального рішення прямої і двоїстої задач. - student2.ru приведе до таких оцінок:

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Нові значення оцінок мають задовольняти умову оптимальності, тобто находження оптимального рішення прямої і двоїстої задач. - student2.ru . Тому інтервал для находження оптимального рішення прямої і двоїстої задач. - student2.ru визначається з такої системи нерівностей:

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Отже ціна одиниці продукції С може змінюватись в межах

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Звідси находження оптимального рішення прямої і двоїстої задач. - student2.ru

Таким чином, ціна одиниці продукції продукції С2 може збільшуватись на 11.4 та зменшуватись на 2,9 ум.од., і перебувати в межах від 6.1 до 19.4 ум.од.

Аналогічно для базисної змінної находження оптимального рішення прямої і двоїстої задач. - student2.ru зміна коефіцієнта на находження оптимального рішення прямої і двоїстої задач. - student2.ru приведе до таких оцінок:

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Нові значення оцінок мають задовольняти умову оптимальності, тобто находження оптимального рішення прямої і двоїстої задач. - student2.ru . Тому інтервал для находження оптимального рішення прямої і двоїстої задач. - student2.ru визначається з такої системи нерівностей:

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Отже ціна одиниці продукції С може змінюватись в межах

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Звідси находження оптимального рішення прямої і двоїстої задач. - student2.ru

Таким чином, ціна одиниці продукції продукції С3 може збільшуватись на 3.7 та зменшуватись на 2.8 ум.од., і перебувати в межах від 7.8 до 12.7 ум.од.

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

Проведений в даному прикладі аналіз лінійної моделі на чутливість дає широкий спектр динамічної інформації про визначений оптимальний план і змогу дослідити можливі зміни цього оптимального плану в результаті коректування умов прямої задачі.

Висновок

В даній роботі ми розглянули одну з задач лінійного програмування та методи її вирішення. Один з методів покладений в основу роботи даної програми – симплекс-метод. Виконуючи курсову я вдосконалив свої знання та навички використання мови програмування Java. Робота вимагала знань основ алгоритмічної мови, вміння складати програми різної складності використовуючи дану мову програмування. Я вдосконалив свої знання у області роботи з класами, методами, функціями. Набув суттєвих практичних навиків у роботі з компілюванням файлів Java. Також я вдосконалив знання з дослідження операцій та конкретно з рішення задач лінійного програмування та симплекс-метода, аналіза оптимального рішення на чутливість.

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

1 Орлова И.В. Экономико-математическое моделирование. Практическое пособие по решению задач. – М.: ВЗФЭИ, 2004.

2 Математические методы принятия решений в экономике: Учебник/ Под ред. В.А. Каламаева – М.: ЗАО «Финстатинформ», 1999.

3 Гатауллин Т.М. Введение в исследование операций. – М.: Академический центр «Единые транспортные системы», 1999.

4 Таха Х. Исследование операций. 7-е изд. . – М: Вильямс, 2007.

5 Зайченко Ю.П. Дослідження операцій. Підручник для ВНЗ (рек. МОН України). – 7-е вид. . – К: Слово, 2006.

6 Карманов В.Г. Математическое программирование: Учеб. пособие. – 5-е изд., Стереотип. – М: Физматлит., 2004.

7 Исследование операций в экономике: Учебное пособие для вузов. / Кремер Н.Ш., Путко Б.А., Гришин Н.М., Фридман М.Н. Под ред. проф. Н.Ш. Кремера. – М: ЮНИТИ, 2002.

одаток 1

Інструкція користувачеві

Після запуску програми на виконання програма пропонує ввести такі данні: а) кількість рівнянь та кількість обмежень; б) після цього з’являється вікно в якому потрібно ввести коефіцієнти функції та коефіцієнти рівнянь системи; в) потім потрібно вибрати куди прямує функція (МАХ або MIN); г) вибрати знаки рівності або нерівності (=, ≥, ≤)

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

Для коректної роботи з програмою потрібно мати певну базу знань англійської мови, адже всі посилання, назви, та написи на клавішах написано виключно на англійські мові. Щодо користування даною програмою: треба ввести в діалоговому вікні коефіцієнти функції та систем рівнянь, віибрати МАХ або MIN (відповідно до задачі, яка перед вами ставиться) та натиснути клавішу розрахування (рис. 2). Далі є два варіанти подальшої роботи з програмою – перший – це одразу отримати кінцевий результат, а інший – натискати клавішу виконання завдання декілька раз. Другий спосіб дає можливість поступово (крок за кроком) спостерігати за роботою програми та вирішенні задачі.

находження оптимального рішення прямої і двоїстої задач. - student2.ru

Рисунок 2- Інтерфейс користувача

одаток 2

Текст програми

package simplex;

import javax.swing.*;

public class Simplex {

static boolean solved = false;

static boolean lim = false;

static int tempCInd = 0;

static int minRInd = 0;

static int minCInd = 1;

static float[] solution;

//решение задачи в автоматическом режиме

static float[][] Solve(float[][] matrix){

solved = true;

// Check for optimum

for (int i = 0; i <= ReadFile.colCount; i++){

if (matrix[i][0] < 0)

solved = false;

//While answer is not optimum

while (!solved){

// находим ведущий столбец

float minR = matrix[0][0];

int minRInd = 0;

for (int i = 0; i <= ReadFile.colCount; i++){

if (matrix[i][0] < minR){

minR = matrix[i][0];

minRInd = i;

}

}

//check AF

lim = false;

for (int i = 0; i <= ReadFile.rowCount; i++){

if (matrix[minRInd][i] > 0)

lim = true;

}

//If error…

//решение

if (!lim){

solved = true;

JOptionPane.showMessageDialog(null, "функция не ограничена на множестве допустимых решений");

break M1;

}

//Finding direction string

float minC = matrix[ReadFile.colCount][1]/matrix[minRInd][1];

int minCInd = 1;

for (int i = 1; i < tempCInd; i++){

if (matrix[ReadFile.colCount][i]/matrix[minRInd][i] < minC){

minC = matrix[ReadFile.colCount][i]/matrix[minRInd][i];

minCInd = i;

}

}

for (int i = tempCInd + 1; i <= ReadFile.rowCount; i++){

if (matrix[ReadFile.colCount][i]/matrix[minRInd][i] < minC){

minC = matrix[ReadFile.colCount][i]/matrix[minRInd][i];

minCInd = i;

}

}

//Get from basis [0][minCInd], push into basis [minRInd][0]

ReadFile.varCol[minCInd-1] = ReadFile.varRow[minRInd] ;

//new simplex table

//separate DS on D element

float temp = matrix[minRInd][minCInd];

System.out.print(">> " + temp + "\n");

System.out.print("\n Ведуча строка: ");

for (int i = 0; i <= ReadFile.colCount; i++){

matrix[i][minCInd] /= temp;

}

//получаем нули в ведущем столбце

for (int j = 0; j < minCInd; j++){

float minTemp = matrix[minRInd][j];

for (int i = 0; i <= ReadFile.colCount; i++){

matrix[i][j] += matrix[i][minCInd] * -minTemp;

}

}

for (int j = minCInd+1; j <=ReadFile.rowCount; j++){

float minTemp = matrix[minRInd][j];

for (int i = 0; i <= ReadFile.colCount; i++){

matrix[i][j] += matrix[i][minCInd] * -minTemp;

}

}

//upgrade answer vector

for (int i = 0; i < ReadFile.bvarCount; i++){

for (int j = 0 ; j < ReadFile.varCount; j++){

int k = j + 1;

String tempS = "x" + k;

if (tempS.equals(ReadFile.varCol[i]))

solution[j] = matrix[ReadFile.colCount][i+1];

}

}

tempCInd = minCInd;

//recursion until not optimum answer

Solve(matrix);

}

}

return matrix;

}

//create answer vector

static void initSolution(int varCount){

solution = new float[varCount];

for (int i = 0; i < varCount; i++){

solution[i] = 0;

}

}

//select D column

static boolean userChooseCol(float[][] matrix, JTable tableName){

boolean err = false;

M1: {

//find DC

float minR = matrix[0][0];

minRInd = 0;

for (int i = 0; i <= ReadFile.colCount; i++){

if (matrix[i][0] < minR){

minR = matrix[i][0];

minRInd = i;

}

}

//check choise of user

while (minRInd != SimplexView.getSelectedCol() - 1){

JOptionPane.showMessageDialog(null, "ведущий столбец выбран

неверно");

err = true;

break M1;

}

int temp = minRInd;

float[] proportion = new float[ReadFile.rowCount];

//calculate help column

for (int i = 1; i <= ReadFile.rowCount; i++){

if ( i == tempCInd ){

proportion[i-1] = java.lang.Float.NaN;

}

else{

proportion[i-1] = matrix[ReadFile.colCount][i] /

matrix[temp][i];

}

}

TableView.fillProportion(tableName, proportion, tempCInd);

}

return err;

}

//select DS

static boolean userChooseRow(float[][] matrix, JTable tableName){

lim = false;

boolean err = false;

M1:{

//check AF

for (int i = 0; i <= ReadFile.rowCount; i++){

if (matrix[minRInd][i] > 0)

lim = true;

}

if (!lim){

JOptionPane.showMessageDialog(null, "функция не ограничена на

множестве допустимых решений");

break M1;

}

//find DS

float minC = matrix[ReadFile.colCount][1]/matrix[minRInd][1];

minCInd = 1;

for (int i = 1; i < tempCInd; i++){

if (matrix[ReadFile.colCount][i]/matrix[minRInd][i] < minC){

minC = matrix[ReadFile.colCount][i]/matrix[minRInd][i];

minCInd = i;

}

}

for (int i = tempCInd + 1; i <= ReadFile.rowCount; i++){

if (matrix[ReadFile.colCount][i]/matrix[minRInd][i] < minC){

minC = matrix[ReadFile.colCount][i]/matrix[minRInd][i];

minCInd = i;

}

}

//check user

System.out.print("user: " + SimplexView.getSelectedRow() + "; min: "

+minCInd);

while (minCInd != SimplexView.getSelectedRow()){

err = true;

JOptionPane.showMessageDialog(null, "ведущая строка выбрана

неверно");

break M1;

}

}

return err;

}

//rebuild simplex table

static void userBuildNewTable(float[][] matrix, JTable tableName){

ReadFile.varCol[minCInd-1] = ReadFile.varRow[minRInd] ;

float temp = matrix[minRInd][minCInd];

for (int i = 0; i <= ReadFile.colCount; i++){

matrix[i][minCInd] /= temp;

}

//nulls in DC

for (int j = 0; j < minCInd; j++){

float minTemp = matrix[minRInd][j];

for (int i = 0; i <= ReadFile.colCount; i++){

matrix[i][j] += matrix[i][minCInd] * -minTemp;

}

}

for (int j = minCInd+1; j <=ReadFile.rowCount; j++){

float minTemp = matrix[minRInd][j];

for (int i = 0; i <= ReadFile.colCount; i++){

matrix[i][j] += matrix[i][minCInd] * -minTemp;

}

}

for (int i = 0; i < ReadFile.bvarCount; i++){

for (int j = 0 ; j < ReadFile.varCount; j++){

int k = j + 1;

String tempS = "x" + k;

if (tempS.equals(ReadFile.varCol[i]))

solution[j] = matrix[ReadFile.colCount][i+1];

}

}

tempCInd = minCInd;

}

//check for optimum

static boolean checkSolved(float matrix[][]){

solved = true;

for (int i = 0; i <= ReadFile.colCount; i++){

if (matrix[i][0] < 0)

solved = false;

}

if (solved){

JOptionPane.showMessageDialog(null, " задача решена ");

tempCInd = 0;

}

return solved;

}

}

Наши рекомендации