Методы оптимальных решений

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ
АГРАРНЫЙ УНИВЕРСИТЕТ
ЭКОНОМИЧЕСКИЙ ФАКУЛЬТЕТ

В. Г. Бардаков, О. В. Мамонов

МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Учебное пособие

Новосибирск 2013

УДК 512(075.8)
ББК В14я73-2
Б 247

Кафедра автоматизированной обработки информации

Авторы-составители:
д-р физ.-мат. наук, проф. В. Г. Бардаков
доц. О. В. Мамонов

Рецензенты:
канд. экон. наук, проф. Г. М. Дмитриева, НГАУ
д-р физ.-мат. наук, доц. М. В. Нещадим, Институт математики СО РАН

Э40 Методы оптимальных решений: учеб. пособие / Новосиб. гос. аграр. ун-т. Эконом. фак.; авт.-сост.: В. Г. Бардаков,
О. В. Мамонов.–Новосибирск.: Изд-во НГАУ, 2013.–230 c.: 12
ил.

ISBN 978-5-4437-0061-8

Учебное пособие предназначено для студентов вузов всех
форм обучения по направлению подготовки 080100.62 – Экономика, изучающих методы оптимизации в рамках курса «Методы оптимальных решений». В пособие рассматриваются основные понятия теории оптимизации. В частности, способы нахождения экстремума функции одной и нескольких переменных, задача линейного программирования, симплекс-метод,
транспортная задача.
Представленный в учебном пособие материал охватывает
основную часть учебной дисциплины «Методы оптимальных
решений» и ориентирован на реализацию общекультурных и
профессиональных компетенций в процессе профессионально
направленного обучения методам оптимизации.
c⃝Новосибирский государственный
аграрный университет, 2013
c⃝Бардаков В. Г., Мамонов О. В., 2013

Предисловие

Настоящее учебное пособие возникло из курса
лекций, читавшегося авторами на экономическом
факультете НГАУ. В пособие вошли такие разделы: методы оптимизации, линейное программирование, симплек-метод, транспортная задача.
Пособие состоит из 4 глав, разбитых на 13 параграфов. В конце каждого раздела приведены
упражнения для самостоятельного решения.
При изучении данного пособия требуется знание основ математического анализа и линейной
алгебры, изучаемых на первом курсе. Предполагается, что читатель знаком с элементарными приемами дифференцирования, имеет навыки работы
с матрицами (умножение, транспонирование, нахождение обратной), знаком с уравнениями прямой и плоскости, умеет по уравнению построить
прямую на плоскости, а также построить множество решений линейного неравенства с двумя неизвестными.
В первой главе рассматривается задача о нахождении наибольшего (наименьшего) значения
функции одной переменной на отрезке, формулируется общая задача оптимизации, рассматривается метод Лагранжа решения задачи оптими

Предисловие

зации без ограничений, а также с ограничениями, имеющими вид равенств и неравенств. Для
каждого вида задач разбираются соответствующие примеры.
Во второй главе рассматривается задача линейного программирования, формулируются некоторые конкретные задачи, часто возникающие на
практике. Изучаются различные виды задач линейного программирования и связи между ними.
Описывается множество допустимых планов задачи линейного программирования, излагается графический способ решения задач линейного программирования.
Третья глава посвящена симплек-методу. Вначале приводится метод решения систем линейных
уравнений при помощи симплекс-таблиц, затем –
нахождение неотрицательных решений систем линейных неравенств и, наконец, нахождение допустимого и оптимального планов задачи линейного
программирования. Последний параграф третьей
главы посвящен теории двойственности в линейном программировании.
В четвертой главе разбирается решение транспортной задачи. В частности, дается общая постановка, излагаются методы построения начального
опорного плана, а затем дается метод потенциалов, позволяющий найти решение транспортной

задачи.
В конце книги приведены варианты типовых
заданий, которые студенты должны решить и защитить в течение семестра. Также приведены теоретические вопросы и вопросы из экзаменационных билетов.
Благодарим всех, кто принимал участие в подготовке этих лекций: Г. М. Дмитриеву, внимательно прочитавшую рукопись и внесшую ряд полезных замечаний и предложений; О. А. Кутненко
и М. В. Нещадима, беседы с которыми помогли
улучшить текст; О. В. Брюханова, разработавшего дизайн обложки и оказавшего помощь в подготовке оригинал-макета; М. В. Камленкову, нарисовавшую рисунки; Н. Л. Абашееву и Н. Б. Аюпову, помогавших освоить премудрости LaTeXа.
Также благодарим студентов, прослушавших этот
курс и внесших в него ряд полезных замечаний.

Обозначения

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

A = {a1, a2, . . .}

обозначается множество A, состоящее из элементов a1, a2, . . . Запись a ∈ A означает, что элемент a принадлежит множеству A; запись a ̸∈ A
означает, что a не принадлежит множеству A. Если B является подмножеством множества A, то
символически это записывается так: B ⊆ A. Пустое множество будем обозначать символом ∅. Если A = {a1, a2, . . . , an} – конечное множество, то
символом |A| = n обозначается число элементов
множества A.
Для числовых множеств будем использовать
следующие обозначения:

N = {1, 2, . . .}

– множество натуральных чисел;

Z = {0, ±1, ±2, . . .}

– множество целых чисел;

Q =
{p

q | p ∈ Z, q ∈ N
}

– множество рациональных чисел; символом R
будем обозначать множество вещественных чисел,
которое можно представлять как множество точек
на вещественной оси;

R+ = {r ∈ R | r > 0}

– множество положительных вещественных чисел;
R≥0 = {r ∈ R | r ≥ 0}

– множество неотрицательных вещественных чисел;
C = {a + ib | a, b ∈ R, i2 = −1}

– множество комплексныных чисел .
Если A1, A2, . . . , An – непустые множества, то
их декартовым произведением A1 ×A2 ×. . .×An
называется множество упорядоченных n-ок:

A1 × A2 × . . . × An = {(a1, a2, . . . , an) | ai ∈ Ai}.

В частности, если A1 = A2 = . . . = An = A, то
декартово произведение A1 × A2 × . . . × An называется n-й декартовой степенью множества A и
обозначается An.
Отображение множества A в множество B будем обозначать либо

φ : A −→ B, либо A
φ
−→ B.

Обозначения

Если a ∈ A, то образ элемента a при отображении
φ обозначается либо φ(a), либо aφ.

Введение

Один старый французский математик сказал:
«Математическую теорию только тогда можно
считать совершенной, когда ты... берешься
изложить ее содержание первому встречному».
Д. Гильберт

Задача оптимизации – одна из древнейших задач, возникших перед человечеством. Еще в древности людям приходилось решать, как оптимально использовать землю при посеве различных
сельскохозяйственных культур, как из шкуры животного выкроить одежду и т. д. Особенное значение задачи оптимизации приобретают в настоящее время, что связано с важностью эффективного использования природных богатств, людских
ресурсов, материальных и финансовых средств.
По своему содержанию задачи оптимизации
очень разнообразны. Они могут быть связаны с
разработкой различных технических устройств, с
распределением ограниченных ресурсов и планированием работы предприятий, а также с решением проблем, возникающих в повседневной жизни. Часто человек сталкивается с ситуацией, когда из нескольких вариантов решения ему необходимо выбрать один. Чем он руководствуется при

Введение

этом? Что означает «оптимальное решение»? В
жизни бывает трудно ответить на последний вопрос: «Лишь спустя годы, начинаешь понимать
какие мосты надо было сжечь, а какие перейти».
Иногда же ситуация более простая.

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