История математического программирования. Велись разработки ПО для реализации симплекс – метода для решения задачи ЛП (И.В

Велись разработки ПО для реализации симплекс – метода для решения задачи ЛП (И.В. Романовский, А.А. Станевичус, и др, доцент УГАТУ А.П. Мартынов).

Появились численные методы решения специальных классов задач ЛП:

транспортная задача, методы декомпозиции, итеративные методы ЛП.

Практическое применение ЛП для социалистической экономики.

9. 70-80-е годы

Вводится новое понятие сложности оптимизационной задачи: установлены нижние границы для различных классов оптимизационных задач (Юдин Д.Б. и др.).

Было установлено: если метод имеет сложность, совпадающую с нижней границей, то он оптимален, т.е. не существует методов, которые решают все задачи класса быстрее (в отношении порядка).

Построен итеративный метод решения задачи ЛП, для которой была доказана полиномиальная сходимость (Хачиян Л.Г.)

Литература

1.Канторович Л.В. Математические методы организации и планирования производства. Л.: Изд-во Ленинградский университет, 1939, 64с.

2. Юдин Д.Б., Гольштейн Е.Г. Задачи и методы линейного программирования. М.: Советское радио. 1964, 491с.

3. Карманов В.Г. Математическое программирование. М.: Наука, 1975, 272с.

4. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. Новосибирск: Изд-во «Наука», Сибирское отделение, 1987, 272с.

5. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение АСУ. М.: Машиностроение, 1984,174с.

6. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя-упаковки геометрических объектов. Уфа: УГАТУ, 1998, 217с.

7. Мухачева Э.А., Валеева А.Ф., Картак В.М. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума. Москва: Изд-во МАИ, 2004, 192с.