Оптимізація ресурсів за допомогою лінійного програмування

  • Почніть
  • PHPSimplex
    • Довідка PHPSimplex
  • Оперативне розслідування
    • Історія
    • Реальні справи
  • Теорія
    • Моделювання проблем
    • Симплексний метод
    • Двофазний метод
    • Графічний метод
  • Приклади
    • Моделювання проблем
      • Проблема дієти
      • Проблема транспорту військ
      • Проблема вантажного транспорту
      • Проблема плодових дерев
      • Кадрове питання
      • Мінімальна проблема шляху
      • Проблема з розташуванням
      • Проблема інвестицій в акції
    • Симплексний метод
    • Графічний метод
  • Джордж Б. Данциг
    • Біографія
    • Інтерв’ю
  • Ідіома
    • Іспанська
    • Англійська
    • Франсуа
    • Португальська

Історія досліджень операцій

Протягом історії загальноприйнятим є тісна співпраця між науковцями та військовими, щоб диктувати оптимальне рішення в бою та намагатися добитися перемоги. Ось чому багато експертів у цій галузі вважають початок оперативних досліджень у 3 столітті до нашої ери, під час Другої Пунічної війни, аналізом та рішенням, запропонованим Архімедом для оборони міста Сіракузи, обложеного римлянами. Серед його винаходів були катапульта та система дзеркал, за допомогою яких він підпалював ворожі судна, фокусуючи їх сонячними променями.

У 1503 році Леонардо да Вінчі брав участь в якості інженера у війні проти Пізи, оскільки він знав техніки для бомбардування, будівництва кораблів, бронетехніки, гармат, катапульт та інших військових машин.

оперативні

Інший попередник використання операційних досліджень відбувається під час Першої світової війни в Англії, при математичному дослідженні Фредеріка Вільяма Ланчестера про балістичну силу протиборчих сил. Він також розробив на основі системи диференціальних рівнянь Квадратичний закон бою Ланчестера, за допомогою якого можна було визначити результат військової битви на основі відносної чисельної сили та відносної вогневої сили учасників бойових дій.

Томас Альва Едісон також використовував дослідження операцій, сприяючи протичовновій війні, розробляючи методи, що дозволяють кораблям уникати та знищувати ворожі підводні човни, забезпечуючи їм протиторпедний захист.

З математичної точки зору, у XVII-XVIII століттях Ньютон, Лейбніц, Бернуллі та Лагранж працювали над отриманням умовних максимумів та мінімумів певних функцій. Французький математик Жан Батист-Жозеф Фур'є окреслив методи поточного лінійного програмування. А в останні роки 18 століття Гаспар Монж створив прецеденти Графічного методу завдяки своєму розвитку Описової геометрії.

Наприкінці 19 століття Фредерік Уінслоу Тейлор провів дослідження, яке максимізувало продуктивність шахтарів, в ході якого було встановлено, що єдиною дійсно значущою змінною є загальна вага лопати та її навантаження. Таким чином, леза були розроблені відповідно до різних типів матеріалів, з якими вони мали бути використані.

Янош фон Нойман опублікував свою працю "Теорія ігор" в 1928 році, яка забезпечила математичні основи лінійного програмування. Пізніше, в 1947 році, він передбачив схожість між проблемами лінійного програмування та розробленою ним теорією матриць.

У 1939 р. Російський математик Леонід Віталійович Канторович та голландський Тілінг Чарльз Купманс розробили математичну теорію під назвою "Лінійне програмування", за що їм була присуджена Нобелівська премія з економіки.

У 1945 р. Джордж Джозеф Стіглер підняв проблему дієти, як результат турботи американської армії про забезпечення основних потреб у харчуванні своїх військ за мінімально можливих витрат. Метою було визначити кількість, серед 77 різних продуктів харчування, яку повинен їсти середньостатистичний чоловік вагою приблизно 70 кг щодня, щоб мінімальні потреби в поживних речовинах були рівними потребам, рекомендованим Північноамериканською національною дослідницькою радою. Проблема була вирішена вручну за допомогою евристичного методу, за допомогою якого було досліджено 510 різних можливостей поєднання харчових продуктів, і рішення яких відрізнялося лише на кілька центів від рішення, наданого роками пізніше методом Сімплекс.

Протягом 1941 та 1942 років Канторович та Купманс вперше самостійно вивчали транспортну проблему, ця проблема була відома як проблема Купманса-Канторовича. Для їх розв’язання вони використовували геометричні методи, пов’язані з теорією опуклості Мінковського.

