ВВЕДЕННЯ - Рішення оптимізаційної задачі лінійного програмування
В даний час оптимізація знаходить застосування в науці, техніці і в будь-якій іншій області людської діяльності.
Оптимізація - цілеспрямована діяльність, що полягає в отриманні якнайкращих результатів за відповідних умов.
Пошуки оптимальних рішень привели до створення спеціальних математичних методів і вже в 18 столітті були закладені математичні основи оптимізації (варіаційне числення, чисельні методи і др). Проте до другої половини 20 століть методи оптимізації в багатьох областях науки і техніки застосовувалися дуже рідко, оскільки практичне використання математичних методів оптимізації вимагало величезної обчислювальної роботи, яку без ЕОМ реалізувати було украй важко, а у ряді випадків - неможливо.
Постановка завдання оптимізації припускає існування конкуруючих властивостей процесу, наприклад:
кількість продукції - витрата сировини
кількість продукції - якість продукції
Вибір компромиcного варіанту для вказаних властивостей і є процедурою рішення оптимізаційної задачі.
При постановці завдання оптимізації необхідно:
1. Наявність об'єкту оптимізації і мети оптимізації. При цьому формулювання кожного завдання оптимізації повинне вимагати екстремального значення лише однієї величини, тобто одночасно системі не повинно приписуватися два і більш за критерії оптимізації, оскільки практично завжди екстремум одного критерію не відповідає екстремуму іншого. Приведемо приклади.
Типовий приклад неправильної постановки завдання оптимізації:
"Отримати максимальну продуктивність при мінімальній собівартості".
Помилка полягає в тому, що ставиться завдання пошуку оптимальності 2-х величин, що суперечать один одному за своєю суттю.
Правильна постановка завдання могла бути наступна:
- А) отримати максимальну продуктивність при заданій собівартості; Б) отримати мінімальну собівартість при заданій продуктивності;
У першому випадку критерій оптимізації - продуктивність а в другому - собівартість.
- 2. Наявність ресурсів оптимізації, під якими розуміють можливість вибору значень деяких параметрів об'єкту, що оптимізується. 3. Можливість кількісної оцінки величини, що оптимізується, оскільки тільки в цьому випадку можна порівнювати ефекти від вибору тих або інших дій, що управляють. 4. Облік обмежень.
Величина, що зазвичай оптимізується, пов'язана з економічністю роботи даного об'єкту (апарат, цех, завод). Варіант роботи об'єкту, що оптимізується, повинен оцінюватися якоюсь кількісною мірою - критерієм оптимальності.
Критерієм оптимальності називається кількісна оцінка якості об'єкту, що оптимізується.
На підставі вибраного критерію оптимальності складається цільова функція, що є залежністю критерію оптимальності від параметрів, що впливають на її значення. Вид критерію оптимальності або цільової функції визначається конкретним завданням оптимізації.
Таким чином, завдання оптимізації зводиться до знаходження екстремуму цільової функції.
Залежно від своєї постановки, будь-яке із завдань оптимізації може вирішуватися різними методами, і навпаки - будь-який метод може застосовуватися для вирішення багатьох завдань. Методи оптимізації можуть бути скалярними (оптимізація проводиться по одному критерію), векторними (оптимізація проводиться по багатьом критеріям), пошуковими (включають методи регулярного і методи випадкового пошуку), аналітичними (методи диференціального числення, методи варіаційного числення і ін.), обчислювальними (засновані на математичному програмуванні, яке може бути лінійним, нелінійним, дискретним, динамічним, стохастичним, евристичним і т. д.), теоретико-імовірнісними, теоретико-ігровими і ін. Піддаватися оптимізації можуть завдання як з обмеженнями, так і без них.
Лінійне програмування - один з перших і найбільш детально вивчених розділів математичного програмування. Саме лінійне програмування з'явилося тим розділом, з якого початку розвиватися сама дисципліна "математичне програмування". Термін "програмування" в назві дисципліни нічого спільного з терміном "програмування (тобто складання програм) для ЕОМ" не має, оскільки дисципліна "лінійне програмування" виникла ще до того часу, коли ЕОМ стали широко застосовуватися при рішенні математичних, інженерних, економічних і ін. завдань. Термін "лінійне програмування" виник в результаті неточного перекладу англійського "linear programming". Одне із значень слова "programming" - складання планів, планування. Отже, правильним перекладом "Linear programming" було б не "лінійне програмування", а "лінійне планування", що точніше відображає зміст дисципліни. Проте, термін лінійне програмування, нелінійне програмування і т. д. в наший літературі стали загальноприйнятими.
Отже, лінійне програмування виникло після Другої Світової Війни і став швидко розвиватися, привертаючи увагу математиків, економістів і інженерів завдяки можливості широкого практичного застосування, а так само математичній "стрункості".
Можна сказати, що лінійне програмування застосовне для побудови математичних моделей тих процесів, в основу яких може бути покладена гіпотеза лінійного представлення реального миру: економічних завдань, завдань управління і планування, оптимального розміщення устаткування і ін.
Завданнями лінійного програмування називаються завдання, в яких лінійні як цільова функція, так і обмеження у вигляді рівності і нерівностей. Стисло завдання лінійного програмування можна сформулювати таким чином: знайти вектор значень змінних, що доставляють екстремум лінійної цільової функції при m обмеженнях у вигляді лінійної рівності або нерівностей.
Лінійне програмування є найбільш часто використовуваним методом оптимізації. До завдань лінійного програмування можна віднести завдання:
Раціонального використання сировини і матеріалів; завдання оптимізації розкроу;
Оптимізації виробничої програми підприємств;
Оптимального розміщення і концентрації виробництва;
Складання оптимального плану перевезень, роботи транспорту;
Управління виробничими запасами;
І багато інших, що належать сфері оптимального планування.
Так, по оцінках американських експертів, близько 75% від загального числа вживаних оптимізаційних методів доводиться на лінійне програмування. Близько чверті машинного часу, витраченого останніми роками на проведення наукових досліджень, була відведена рішенню завдань лінійного програмування і їх численних модифікацій.
Перші постановки завдань лінійного програмування були сформульовані відомим радянським математиком Л. В. Канторовичем, якому за ці роботи була присуджена Нобелівська премія по економіці.
Значний розвиток теорія і алгоритмічний апарат лінійного програмування отримали з винаходом і розповсюдженням ЕОМ і формулюванням американським математиком Дж. Данцингом симплекс-метода.
В даний час лінійне програмування є одним з найбільш споживаних апаратів математичної теорії оптимального ухвалення рішення. Для вирішення завдань лінійного програмування розроблено складне програмное забезпечення, що дає можливість ефективно і надійно вирішувати практичні завдання великих об'ємів. Ці програми і системи забезпечені розвиненими системами підготовки початкових даних, засобами їх аналізу і представлення отриманих результатів.
У розвиток і вдосконалення цих систем вкладена праця і талант багатьох матеметиков, закумульований досвід рішення тисяч завдань. Володіння апаратом лінійного програмування необхідне кожному фахівцеві в області математичного програмування. Лінійне програмування тісно пов'язане з іншими методами математичного програмування (наприклад, нелінійного програмування, де цільова функція нелінійна).
Завдання з нелінійною цільовою функцією і лінійними обмеженнями називають завданнями нелінійного програмування з лінійними обмеженнями. Оптимізаційні завдання такого роду можна класифікувати на основі структурних особливостей нелінійних цільових функцій. Якщо цільова функція Е - квадратична функція, то ми маємо справу із завданням квадратичного програмування; якщо Е - це відношення лінійних функцій, то відповідне завдання носить назву завдання лінійного для дробу програмування, і т. д. Ділення оптимізаційних завдань на ці класи представляє значний інтерес, оскільки специфічні особливості тих або інших завдань грають важливу роль при розробці методів їх рішення.
Сучасні методи лінійного програмування досить надійно вирішують завдання загального вигляду з декількома тисячами обмежень і десятками тисяч змінних. Для вирішення надвеликих завдань використовуються вже, як правило, спеціалізовані методи.
Похожие статьи
-
Цінність ресурсу - це величина збільшення значення цільової функції при збільшенні запасів даного ресурсу на одиницю (або відповідно величина зменшення...
-
Етапи рішення прикладних задач з використанням комп'ютерів 1) Формулювання задачі в термінах певної предметної галузі знань (математика, фізика,...
-
ДРУГИЙ ЕТАП ДВОХЕТАПНОГО СИМЛЕКС-МЕТОДУ - Рішення оптимізаційної задачі лінійного програмування
Отже, як видно з Таблиці 4, всі штучні змінні вийшли з базису, штучна цільова функція обнулилася - значить, перший етап двохетапного симплекс-метода...
-
ПЕРШИЙ ЕТАП ДВОХЕТАПНОГО СИМПЛЕКС-МЕТОДА - Рішення оптимізаційної задачі лінійного програмування
Отже, на першому етапі двохетапного методу відшукується початкове допустиме рішення. Для цього виконаємо наступні дії: Будуємо штучну цільову функцію -...
-
ПРИВЕДЕННЯ ЗАВДАННЯ ДО СТАНДАРТНОЇ ФОРМИ Для приведення даного завдання до стандартної форми необхідно лише перейти від обмежень - нерівностей до...
-
ПОБУДОВА ШТУЧНОГО БАЗИСУ - Рішення оптимізаційної задачі лінійного програмування
Методи штучного базису призначені для побудови початкового базису (тобто для отримання початкового рішення) у випадках, коли його побудова безпосередньо...
-
Варіант 80. У цеху є токарний верстат і верстат-автомат. Цех випускає деталі 1,2 і 3 в комплекті: на кожну деталь 1 - по 2 деталі 2 і 3. Годинна...
-
Математична постановка задачі Для того, щоб розіграш лоту здійснився, необхідна одна з двох умов: кількість можливих білетів у розіграшу лоту набралась,...
-
Для третьего способа мне понадобился способ под названием "Стемминг". Данное понятие очень популярно во всемирной паутине, так как оно применяется в...
-
В качестве доступного инструментария были рассмотрены две открытые кроссплатформенные библиотеки для разработки C++ приложений WxWidgets и Boost ,...
-
Для того, чтобы разработать оптимальный метод интеграции сторонних систем в существующую ИТ-инфраструктуру систем компании, требуется точно поставить...
-
Табличный процессор Excel фирмы Microsoft предназначен для ввода, хранения, обработки и выдачи больших объемов, данных в виде, удобном для анализа и...
-
1. Провести обзор методов автоматического построения профиля нормального поведения веб-приложения. 2. Сформулировать требования к методу, провести...
-
Загальні відомості Теплова електростанція (ТЕС) - це електростанція, що виробляє електричну енергію в результаті перетворення теплової енергії, що...
-
Транспортная задача оптимальность Поставим в соответствие поставщикам потенциалы Ui, , а потребителям - Vj, . В оптимальном плане для всех базисных...
-
Відомі два підходи до організації інформаційних масивів: файлова організація та організація у вигляді бази даних. Файлова організація передбачає...
-
Вступ, Етапи розв'язання статистичної задачі - Статистичне оброблення медичної інформації
Статистичний програма excel програма Мета: Ознайомити студентів з прикладними програмами Microsoft Office, з медичними документами, їх створенням та...
-
VC++ - мова і середовище програмування, що відноситься до класу RAD - (Rapid Application Development _ "Засіб швидкої розробки додатків") засобів CASE -...
-
Транспортная задача - Линейное программирование
Одна из наиболее распространенных задач математического программирования -- транспортная задача. В общем виде ее можно представить так: требуется найти...
-
Шестой метод - построение суффиксных деревьев. Среди большого количества методов анализа текста метод аннотированного суффиксного дерева выделяется тем,...
-
Взаимодействие задач с PVM - Администрирование параллельных процессов
В системе PVM каждая задача, запущенная на некотором процессоре, идентифицируется целым числом, которое называется идентификатором задачи (TID) и по...
-
Базы данных (БД) составляют в настоящее время основу компьютерного обеспечения информационных процессов, входящих практически во все сферы человеческой...
-
Вступ - Розробка гри в С# "Корови та бики"
Ціль курсової роботи є програмна реалізація логічної гри "Корови і бики". Програмування - процес і мистецтво створення комп'ютерних программ за допомогою...
-
Постановка задачи Составить инфологическую модель базы данных (БД), необходимой для предоставления информации программе расчета предельно-допустимых...
-
Заключение - Сравнение моделей представления слов в задаче очистки текста от обесцененной лексики
В данной работе проводится сравнение эффективности 6 методов поиска по однословному запросу. В качестве запроса выступает слов из стоп-листа - списка...
-
Метод конечных элементов (МКЭ) жесткости возник в аэрокосмической отрасли. Исследователи рассматривали различные подходы к анализу сложных частей...
-
В рамках данной работы по разработке схемотехнического метода повышения сбоеустойивости ПЛИС поставлены следующие задачи: 1. Создание сбоеустойчивой...
-
МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ - Анализ потерь рабочего времени сорудников предприятия
Постановка задачи Имеется смета на выполнение проекта монтажа охранной сигнализации, в которой расписаны этапы выполнения работ, подбор специалистов на...
-
Постановка задачи Необходимо разработать программу для поиска автобусных маршрутов. В качестве среды разработки должна использоваться Delphi 7. В...
-
Постановка задачі - Розробка гри в С# "Корови та бики"
Етап 1 . Визначення цілей програми . На даному етапі творець програми повинен: - чітко визначити, які функції повинна виконувати програма; - обміркувати...
-
Выполнения проекта монтажа охранной сигнализации состоит из множества операций, которые складываются в этапы работ проекта. Схематично структура этапов...
-
Широкое распространение в операционной системе Windows имеет множество стандартных программ обеспечивающих работу устройств компьютера и служащих для...
-
Операционная система Windows XP была разработана и выпущена на смену операционной системе DOS фирмой Microsoft XP в 2002 году. Именно поэтому она и...
-
Задачи файловой системы - Операционная система Windows
Основные функции любой файловой системы нацелены на решение Следующих задач:именование файлов;программный интерфейс работы с файлами для...
-
Постановка задачи на разработку программного обеспечения Для того чтобы предлагаемая схема была интегрирована в САПР, который не имеет функции интеграции...
-
Постановка задачи, Подход к реализации - Обьекто-ориентированное программирование
Создать класс Triangle для представления треугольника. Поля класса - длины сторон. Требуется реализовать операции: вычисления углов треугольника,...
-
Програмна реалізація алгоритмів лінійної структури Алгоритм (латинізов. Algorithmi за араб. ім'ям узб. математека аль-Хороезмі) -- набір інструкцій, які...
-
До цього моменту було розглянуто одновимірні масиви, якими не завжди можна обмежитися. Припустимо, необхідно обробити деякі дані з таблиці. У таблиці є...
-
Постановка задачи., Практическая часть. Ход работы - Автоматизация регрессионного тестирования
В проекте несколько раз в течение жизненного цикла тестируемого продукта проводится ручное регрессионное тестирование такой функциональности, как...
-
Склад і характеристика проектів IDE MS Visual Studio C++ Будь-яка програма, що створюється в середовищі Visual Studio C++ завжди оформляється як окремий...
ВВЕДЕННЯ - Рішення оптимізаційної задачі лінійного програмування