28
29
Міністерство освіти та науки України
Вінницький національний технічний університет
Інститут автоматики, електроніки та комп'ютерних систем управління
Факультет АКСУ
Кафедра АІВТ
Курсова робота
з дисципліни
«Алгоритмічні мови та програмування»
Аналіз методів рішення задачі лінійного програмування
симплекс-методом
Технічне завдання
Розробити програму, що дозволяє знайти рішення системи рівнянь:
при умовах , що забезпечує найменше значення функції
Мова програмування - 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 млн. Дол.. США.
Отже, можемо зробите маленький висновок, рівень розвитку комп'ютерних технологій стає складовою „невагомої економіки” - тобто „економіки знань” і невід'ємною частиною кожної країни, кожного із нас.
Джава (англ. 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 є статично типізованою.
Java програми записуються в Юнікоді, також надається лексичне перетворення, яке дозволяє записувати символи Юнікоду керівними кодами Unicode за допомогою лише множини символів ASCII. Мова Java представляє текст послідовностями 16-бітний кодових одиниць, використовуючи кодування UTF-16. За винятком коментарів, ідентифікаторів та вмісту символьних та рядкових літералів, всі вхідні елементи програми на Java складаються із символів ASCII або відповідних їм керівних кодів Unicode.
Java є сильно типізованою мовою, кожна змінна та вираз має тип, відомий на етапі компіляції. Типи мови Java належать до двох категорій: прості (primitive) та вказівникові (reference). До простих типів належить бульовий тип та числові типи. Числові типи складаються із цілих типів byte, short, int, long, char та дійсних типів float, double. Вказівникові типи складаються із класів, інтерфейсів, масивів. Значенням вказівникового типу є вказівник на об'єкт -- екземпляр класу чи масиву. Рядки є об'єктами класу String.
Задача лінійного програмування -- задача оптимізації з лінійною цільовою функцією та допустимою множиною обмеженою лінійними рівностями або нерівностями.
Тобто, необхідно мінімізувати
(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. В цій же роботі намічено один із методів розв'язання задачі -- метод послідовного зменшення невязок.
Страницы: 1, 2
