Современные информационные технологии/3.Программное обеспечение

Царьова А.М., Зайцева Т.А., Фридман О.Д., Шишканова А.А.*

Дніпропетровський національний університет ім. О.Гончара, *Запорізький національний технічний університет

Розробка програмного забезпечення

для розрахунків задач лінійного програмування

Лінійне програмування - один з перших і найбільш детально вивчених розділів математичного програмування. Саме лінійне програмування з'явилося тим розділом, з якого почала розвиватися сама дисципліна «математичне програмування» [1]. Воно застосоване для побудови математичних моделей тих процесів, в основу яких може бути покладені економічні завдання, завдання управління і планування, оптимального розміщення устаткування та ін. Завданнями лінійного програмування називаються завдання, в яких лінійні як цільова функція, так і обмеження у вигляді рівності і нерівностей. Для них характерний показник ефективності (цільова функція) виражається лінійною залежністю; обмеження на рішення – лінійна рівність або нерівності. Коротко завдання лінійного програмування можна сформулювати таким чином - знайти вектор значень змінних, що доставляють екстремум лінійної цільової функції при m обмеженнях у вигляді лінійної рівності або нерівностей.

Сучасне програмне забезпечення для вирішення завдань лінійного програмування─це алгоритмічне програмне забезпечення розраховане на знаходження оптимальних розв’язкiв конкретних завдань. На вході задається список коефіцієнтів обмежень і на виході видається результат - оптимальні значення змінних [2].

Розглянемо можливості існуючих програмних продуктів для рішення завдань лінійного програмування. Simka - програма, яка має наступнi обмеження – максимальне число невідомих не бiльш 200, а максимальна кiлькiсть обмежень кожного виду до 40. Програма виконує дві перевірки отриманого рішення: перевірку допустимості рішення і перевірку оптимальності рішення. Програма розв’язує завдання одним методом – модифікованим симплекс методом, причому шукає мінімум (лише) цільової функції. Дані готуються у вигляді текстового файлу певної структури. Scalc v1.5 - програма для розв’язку задач лінійного програмування симплекс методом. Iснує три режими рішення завдань: автоматичний, покроковий і ручний. У першому режимі програма сама вибирає вирішуючий стовпець і рядок, які забезпечують максимальне зростання або зменшення цільової функції. А також автоматично перераховує всі таблиці. У покроковому режимі, кожна перерахована таблиця виводиться на екран. У ручному режимі користувач сам обирає вирішуючий рядок і стовпець. Також є можливість експорту всіх таблиць, отриманих в ході рішення задачі, в Excel. Програма Simplexwin призначена для вирішення завдань лінійного програмування симплекс методом. Процес рішення повністю автоматизований. Додаткові змінні і штучні базиси вводяться автоматично. Є повна підтримка звичайних дробів. Є можливість складання двоїстої задачі. Підтримується завантаження і збереження даних у файл і виведення результатів в Excel [3, 4].

Розглянувши основні види симплекс методу, а саме симплексний метод, метод штучного базису, модифікований симплекс метод, двоїсті задачі, було розроблено програмне забезпечення, яке дозволяє :

§ проводити тестування по кожному з вище зазначених видів методу (відповідний вид метода для тестування обирається користувачем);

§ обирати тестування тільки з варіантами відповідей: користувач бачить на екрані задачу метода та варіанти відповідей серед яких він повинен обрати букву, яка відповідає правильному розв’язку;

§ виводити на екран результати тестування з вказанням номеру завдання і номеру тесту, відповіді, яку обрав користувач та позначкою чи вірна ця відповідь чи ні.

§ розв’язувати будь яким з видів методу довільну задачу лінійного програмування, яку задає користувач, при цьому в залежності від вибору користувача він може отримати або тільки кінцевий розв’язок, або проглянути всі проміжні кроки розв’язку, які обчислюються автоматично [5].

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

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

Література:

1. Ашманов С.А. Линейное программирование.-М.: Наука, 1981, 158 с.

2. Давыдов Э.Г. Исследование операций. – М.:Высш. шк. ,1990, 213 с.

3. Данциг Дж. Линейное программирование, его обобщение и приложения. — М.: Прогресс, 1966, 78 с.

4. Муртаф Б. Современное линейное программирование. Теория и практика. — М.: Мир, 1984, 67 с.

5. Царьова А.М., Зайцева Т.А., Фридман О.Д. Розробка програмного пакету для розв’язку спеціальних задач лінійного програмування // Тези, Міжнародна научно-практична конференція «Перспективні інновації в науці, освіті, виробництві та транспорті 2009», 2009, с.3-4.