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)
де cj (j = 1, ..., n), aij(i = 1, ..., m) — задані числа.
Задача максимізації функції зводиться до задачі мінімізації шляхом заміни знаків всіх коефіціентів cj на протилежні.
Лінійне програмування (та дослідження задачі лінійного програмування) є однією із найрозвинутишіх галузей математичного програмування та теорії оптимізації. Загальна постановка задачі лінійного програмування, та один із підходів до її розв'язання (ідея розрішаючих множників або двоїстих оцінок) вперше наведено в роботі радянського вченого Канторовича Л. В. в 1939. В цій же роботі намічено один із методів розв'язання задачі — метод послідовного зменшення невязок.
2. Функціональне призначення
Задача лінійного програмування широко використовується для рішення задач прикладної математики.
В сучасній ринковій економіці в умовах жорсткої конкуренції і боротьби за кожен відсоток рентабельності – а, значить, конкурентної здатності – ефективність вирішення задач з багатьма взаємопов’язаними факторами набуває вирішального значення, коли потрібно прорахувати ефективність виробничого процесу з огляду на різні фактори ризику – кон’юнктуру ринку, наявність сировини, доступ до джерел енергії, демографічну ситуацію та навіть наслідки глобального потепління.
3. Аналіз методів розв’язання даної задачі
3.1 Метод потенціалів
Метод потенціалів — розроблений в 1940 радянськими вченими Канторовічем Л. В. та Гавуріним Л. В. в застосуванні до транспортної задачі;
Розглянемо алгоритм даного методу:
1. Порівнюють загальний запас вантажу з сумарним попитом іі у випадку порушення балансу приводять задачу до закритої моделі.
2. Умову задачі записують у формі транспортної таблиці.
3. Будують початковий опорний план перевезень
4. Перевіряють умову для базисних клітин (їх повинно бути m+n-1): якщо ця умова не виконується, то в одну з вільних клітинок (як правило, в клітинку з найменшим тарифом) вписуюють число 0, і така клітина вважається базисною. Однак число 0 записуюють тільки в ті вільні клітинки, які не утворюють циклів з раніше зайнятими клітинками.
5. Обчислюють потенціали ui i vj. Кожному постачальнику (кожній стрічці) ставлять у відповідність деяке число ui, яке називають потенціалом постачальника Аі (і=1,m), і записуюють праворуч таблиці, а кожному споживачу (або стовпчику) – деяке число vj, яке називають потенціалом споживача Вj (j=1,n), і записують під таблицею. Числа ui i vjвибирають так, щоб у будь-якій базисній клітинці їх сума дорівнювала тарифу, тобто ui+vj=сіj. Так, як кількість всіх потенціалів ui i vj складає m+n, а зайнятих клітинок m+n-1, то для визначення чисел ui i vj доведется вирішувати систему із m+n-1 рівнянь з m+n невідомими. Тому одному із невідомих потенціалів надають довільне значення. Тоді інші визначаються однозначно.
6. Для перевірки оптимальності плану переглядають вільні клітинки, для яких визначають оцінки ∆іj – різниця між тарифом клітинки і сумою потенціалів строки і стовпчика, тобто ∆іj= сіj-( ui+vj). Економічно, оцінка покаже на скільки грошових одиниць змінятся транспортні витрати від завантаження даної клітинки одиницею вантажу. Якщо всі оцінки невід′ємні, тобто ∆іj≥0, то план оптимальний і залишається підрахувати транспортні витрати. Інакше переходять до пункту 7.
7. З від′ємних оцінок ∆іj≤0 вибирають мінімальну. Нехай це буде ∆іk. Тоді клітинку (1, k) вводять в число базисних, тобто будують цикл по завантаженим клітинкам з початком в цій клітинці і перерозподіляють поставки так, щоб баланс циклу зберігався. Для цьогго вершинам циклу приписують знаки „+” і ”-”, які чергуються, (вільній клітинці (1, k) приписують позитивний знак „+”). В „мінусових” клітинках віднаходять найменший вантаж w, тобто w=min xіj=xst, який і переміщається клітинками замкнутого циклу, тобто додається до перевозок xіj в клітинках зі знаком „+” (включаючи вільну) і віднімається з перевозок xіj в клітинках із знаком ”-”. З цього слідує, що клітинка (s, t) стане вільною і змінна xst вийде з базису. Значення інших базисних змінних переписуюються. Таким чином, отримуюють або одержують нову транспортну таблицю с поліпшеним планом, для якого транспортні витрати змінюються на величину ∆1k* xst. Переходять до пункту №4.
... розвиток як математична теорія лінійного і нелінійного програмування, так і додаток її методів до дослідження різних економічних проблем. У 1949 р. американським математиком Дж. Данцигом (GB Dantzig) був опублікований симплекс-метод - основний метод рішення задач лінійного програмування. Термін «лінійне програмування» вперше з'явився в 1951 р. в роботах Дж. Данцига і Т. Купманса. При всьому ...
... і екстремуми, полягає в послідовному виборі числових значень , після реалізації, якого дана система зважується відносно х. 3. ВИКОРИСТАННЯ МЕТОДУ ЯКОБІ ДЛЯ РІШЕННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ Дано задачу лінійного програмування, у якій потрібно максимізувати z=2xi+3xa при обмеженнях х1+х2+х3=5 х1-х2+х4=3 х1,х2,х3,х4>0 Розглянемо обмеження xj>0 устанавлюючи не заперечність перемі ...
... зумовлюється метою, якої хочуть досягти даною геометричною інтерпретацією та особливостями структури самої задачі, в тому числі й формою її представлення. Для геометричної інтерпретації візьмемо основну задачу лінійного програмування у другій стандартній формі. Для наочності розглянемо найпростіший випадок, коли в системі обмежень (26) і цільовій функції (25) є лише дві змінних, Розглянемо розв' ...
... , а при більшому числі змінних - взагалі неможливим. Незважаючи на це, розгляд графічного методу дасть змогу зробити висновки, що послужать основою для розробки загального методу розв’язання задач лінійного програмування[2]. Перший крок при використанні графічного методу полягає в поданні області допустимих розв’язків, у якій водночас задовольняються всі обмеження моделі. Нехай шукана область ( ...
0 комментариев