МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Учебное пособие
Составители:
А.Я. Аснина,
Н.Г. Аснина
Издательско-полиграфический центр
Воронежского государственного университета
2011
Стр.1
Содержание
Глава 1. Общая постановка задачи линейного программирования.
Графическое решение задач линейного программирования.
Каноническая форма. Базисное решение ................................................................4
1.1. Основные определения ........................................................................................4
1.2. Способы записи задачи линейного программирования ...................................5
1.3. Представление экономических задач в виде ЗЛП ............................................6
1.3.1. Задача формирования плана предприятия ...................................................6
1.3.2. Задача о формировании рациона ..................................................................7
1.4. Графический метод решения задачи линейного программирования .............8
Лабораторная работа № 1 ....................................................................................... 13
1.5. Каноническая форма задачи линейного программирования.
Приведение к канонической форме ....................................................................... 14
1.6. Базисное решение ЗЛП .................................................................................... 17
1.7. Перестроение базисного решения ЗЛП .......................................................... 18
Лабораторная работа № 2 ................................................................................................. 21
Глава 2. Симплекс-метод ........................................................................................ 21
2.1. Основная теорема линейного программирования ......................................... 21
2.2. Алгоритм симплекс-метода ............................................................................. 22
Лабораторная работа № 3 ................................................................................................. 24
2.3. Симплекс-метод с искусственным базисом ................................................... 24
Лабораторная работа № 4 ....................................................................................... 30
Глава 3. Двойственность в задачах линейного программирования .............. 30
3.1. Основные понятия и определения ................................................................... 30
3.2. Леммы и теоремы двойственности ................................................................. 36
3.3. Экономический смысл двойственной задачи ................................................. 40
Лабораторная работа № 5 ....................................................................................... 41
Глава 4. Транспортная задача ................................................................................ 41
4.1. Математическая модель транспортной задачи .............................................. 41
4.2. Решение транспортной задачи. Метод потенциалов ..................................... 45
4.3. Транспортные задачи, имеющие усложнения в постановке ........................ 54
Лабораторная работа № 6 ....................................................................................... 60
Список литературы .................................................................................................. 62
3
Стр.3
x ≥ 0, ( 1, ),k1
xi ≥ 0, ( 1,
1
j
i
j =
≤ ≤ ≤
=
1
2
f x( ) →= xc
T
k k n
k
2 ),
max.
(min)
1.3. Представление экономических задач в виде ЗЛП
Многие экономические задачи сводятся к задачам линейного программирования.
Вербальной
моделью называется описание на языке предметной области
основных свойств и зависимостей исследуемого объекта или проекта.
Математическая модель – это описание с помощью математических символов
основных свойств и зависимостей, описанных вербальной моделью.
1.3.1. Задача формирования плана предприятия
Вербальная модель
Имеем предприятие, которое может выпускать n различных видов изделий.
Для выпуска данных изделий необходимо m различных видов ресурсов.
Пусть bi – лимит i-го ресурса на предприятии, aij – расход i-го ресурса
на единицу j-го вида продукции, cj – прибыль от реализации одной единицы
j-го вида продукции. Требуется сформировать план предприятия, обеспеченный
всеми ресурсами и дающий максимально возможную прибыль.
Математическая модель
Формируем план:
xj ≥ 0,
ограничение
∑ ≤
=
n
j 1
ij
j
j =1, n,
где xj – количество продукции j-го вида в плане, тогда весь план задается
вектором x.
Так как план должен быть обеспечен всеми ресурсами, то получаем
a x b i m. Здесь левая часть неравенства описывает
, 1,
=
количество ресурсов, которое будет израсходовано для выполнения плана x.
При этом при выполнении плана х будет получена прибыль ∑
j 1
=
n
∑ ≤ i ,
j=1
n
ij
j
6
Окончательный вид математической модели будет следующий:
a x b i m
=1,
,
c x .
j
j
Стр.6
xj ≥ 0,
f x =∑c x → max
( )
или
Ax b≤ ,
x ≥ 0,
f x( ) →= xc
T
???
max .
Задание для самостоятельной работы
Фабрика выпускает продукцию двух видов: П1 и П2. Продукция
обоих видов поступает в оптовую продажу. Для производства этой
продукции используются три исходных продукта: А, В, С. Максимально
возможные суточные запасы этих продуктов, расходы продуктов
(сырья) А, В, С на 1 тыс. изделий, а также оптовая цена Z 1 тыс. шт.
изделий П1 и П2 приведены в таблице.
Исходный
продукт
А
В
С
Расход исходных продуктов на 1
тыс. изделий
П1
1
2
1
П2
2
1
0,8
Максимально
возможный запас
(Т)
6
8
5
Z 3 2
Какое количество изделий (в тыс. шт.) должна производить
фабрика, чтобы доход от реализации продукции был максимальным?
Запишите математическую модель этой задачи.
1.3.2. Задача о формировании рациона
Вербальная модель
Для составления дневного рациона имеем в наличии n различных
кормов. Для получения сбалансированного рациона (белки, витамины, микроэлементы
и др.) необходимо, чтобы в него входило m различных ингредиентов,
причем каждый i-й ингредиент должен входить в количестве не
меньше bi ( mi =1,
), aij – количество i-го ингредиента в одной единице j-го
вида корма, cj – стоимость одной единицы j-го корма.
Требуется сформировать ежедневный рацион так, чтобы он был
обеспечен всеми необходимыми ингредиентами и имел минимальную
стоимость.
j 1
=
n
j
j
j =1,n,
7
Стр.7
Математическая модель
⎛
Введем вектор
x L
2
=
⎜
⎜
⎜
⎜
⎜
x
x
1 ⎞
⎟
⎟
⎟
⎝ xn ⎠
⎟
⎟
рационе.
По аналогии с предыдущей задачей математическая модель задачи
формирования рациона будет иметь вид
A bx ≥ ,
x ≥ 0,
f x( ) →= xc
T
max
(1.4)
(1.5)
(1.6)
Заметим, что полученная математическая модель недостаточно адекватно
отражает искомую цель, т.к. в вербальной модели описаны не все необходимые
зависимости.
В самом деле, если предположить, что среди выбранных кормов
присутствует, например, прошлогодняя солома, стоимость которой
равна нулю, а все имеющиеся ингредиенты присутствуют в ней в исчезающее
малых количествах, то при решении задачи может получиться,
что ежедневный рацион должен состоять только из прошлогодней соломы
и составлять, например, пятнадцать тонн, что, разумеется, невозможно.
Отсюда
следует, что ограничение (1.5) необходимо заменить на
0 ≤ x D≤ , где D – вектор верхних границ переменных xj.
???
Задание для самостоятельной работы
Если (1.4)–(1.5) оставить в исходном виде, то какие еще «неприятности»
мы можем получить в оптимальном плане?
1.4. Графический метод решения задачи линейного
программирования
Если задача линейного программирования имеет две переменные: x1 и
x2, то ее можно решить графически.
Решение задачи происходит в два этапа.
На первом этапе необходимо на плоскости изобразить допустимое
множество, а на втором найти оптимальную точку, если она существует, в
противном случае убедиться в неразрешимости задачи.
8
– рацион, где xj – количество j-го вида корма в
Стр.8