Вважається, що Чарльз Беббідж є батьком Operations Research, завдяки його дослідженням витрат на транспортування та сортування пошти, проведених в Uniform Penny Post в Англії в 1840 р.

Однак не вважається, що нова наука під назвою «Дослідження операцій» або «Дослідження операцій» народилася до Другої світової війни, під час битви за Британію. Люфтваффе, німецькі ВПС, піддавали цю країну сильним переслідуванням, використовуючи зменшену британську пропускну спроможність через політику роззброєння, хоча і мали досвід бойових дій. Британський уряд, шукаючи певного методу захисту своєї країни, закликав вчених з різних дисциплін, щоб спробувати вирішити проблему та максимально використати у своєму розпорядженні нещодавно винайдені радари. Завдяки їх роботі щодо визначення оптимального розташування антен та найкращого розподілу сигналів, їм вдалося подвоїти ефективність системи ППО та запобігти потраплянню острова в руки нацистської Німеччини.

Оцінивши масштаби цієї нової дисципліни, Англія створила інші групи такого ж характеру для отримання оптимальних результатів у змаганні. Таким же чином, США (США), приєднавшись до війни в 1942 р., Почали застосовувати методи досліджень операцій у військовому порядку, а кілька років потому, в 1947 р., Створили робочу групу, спрямовану на вдосконалення процесів планування до великих масштабів: Проект SCOOP (Наукове обчислення оптимальних програм). У цій групі працював Джордж Бернард Данциг, який розробив алгоритм методу Сімплекс у 1947 році.

Під час холодної війни колишній Радянський Союз (СРСР), виключений із плану Маршалла, хотів контролювати наземні комунікації, включаючи річкові шляхи, з Берліна. Щоб уникнути капітуляції міста та подання його частиною німецької комуністичної зони, Англія та США вирішили забезпечити місто або конвойними конвоями (що може призвести до нових конфронтацій), або повітряним транспортом, зламавшись або будь-який випадок ухилення від Берлінської блокади. Цей другий варіант був обраний, запустивши Luftbrücke (авіаліфт) 25 червня 1948 р. Це була ще одна проблема, в якій брала участь група SCOOP, у грудні того ж року можна було поставляти 4500 тонн на день, а після експлуатації У ході дослідницьких досліджень постачання було оптимізовано до досягнення 8000 або 9000 тонн на день у березні 1949 року. Цей показник був таким самим, як і той, який був би перевезений наземним транспортом, тому Ради вирішили зняти блокаду 12 травня 1949 року.

Після Другої світової війни було визнано доцільним організувати ресурси Сполучених Штатів (енергія, зброя та всі види поставок) за допомогою моделей оптимізації, вирішених за допомогою лінійного програмування.

Одночасно з доктриною досліджень операцій були також розроблені комп'ютерні методи, що дозволило значно скоротити час для вирішення проблем.

Перший результат цих методів був отриманий в 1952 р. За допомогою комп’ютера SEAC від Національного бюро стандартів для вирішення проблеми. Успіх у часі вирішення був настільки обнадійливим, що його відразу застосували для вирішення усіх видів військових проблем, таких як управління грошовими коштами на матеріально-технічне забезпечення та озброєння, визначення оптимальної висоти, на якій повинен летіти літак для визначення підводних човнів противника, і навіть глибини на які потрібно було направити звинувачення, щоб дістатися до підводних човнів противника таким чином, що спричинило найбільшу кількість жертв. Все це призвело до п’ятикратного збільшення ефективності повітряних сил.

Протягом 50-х та 60-х років інтерес та розвиток досліджень операцій зростав завдяки його застосуванню в галузі комерції та промисловості. Прикладом цього є проблема розрахунку оптимального плану транспортування будівельного піску до будівельних майданчиків у місті Москва, де було 10 пунктів початку та 230 пунктів призначення. Для її вирішення в червні 1958 р. Був використаний комп’ютер Strena, який після 10 днів розрахунків створив рішення, яке призвело до зменшення витрат на 11% порівняно з початковими передбачуваними витратами.

Раніше ці проблеми порушувались у дисципліні, відомій як Бізнес-дослідження або Аналіз бізнесу, яка не мала таких ефективних методів, як ті, що були розроблені під час Другої світової війни (наприклад, метод Сімплекс). Невоєнні програми оперативних досліджень поширюються на всі сфери, з проблемами: від продовольства, худоби, розподілу полів у сільському господарстві, транспортування товарів, розміщення, розподілу персоналу, проблем у мережі, черг, графіків тощо.

Як приклад, можна спостерігати наступні реальні випадки використання операційних досліджень та зазначені переваги.