Оптимизиране на ресурсите с линейно програмиране

  • Започнете
  • PHPSimplex
    • Помощ за PHPSimplex
  • Оперативно разследване
    • История
    • Реални случаи
  • Теория
    • Моделиране на проблеми
    • Симплекс метод
    • Двуфазен метод
    • Графичен метод
  • Примери
    • Моделиране на проблеми
      • Проблем с диетата
      • Проблем с транспорта на войските
      • Проблем с товарния транспорт
      • Проблем с плодовото дърво
      • Въпрос с персонала
      • Минимален проблем с пътя
      • Проблем с местоположението
      • Проблем с инвестициите в акции
    • Симплекс метод
    • Графичен метод
  • Джордж Б. Данциг
    • Биография
    • Интервю
  • Идиом
    • Испански
    • Английски
    • Français
    • Португалски

История на оперативните изследвания

През цялата история е обичайно да се намери тясно сътрудничество между учените и военните, за да се диктува оптималното решение в битката и да се опита да се постигне победа. Ето защо много експерти в областта смятат началото на оперативните изследвания през III век пр. Н. Е., По време на Втората пуническа война, с анализа и решението, които Архимед предлага за отбраната на град Сиракуза, обсаден от римляните. Сред неговите изобретения са катапултът и система от огледала, с които той подпалва вражески кораби, като ги фокусира със слънчевите лъчи.

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

Operations Research

По време на Първата световна война в Англия се случва още един предшественик на използването на Operations Research с математическото изследване на Фредерик Уилям Ланчестър върху балистичната сила на противоположните сили. Той също така разработи, въз основа на система от диференциални уравнения, Квадратичния закон за борбата на Ланчестър, с който беше възможно да се определи резултатът от военна битка въз основа на относителната числена сила и относителната огнева мощ на бойците.

Томас Алва Едисон също се възползва от Operations Research, допринасяйки за борба с подводниците, разработвайки техники, така че корабите да могат да избягват и унищожават вражеските подводници, осигурявайки им анти-торпедна защита.

От математическа гледна точка, през седемнадесети и осемнадесети век, Нютон, Лайбниц, Бернули и Лагранж работят за получаване на условни максимуми и минимуми на определени функции. Френският математик Жан Батист-Жозеф Фурие очерта методите на текущото линейно програмиране. И през последните години на 18-ти век, Гаспар Монж създава прецедентите на Графичния метод благодарение на своето развитие на Дескриптивна геометрия.

В края на 19-ти век Фредерик Уинслоу Тейлър провежда проучване, което максимизира производителността на миньорите, в което се определя, че единствената наистина значима променлива е комбинираното тегло на лопатата и нейното натоварване. По този начин остриетата са проектирани според различните видове материали, с които трябва да бъдат използвани.

Янош фон Нойман публикува своята работа „Теория на игрите“ през 1928 г., която предоставя математически основи за линейно програмиране. По-късно, през 1947 г., той си представя сходството между линейното програмиране и разработената от него теория на матриците.

През 1939 г. руският математик Леонид Виталиевич Канторович и холандският Tjalling Чарлз Купманс разработват математическата теория, наречена „Линейно програмиране“, за което са отличени с Нобелова награда за икономика.

През 1945 г. Джордж Джоузеф Стиглер повдига проблема с диетата, в резултат на загрижеността на американската армия да осигури основните хранителни изисквания за своите войски на възможно най-ниска цена. Целта беше да се определи количеството, сред 77 различни храни, което един средностатистически мъж с тегло приблизително 70 кг трябва да яде дневно, така че минималните нужди от хранителни вещества да са равни на препоръчаните от Северноамериканския национален изследователски съвет. Проблемът беше решен ръчно чрез евристичен метод, с който бяха изследвани 510 различни възможности за комбиниране на храни и чието решение се различаваше само няколко цента от решението, предоставено години по-късно чрез метода Simplex.

През годините 1941 и 1942 Канторович и Коопманс за първи път самостоятелно изучават транспортния проблем, като този тип проблеми са известни като проблем на Купманс-Канторович. За своето решение те използваха геометрични методи, които са свързани с теорията на изпъкналостта на Минковски.

Смята се, че Чарлз Бабидж е бащата на Operations Research, поради неговото изследване на разходите за транспорт и сортиране на пощата, проведено в Uniform Penny Post в Англия през 1840 г.

Въпреки това не се счита, че нова наука, наречена Operations Research или Operations Research, се ражда до Втората световна война, по време на битката за Великобритания. Луфтвафе, германските военновъздушни сили, подлагаше тази страна на силен тормоз, като се възползва от намаления британски въздушен капацитет поради политиката на разоръжаване, макар и с опит в боевете. Британското правителство, търсейки някакъв метод за защита на страната си, призова учени от различни дисциплини, за да се опитат да разрешат проблема и да се възползват максимално от новоизмислените радари, с които разполагат. Благодарение на тяхната работа за определяне на оптималното местоположение на антените и най-доброто разпределение на сигналите, те успяха да удвоят ефективността на системата за ПВО и да предотвратят попадането на острова в ръцете на нацистка Германия.

След като оцени обхвата на тази нова дисциплина, Англия създаде други групи от същото естество, за да получи оптимални резултати в състезанието. По същия начин Съединените щати (САЩ), след като се присъединиха към войната през 1942 г., започнаха да прилагат военни техники за оперативни изследвания и няколко години по-късно, през 1947 г., сформираха работна група, посветена на усъвършенстване на мащабните процеси на планиране: проектът SCOOP (Научно изчисляване на оптимални програми). В тази група работи Джордж Бернард Данциг, който през 1947 г. разработва алгоритъма на метода Simplex.

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

След Втората световна война беше счетено за подходящо да се организират ресурсите на Съединените щати (енергия, оръжия и всякакви видове доставки) чрез модели за оптимизация, решени чрез линейно програмиране.

Едновременно с доктрината за изследване на операциите бяха разработени и компютърни техники, които позволиха значително намаляване на времето за решаване на проблеми.

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

През 50-те и 60-те години интересът и развитието на Operations Research нарастват, поради прилагането му в областта на търговията и индустрията. Пример за това е проблемът с изчисляването на оптималния план за транспортиране на строителен пясък до строителни площадки в град Москва, където имаше 10 точки на начало и 230 точки на местоназначение. За да го реши, през юни 1958 г. се използва компютър Strena и след 10-дневни изчисления той създава решение, което донася 11% намаление на разходите в сравнение с първоначалните очаквани разходи.

По-рано тези проблеми бяха повдигнати в дисциплина, известна като бизнес изследвания или бизнес анализ, която не разполагаше с толкова ефективни методи като тези, разработени по време на Втората световна война (например методът Simplex). Невоенните приложения на Operational Research се разпростират във всички области, като проблемите варират от храни, добитък, разпределение на полетата в селското стопанство, транспорт на стоки, местоположение, разпределение на персонала, мрежови проблеми, опашки, графики и т.н.

Като пример могат да се наблюдават следните реални случаи на използване на оперативни изследвания и отчетените ползи.