Аналіз методів рішення задачі лінійного програмування симплекс методом
Міністерство освіти та науки України
Вінницький національний технічний університет
Інститут автоматики, електроніки та комп’ютерних систем управління
Факультет АКСУ
Кафедра АІВТ
Курсова робота
з дисципліни
«Алгоритмічні мови та програмування»
Аналіз методів рішення задачі лінійного програмування
симплекс-методом
Технічне завдання
Розробити
програму, що дозволяє знайти рішення
системи рівнянь:
при умовах
,
що забезпечує найменше значення функції
Мова програмування – Java.
Зміст
Анотація
Вступ
1. Загальні теоретичні відомості
1.1 Мова програмування Java
1.1.1 Лексична структура
1.1.2 Типи даних
1.1.3 Короткий огляд задачі, що розв’язується
2. Функціональне призначення
3. Аналіз методів розв’язання даної задачі
3.1 Метод потенціалів
3.2 Симплекс метод
3.3 Двоїстий симплекс метод
4. Опис логічної структури програми
5. Технічні засоби
6. Виклик та завантаження
7. Вхідні та вихідні данні
8. Інструкція для користувача
Висновки
Література
Анотація
Дана курсова робота написана на мові програмування Java. В курсовій роботі розглядається „задача лінійного програмування” та методи її розв’язання.
Поставлена задача розв’язана за допомогою симплекс методу.
Завдання курсової включає в себе побудову зручного інтерфейсу.
Вступ
У грудні 1951 року державна комісія на чолі з академіком Мстиславом Келдишем прийняла в експлуатацію першу в Радянському Союзі та континентальній Європі електронно-обчислювальну машину, розроблену під керівництвом академіка Сергія Лебедєва у Києві в лабораторії обчислювальної техніки Інституту електротехніки Академії наук України. З того часу минуло понад п’ятдесят років, і тепер ми вже точено знаємо, що це була епохальна подія. Вона ознаменувала собою початок нового етапу в розвитку науково-технічного прогресу суспільства.
Машину назвали МЭСМ (малая электронно-счетная машина), і першими на ній розв’язували свої задачі всесвітньо відомі математики та механіки – академіки Келдиш, Дородніцин, Зельдович, Савін та багато інших молодих спеціалістів, які згодом стали відомими вченими.
Не варто порівнювати МЭСМ із сучасними комп’ютерами ні за пам’яттю, ні за здатністю працювати в різноманітних технічних комплексах. Головне значення тієї першої машини полягає в тому, що при її розробці були закладені основоположні структурно-алгоритмічні принципи організації обчислень, присутні у всіх поколіннях обчислювальних машин.
В середині дев’яностих років на базі Інституту кібернетики ім. В. Глушкова був створений Кібернетичний центр, до складу якого ввійшли також Інститут прикладного системного аналізу, Міжнародний науково-навчальний центр інформаційних технологій та систем. Сьогодні в даному Кібцентрі працює близько 2500 співробітників, серед них – 135 докторів близько 500 кандидатів наук. За своїм потенціалом ця наукова організація є однією з найпотужніших у галузі інформатики в світі. Інститути Кібцентру роблять вагомий внесок в розробку нових інтелектуальних інформаційних технологій (ІТ).
У сучасному суспільстві інформація є важливим і цінним ресурсом, а рівень розвитку країни оцінюється рівнем її інформатизації. Тому всі країни світу докладають чималих зусиль для забезпечення розвитку інформаційної сфери, створення відповідного комп’ютерного середовища. Зусиллями багатьох організацій, насамперед Кібернетичного центру НАН України, інших колективів учених і фахівців в Україні, створена платформа розвитку інформаційного суспільства.
До речі, світова індустрія інформаційних і комунікаційних комп’ютерних технологій, за оцінками Світового банку, становить близько 1000 млрд. Дол.., і хоча темпи її розвитку найвищі у світовому ринку (11% щорічно), попит на засоби інформатизації залишається далеко незадоволеним і зростає ще більшими темпами. Така тенденція прогнозується і на наступні десятиріччя.
США явно випереджають інші промислово розвинені країни світу за темпами комп’ютеризації усіх сфер господарювання. Вони контролюють понад 65% світового комп’ютерного ринку, 63% ринку програмного забезпечення Західної Європи, 53% аналогічного ринку Японії. З десяти найбільших у світі фірм, що розробляють прорамне забезпечення, шість – американські. Американським фірмам та університетам належить більша частина світових патентів у галузі інформаційних технологій.
У сфері розробки та використання ІТ справжньою революцією стало створення Інтернету. У цій специфічній галузі світової економіки з річним обігом більш як 500 млн. Доларів уже нині зайнято понад 3 млн. Людей.
Варто зазначити, досягнення українських вчених в галузі оптимізації, математичного моделювання – світового рівня! Саме цим пояснюється той факт, що в складеній конкурентній боротьбі за місце на світовому ринку комп’ютерних технологій нашим фахівцям нерідко вдається знайти свою нішу і здобути визнання.
В Україні за різними експертними оцінками, протягом останніх років спостерігається постійне зростання ринку комп’ютерних засобів (15-20% щорічно). Ринок комп’ютерного обладнання, програмних засобів і різноманітних послуг тільки у кризовому 1996 році у нашій країні можна оцінити не менш як у 500 млн. Дол.. США.
Отже, можемо зробите маленький висновок, рівень розвитку комп’ютерних технологій стає складовою „невагомої економіки” – тобто „економіки знань” і невід’ємною частиною кожної країни, кожного із нас.
1. Загальні теоретичні відомості
1.1 Мова програмування Java
Джава (англ. Java) - об'єктно-орієнтована мова програмування, розроблена на початку 90-их компанією Sun Microsystems. У офіційній реалізації, Java програми компілюється в байткод, який компілюється в рідний машинний код при запуску. Sun Microsystems надає компілятор Java та віртуальну машину Java, які задовольняють специфікації Java Community Process, під ліцезією GNU General Public License. Мова значно запозичила синтаксис із C і C++, але має простішу об'єктну модель і менше низькорівненвих можливостей. Мова сценаріїв JavaScript має схожу із Java назву і синтаксис, але не повязана із Java. Мова програмування Java зародилася в 1991 р. в лабораторіях компанії Sun Microsystems inc. Головним мотивом створення Java була потреба в мові програмування, яка б не залежала від платформи (тобто від архітектури) і яку можна було б використовувати для створення програмного забезпечення, яке вбудовується в різноманітні побутові електронні прилади, такі як мобільні засоби зв'язку, пристрої дистанційного керування тощо. Розробка першої робочої версії зайняла 18 місяців і вона мала назву «Oak», але 1995 р. проект був перейменований на «Java». Найбільш цікавою властивістю є те, що програма на Java компілюється в псевдокод, який виконується віртуальною машиною (реалізація такої машини — своя для кожної платформи). Цим досягається можливість виконувати програмне забезпечення під будь-якою операційною системою, для якої реалізовано віртуальну машину. Період становлення Java співпав за часом з розквітом міжнародної інформаційної служби World Wide Web. Ця обставина відіграла вирішальну роль в майбутньому Java, оскільки Web теж вимагала платформо-незалежних програм. Як наслідок, були зміщені акценти в розробці Sun з побутової електроніки на програмування для Інтернет.
Програми на Java утворені з визначень класів та інтерфейсів. Класи містять змінні та сталі, які утримують дані, методи, які виконують дії, та конструктори, які створююсть екземпляри класів — об'єкти. Дані можуть мати простий тип (наприклад байт, ціле число, символ) або бути посиланням на об'єкт. Мова Java є статично типізованою.
1.1.1 Лексична структура
Java програми записуються в Юнікоді, також надається лексичне перетворення, яке дозволяє записувати символи Юнікоду керівними кодами Unicode за допомогою лише множини символів ASCII. Мова Java представляє текст послідовностями 16-бітний кодових одиниць, використовуючи кодування UTF-16. За винятком коментарів, ідентифікаторів та вмісту символьних та рядкових літералів, всі вхідні елементи програми на Java складаються із символів ASCII або відповідних їм керівних кодів Unicode.
1.1.2 Типи даних
Java є сильно типізованою мовою, кожна змінна та вираз має тип, відомий на етапі компіляції. Типи мови Java належать до двох категорій: прості (primitive) та вказівникові (reference). До простих типів належить бульовий тип та числові типи. Числові типи складаються із цілих типів byte, short, int, long, char та дійсних типів float, double. Вказівникові типи складаються із класів, інтерфейсів, масивів. Значенням вказівникового типу є вказівник на об'єкт — екземпляр класу чи масиву. Рядки є об'єктами класу String.
1.1.3 Короткий огляд задачі, що розв’язується
Задача лінійного програмування — задача оптимізації з лінійною цільовою функцією та допустимою множиною обмеженою лінійними рівностями або нерівностями.
Тобто, необхідно мінімізувати
(1.1.3.1)
при обмеженнях:
(1.1.3.2)
(1.1.3.3)
(1.1.3.4)
де c>j> (j = 1, ..., n), a>ij>(i = 1, ..., m) — задані числа.
Задача максимізації функції зводиться до задачі мінімізації шляхом заміни знаків всіх коефіціентів c>j> на протилежні.
Лінійне програмування (та дослідження задачі лінійного програмування) є однією із найрозвинутишіх галузей математичного програмування та теорії оптимізації. Загальна постановка задачі лінійного програмування, та один із підходів до її розв'язання (ідея розрішаючих множників або двоїстих оцінок) вперше наведено в роботі радянського вченого Канторовича Л. В. в 1939. В цій же роботі намічено один із методів розв'язання задачі — метод послідовного зменшення невязок.
2. Функціональне призначення
Задача лінійного програмування широко використовується для рішення задач прикладної математики.
В сучасній ринковій економіці в умовах жорсткої конкуренції і боротьби за кожен відсоток рентабельності – а, значить, конкурентної здатності – ефективність вирішення задач з багатьма взаємопов’язаними факторами набуває вирішального значення, коли потрібно прорахувати ефективність виробничого процесу з огляду на різні фактори ризику – кон’юнктуру ринку, наявність сировини, доступ до джерел енергії, демографічну ситуацію та навіть наслідки глобального потепління.
3. Аналіз методів розв’язання даної задачі
3.1 Метод потенціалів
Метод потенціалів — розроблений в 1940 радянськими вченими Канторовічем Л. В. та Гавуріним Л. В. в застосуванні до транспортної задачі;
Розглянемо алгоритм даного методу:
1. Порівнюють загальний запас вантажу з сумарним попитом іі у випадку порушення балансу приводять задачу до закритої моделі.
2. Умову задачі записують у формі транспортної таблиці.
3. Будують початковий опорний план перевезень
4. Перевіряють умову для базисних клітин (їх повинно бути m+n-1): якщо ця умова не виконується, то в одну з вільних клітинок (як правило, в клітинку з найменшим тарифом) вписуюють число 0, і така клітина вважається базисною. Однак число 0 записуюють тільки в ті вільні клітинки, які не утворюють циклів з раніше зайнятими клітинками.
5. Обчислюють потенціали u>i> i v>j>. Кожному постачальнику (кожній стрічці) ставлять у відповідність деяке число u>i>, яке називають потенціалом постачальника А>і> (і=1,m), і записуюють праворуч таблиці, а кожному споживачу (або стовпчику) – деяке число v>j>> >, яке називають потенціалом споживача В>j> (j=1,n), і записують під таблицею. Числа u>i> i v>j>> >вибирають так, щоб у будь-якій базисній клітинці їх сума дорівнювала тарифу, тобто u>i>+v>j>=с>і>>j>. Так, як кількість всіх потенціалів u>i> i v>j> складає m+n, а зайнятих клітинок m+n-1, то для визначення чисел u>i> i v>j> доведется вирішувати систему із m+n-1 рівнянь з m+n невідомими. Тому одному із невідомих потенціалів надають довільне значення. Тоді інші визначаються однозначно.
6. Для перевірки оптимальності плану переглядають вільні клітинки, для яких визначають оцінки ∆>і>>j> – різниця між тарифом клітинки і сумою потенціалів строки і стовпчика, тобто ∆>і>>j>= с>і>>j>-( u>i>+v>j>). Економічно, оцінка покаже на скільки грошових одиниць змінятся транспортні витрати від завантаження даної клітинки одиницею вантажу. Якщо всі оцінки невід′ємні, тобто ∆>і>>j>≥0, то план оптимальний і залишається підрахувати транспортні витрати. Інакше переходять до пункту 7.
7. З від′ємних оцінок ∆>і>>j>≤0 вибирають мінімальну. Нехай це буде ∆>і>>k>. Тоді клітинку (1, k) вводять в число базисних, тобто будують цикл по завантаженим клітинкам з початком в цій клітинці і перерозподіляють поставки так, щоб баланс циклу зберігався. Для цьогго вершинам циклу приписують знаки „+” і ”-”, які чергуються, (вільній клітинці (1, k) приписують позитивний знак „+”). В „мінусових” клітинках віднаходять найменший вантаж w, тобто w=min x>і>>j>=x>st>, який і переміщається клітинками замкнутого циклу, тобто додається до перевозок x>і>>j> в клітинках зі знаком „+” (включаючи вільну) і віднімається з перевозок x>і>>j> в клітинках із знаком ”-”. З цього слідує, що клітинка (s, t) стане вільною і змінна x>st> вийде з базису. Значення інших базисних змінних переписуюються. Таким чином, отримуюють або одержують нову транспортну таблицю с поліпшеним планом, для якого транспортні витрати змінюються на величину ∆>1>>k>* x>st>. Переходять до пункту №4.
3.2 Симплекс-метод
Симплекс-метод — цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим Данциґом Дж.-Б. в 1949 році.
Симплекс-метод — метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку; симплекс-метод також називають методом поступового покращення плану.
Розглянемо опис методу:
Нехай невироджену задачу лінійного програмування представлено в канонічному вигляді:
(3.2.1)
(3.2.2)
де X
= (x>1>,
…, x>n>)
— вектор змінних, C
= (c>1>,
…., c>n>),
B
= (b>1>,
…, b>m>)T,
A>j>
= (a>1>>j>,
…, a>mj>)T,
j
= 1, …, n
— задані вектори, T
— знак транспонування, та
відмінні від нуля компоненти опорного
плану, для полегшення пояснення
розташовані на перших m
місцях вектору X.
Базис цього плану —
Тоді
(3.2.3)
(3.2.4)
де
значення лінійної форми на даному плані.
Так як вектор-стовпці матриці A лінійно
незалежні, будь який із векторів умов
A>j> розкладається
по ним єдиним чином:
(3.2.5)
(3.2.6)
(3.2.7)
де x>ij> - коефіцієнт розкладання. Система умов
(3.2.8)
z>k> ≥ 0, x>j> = 0, j = m + 1, …, n, j ≠ k (3.2.9)
при заданому k визначає в просторі змінних задачі промінь, який виходить із точки, яка відповідає опорному плану, що розглядається. Нехай значення змінної x>k> при русі по цьому проміню дорівнює θ, тоді значення базисних змінних дорівнюють x>i>(θ). В цих позначеннях рівняння (5) можна представити в вигляді:
(3.2.10)
помноживши рівняння (3) на θ при j = k та віднявши від рівняння (1), отримаємо:
(3.2.11)
Із рівнянь (10-11) отримаємо:
(3.2.12)
Оскільки x>i>(θ) при θ = 0 визначають план задачі, то найбільше θ, яке не порушує обмеження x>i> (θ) ≥ 0, визначається із умови:
(3.2.13)
де I = {i | x>ik> > 0}
В силу невиродженості задачі мінімум досягається не більш ніж для одного i = J та θ > 0. Значення лінійної форми при θ = θ0 визначається із рівнянь (9), (4), (2)
(3.2.14)
де Δ>k> = z>k> — c>k>. Очевидно, Δ>j> = 0 для j = 1, …, m.
Нехай
— початковий базис із m одиничних
векторів. Всі дані задачі записуються
у вигляді симплекс-таблиці (першої
ітерації обчислювального процесу).
Симплекс-алгоритм розв'язання задачі
лінійного програмування складається
із наступних операцій:
1. Знайти Δ>k >= min>j>Δ>j>. Якщо Δ>k> = 0, тоді план, який розглядається оптимізовано; якщо Δ>k> < 0, вектор A>k> вводиться в базис;
2. Знайти θ>0>
та l для якого
,
із формули (10). Якщо I = Λ — порожня множина,
лінійна форма необмежена зверху; якщо
I ≠ Λ вектор A>l>
виводиться із базису;
3. По знайденим l, k обчислити нові значення елементів таблиці по формулам
Перетворення (12) замінює вектор коефіцієнтів X>k> = (x>1k>, …, x>mk>) на одиничний вектор X>k> з x>lk> = 1. В силу монотонного збільшення x0 повернення до вже пройденого плану неможливе, а із скінченності кількості опорних планів випливає скінченність алгоритму. Початковий опорний план з одиничним базисом можна отримати, розв'язавши описаним алгоритмом допоміжну задачу,
(3.2.15)
при обмеженнях
(3.2.16)
(3.2.17)
(3.2.18)
яка містить
одиничний базис, який складається із
векторів A>n+1>,
…, A>n+m>.
Цим векторам відповідають штучні змінні
із значеннями
,
i = 1, …, m. Якщо в оптимальному розв'язку
цієї задачі
,
вихідна задача не має розв'язку. Якщо ж
та задача невироджена, оптимальний
базис складається лише тільки із векторів
вихідної задачі, які по формулам (12)
перетворені в одиничну матрицю. Якщо
задача має невироджені плани, значення
z>0>
може не збільшуватись на ряді ітерацій.
Це відбувається через те, що значення
відповідних дорівнює нулю та визначається
неоднозначно. В таких випадках монотонність
методу порушується і може трапитись
зациклювання, тобто, повернення до вже
пройденого базису. Невелика зміна
вектора обмежень задачі, яка полягає в
заміні величин b>i>
на b>i>
+ ε>i>,
де ε>i>
достатньо малі, при вдалому виборі ε>i>
не змінюють множину векторів оптимального
опорного плану вихідної задачі і робить
її невиродженою.
Описаний вище алгоритм називається першим (або прямим) алгоритмом симплекс-методу. Також відомий другий алгоритм (алгоритм із оберненою матрицею). В ньому перетворюється лише матриця A-1, обернена до базисної матриці.
3.3 Двоїстий симплекс-метод
Двоїстий симплекс-метод розроблений згодом після прямого симплекс-методу, і який є, по суті, симплекс-методом розв'язання двоїстої задачі лінійного програмування, але сформульованої в термінах вихідної задачі.
Симплекс метод приміняється для рішення задач с невідємними вільними членами в>і> і вільні у виборі знаку приведеними коефіцієнтами цільової функції с>j>’. Іноді буває легше знайти базис, який задовільняє ознаку оптимальності (усі с>j>’ ≥0), але не задовільняє критерії допуску (не всі в>і> ≥0). Варіант симплекс метода, який приміняється для рішення таких задач, називається двоїстим симплекс методом. За його допомоги рішаються задачі лінійного програмування виду:
(4.3.1)
де система обмежень має такий вигляд і всі приведені коефіцієнти цільової функції с>j>’ ≥0, і=1,n. При цьому умова в>і> ≥0, і=1,т , не потрібно. Виділену таким методом задачу будемо називати задачею в двоїстій базисній формі. Вона має базисне, але не опорне рішення.
Двоїстий симплекс метод, який приміняється до задачі в двоїстій базисній формі, приводить до послідовності задач із збільшуючим значаченням цільової функції з невідємними коефіцієнтами с>j>’ , j=1,n і значеннями в>і>, і=1,т будь-якого знаку. Двоїстий симплекс метод називають методом поступового покращення оцінок. Перебудова задачі виконується до тих пір, поки не буде встановлено, що вихідна задача не має допустимого рішення або буде отримана задача з допустимим базисним планом (всі в>і> ≥0), який одночасно буде і оптимальним.
Розглянемо етапи рішення задач ЛП двоїстим симплекс методом:
Привести вихідну задачу до канонічного виду.
Виключити базисні змінні із цільової функції z.
3. Перевірити приведені коефіцієнти цільової функції: якщо всі преведені коефіцієнти с>j>’ ≥0, j=1,n, а серед значень в>і>, і=1,т, є від'ємні, то задача рішається двоїстим симплекс методом. Якщо серед приведених коефіцієнтів с>j>’ є додатні, то в системі обмежень слід пребудувати вільні члени в невід'ємні (перемноживши на число (-1) стрічки, які містять від'ємні в>і>) і вирішувати задачу прямим симплекс методом.
4. Опис логічної структури програми
Дана програма умовно розділена 8 модулів, які і утворюють програму, що розв′язує дану нам систему сиплекс методом. Всього є 8 модулів. Кожний модуль окремо відповідає за певну функцію, яку він повинен виконувати.
Модулі під назвою „colorPanel” та „numberCrunchingFrame”. Дані модулі відповідають за візуальне оформлення нашої програми. В ньому ми реалізовуєм кольори вікон,клавіші за допомогою яких ми будемо вводити данні і просуватися по програмі, розміри та всі інші параметри, які мають відношення до візульного оформлення нашої програми.
”SimplexTool.java” В даному модулі ми ініціалізуємо основне вікно нашої програми. В ньому ми вводимо всі обмеження: кількість рівнянь в нашій системі (Constraint) та кількість обмежень (Variable).
Модуль „Matrix.java” даний модуль проводить всі дії з матрицями. Знаходить визначники, і т.д.
„Numbertextfield.java” Даний модуль перевіряє дані, які ввели з клавіатури на правильність. Тобто перевіряє правальність заданої кількості (в дані програмі можливо тільки від 2 до 7) рівнянь та обмежень функції.
„problemDimensionWindow.java” Даний модуль відповідає за діалогове вікно в яке ми вводимо початкові дані (коефіцієнти функції, рівнянь нашої системи рівнянь та знаки рівності або нерівності)
Модуль „revisedSimplex.java” реалізує сам симплекс метод. Наведемо деякі методи з даного класу:
а) public revisedSimplex(int nv, int nc) – ініціалізує об’єкти класу revisedSimplex: nv (Number of Variables – кількість рівнянь), nc (Number of Constrains – кількість обмежень)
б) public int iterateOneStep() – виконання поточної ітерації
в) public int iterateOneStep()- відповідає за проведення усіх кроків одної ітерації.
г) public float calculateObjective() – функція знаходження значення цільової функції.
д) public void chooseLeavingVariable() – знаходження змінної , яка буде виведена із базису.
е) public void updateSolution() – функція, яка обновляє рішення задачі
є) public void ChooseEnteringVariable() - знаходження змінної , яка буде введена в базис.
ж) public boolean testUnboundedness() – функція перевірки існування рішення.
з) public
void
calculateReducedCosts()
– підрахунок значень індексної стрічки
(
)
(4.1)
и) public boolean testForOptimality() – перевірка, чи являється поточне значення цільової функції оптимумом, тобто вірним рцшенням.
і) private void makeBt() – заповнення матриці вільних членів
private void makeB() – заповнення основної матриці.
й) public void addConstraint(float [] coefficients, float rhs, int type) – додавання умови
к) public void specifyObjective(float [] coefficients, boolean type) – відповідає за ініціалізацію цільової функції
л) public boolean preprocess(int numberOfVariables, int numberOfConstraints) – функція, заповнення и виведення данних, які ми вводимо на екран.
м) public void SetCostForPhaseOne() - визначає можливість вирішення данної задачі.
н) public float Dot (float []row, float []col, int size) - підраховування суми:
(4.2)
о) public void reset(int numberOfVariables, int numberOfConstraints) – функція, яка закриває поточне вирішення задачі і дає можливість вести нові початкові дані.
7. Модуль „enterDataFrame.java” Модуль за допомогою якого дані, які вводить користувач присвоюються виділеним змінним. Тобото проводить їх ініціалізацію.
5. Технічні засоби
У розробленні даної програми було використано обладнання з такими характеристиками: а) Процесор: Intel Pentium 4, 1,8 Ггц; б) ОЗУ: 256 Мб; в) HDD: 40 Гб; г) Відеокарта – GeForce 5500 – 128 Mб; д) операційна система Windows XP Professional SP2;
Вище приведені дані саме того комп′ютера, на якому розроблялась програма. Ця програма не тестувалась на іншому обладнанні, але за її складністю та використанню ресурсів (приблизно 19 000 Кб) можна сказати, що дана програма не потребує великого об′єму пам′яті, що дасть їй можливість коректно працювати і на іншому обладнанні нижчого рівня, ніж приведений.
6. Виклик та завантаження програми
Для того, щоб скористуватися даною програмою потрібно просто скопіювати її на жорсткий диск. Детальнішої установки вона не потребує. Для запуску програми потрібно вибрати файл з назвою “run (пакетний файл MS-DOS)” та запустити його на виконання. Після проведення даної дії з′явиться діалогове вікно роботи з програмою.
7. Вхідні та вихідні данні
Після запуску програми на виконання програма пропонує ввести такі данні: а) кількість рівнянь та кількість обмежень; б) після цього з’являється вікно в якому потрібно ввести коефіцієнти функції та коефіцієнти рівнянь системи; в) потім потрібно вибрати куди прямує функція (МАХ або MIN); г) вибрати знаки рівності або нерівності (=, ≥, ≤)
Після того, як програма все підрахує на екрані з’являється матриця, в якій будуть знаходитись відповідь та повідомлення рішення даної задачі або неможливість рішення.
Інструкція для користувача
Для коректної роботи з програмою потрібно мати певну базу знань англійської мови, адже всі посилання, назви, та написи на клавішах написано виключно на англійські мові. Щодо користування даної програми, то воно досить просте та елементарне: вводите в діалоговому вікні коефіцієнти функції та систем рівнянь, вибираєте МАХ або MIN (відповідно до задачі, яка перед вами ставиться) та натискаєте клавішу рішення. Далі є два варіанти подальшої роботи з програмою – перший – це одразу отримати кінцевий результат, а інший – натискати клавішу виконання завдання декілька раз. Другий спосіб дає можливість поступово (крок за кроком) спостерігати за роботою програми та вирішенні задачі. Все це представлено на рис. 9.1
Висновки
В даній роботі ми розглянули одну з задач лінійного програмування та методи її вирішення. Один з методів покладений в основу роботи даної програми – симплекс метод. Виконуючи курсову я вдосконалив свої знання та навички використання мови програмування Java. Робота вимагала знань основ алгоритмічної мови, вміння складати програми різної складності використовуючи дану мову програмування. Я вдосконалив свої знання у області роботи з класами, методами, функціями та вказівниками. Набув суттєвих практичних навиків у роботі з компілюванням файлів Java.
Література
1 Симплекс метод. Материал из Википедии — свободной энциклопедии - http://ru.wikipedia.org/wiki/Симплекс метод
2 Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования М.: Наука, 1976р. – 409с.
3 Карманов В.Г. Математическое программирование. – М.: Наука, 1986р. -250с.
4 Иванов Ю.П., Лотов А.В. Математические модели в экономике. – М.: Наука, 1979р. -359с.
5 Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. – М.:
Наука, 1978р. -506с.
6 Бронштейн И.Н., Семендяев К.А. Справочник по математике. – М.: Наука, 1986р.560с.
7 Коробов П.Н. Математическое программирование и моделирование
экономических процессов.- С.Т.Б. Издательство ДНК 2003р. -601с.
1