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

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

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

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

Новосибирск 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 км в час, станция мет-
ро находится достаточно далеко от дома, ваши де-
нежные средства весьма ограничены, а наследство
от богатой бабушки еще не получено. Учитывая
все эти ограничения, вы и выбираете оптималь-
ный способ передвижения.