Введение. Любая наука возникает в результате возрастающего интереса к определенному классу задач, и развития методов и средств с помощью которых можно решить эти

Любая наука возникает в результате возрастающего интереса к определенному классу задач, и развития методов и средств с помощью которых можно решить эти задачи. ИСО не является исключением.

Название дисциплины «исследование операций» заимствовано из западной литературы и появилось в 1940г..

Первые формальные разработки по ИСО были начаты в Англии во время Второй мировой войны и применялись они для планирования боевых операций, отсюда и возникло название дисциплины.

Команда британских ученых сформулировала и решила задачи эффективной доставки военного снаряжения на фронт.

После окончания войны методы ИСО были перенесены в гражданскую сферу для повышения эффективности и продуктивности экономической и производственной деятельности.

Быстрое развитие дисциплина получает с 1962г. Это связывают с возросшей конкуренцией в коммерческой сфере и быстрым развитием вычислительной техники.

Несмотря на то, что сегодня термин не совсем точно отражает суть предмета, он сохранился до нашего времени.

Линейное программирование (ЛП) – один из первых и подробно изученных разделов математического программирования. Именно с раздела линейное программирование и начало развиваться математическое программирование.

(Линейное программирование применяется в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.)

Термин «линейное программирование» возник в результате неточного перевода с английского «linear programming». Одно из значений слова «programming» – составление планов, планирование. Следовательно, правильным переводом английского «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины.

Первые работы по линейному программированию вышли в Ленинградском госуд. Университете. Автором был Канторович Леонид Витальевич (1912-1986).

Родился в 1912г.в Санкт-Петербурге. В 14 лет поступил в Ленинградский университет на математическое отделение и окончив его в 1930г, остается на преподавательской работе. Канторович занимается исследованиями на кафедре математики, и в 1935г (ему 23 года) ему присваивается ученая степень доктора физико-математических наук.

В 1938 году, Канторович привлекается в качестве консультанта на фанерную фабрику и решает задачу эффективного использования оборудования.

Канторович понял, что решение задачи сводится к максимизации линейной функции многих переменных при наличии ограничений в форме равенств и неравенств.

Так впервые была сформулирована задача производственного планирования, как задача ЛП и разработан метод для ее решения. Результаты его труда были опубликованы в 1939 г. в работе «Математические методы организации и планирования производства». К сожалению в это время эти результаты не были должным образом оценены.

Признание пришло позже, в 60-е годы. В1975г. Канторович вместе с американским экономистом Тьяллингом Купмансом(1910-1985) был удостоен Нобелевской премии по экономике «за вклад в теорию оптимального распределения ресурсов».

На Западе отцом-основателем этого направления считают американского математика Джорджа Данцига (1914-2005).

Во время 2-ой Мировой войны Данциг работал в командовании военно-воздушных сил и занимался программированием поставок военной техники. Термин «программирование» был сугубо военным и означал составление планов поставок.

Данциг предложил использовать линейную модель, а в конце 40-х годов изобрел универсальный численный метод решения, который наз. Симплексный метод.

Большой вклад в развитие оптимизационных методов внесли: Канторович Л.В., Немчинов В.С., Новожилов В.В. В 1965 г. Они были удостоены Ленинской премии за разработку и внедрение оптимизирующих методов.

Значительный вклад в теорию и методы линейного программирования внесли С. Гасс, А. Таккер, Р. Гомори, Г. Кун, Т. Саати, Г. Вагнер, Д.Б. Юдин, Е.Г. Гольштейн и др.

Задача производственного планирования (или общая Задача ЛП). Различные формы записи ее модели.

Параметр управления, – количество выпускаемой продукции j -того вида.

Координатная форма записи

Целевая функция, экономический смысл – максимизировать доход, получаемый от выпуска продукции:

(1)

Структурные ограничения – отражают требование не перерасходовать запасы каждого производственного фактора

– – – – – – – – – – – – – – (2)

– – – – – – – – – – – – – –

Условие неотрицательности параметра управления:

(3)

– технологические коэффициенты, произвольные числа, встречаются в ограничениях произвольное число раз.

С_j,b_i – заданные постоянные величины, а m>n.

Запись с помощью знаков суммирования

– max

Векторно-матричная форма записи задачи

Если воспользоваться матричными обозначениями, то задачу ЛП можно записать компактно. Обозначим С=(с₁,с₂, …, с_j, …, с_n) – вектор-строка стоимостей единиц продукции.

x₁ b₁

x₂ b₂

… …

X= x_j; – вектор-столбец переменных; B = b_i – вектор-столбец;

… … ограничений

x_n b_m

a₁₁ a₁₂ … a_1j a_1n

a₂₁ a₂₂ … a_2j a_2n

A= – – – – – – –матрица условий,

a_i1 a_i2 … a_ij a_in (матрица технологических коэффициентов)

– – – – – –

a_m1 a_m2 … a_mj a_mn

0= … нулевой вектор– столбец

Тогда задача (1)-(3) запишется:

Z= CX – max (1’)

AX ≤ B (2’)

X ≥ 0 (3’)