ОГЛАВЛЕНИЕ
Предисловие		5
Глава 1. Общее линейное программирование		7
§ 1. Постановка задачи линейного программирования		7
Вопросы		13
Упражнения		14
Ответы		16
§2. Построение математических моделей простейших
экономических задач		19
Вопросы		23
Упражнения		24
Ответы		26
§3. Графический метод решения задач линейного
программирования		27
Вопросы		37
Упражнения		38
Ответы		44
§4. Симплексный метод решения задач линейного
программирования		45
Вопросы		58
Упражнения		59
Ответы		64
§5. Двойственность в линейном программировании		66
Вопросы		75
Упражнения		76
Ответы		82
Глава 2. Транспортная задача		85
§6. Постановка транспортной задачи		85
Вопросы		98
Упражнения		99
Ответы		104

Оглавление
§ 7. Транспортная задача по критерию времени		107
Вопросы		110
Упражнения		ПО
Ответы		ПО
§8. Целочисленное программирование. Метод Гомори		111
Вопросы		116
Упражнения		116
Ответы		119
§9. Контрольные задания		119
Вариант 1		120
Вариант 2		121
Вариант 3		123
Вариант 4		124
Вариант 5		125
Список литературы		127

Предисловие
Настоящее пособие написано автором на основании многолетнего
опыта чтения лекций и проведения практических занятий по высшей
математике в МГОУ (Московском государственном открытом уни-
университете). Первые учебные пособия, в том числе учебники по ма-
математическому и линейному программированию, появились в 60-70-
е годы прошлого столетия, а начало этой новой области математики
было положено работами Л.В.Канторовича, который еще в 1939 г.
указал общий метод (метод разрешающих множителей) решения задач
линейного программирования, связанных с составлением оптимально-
оптимального плана при организации производственных процессов. Разработкой
дальнейших методов решения задач математического программирова-
программирования занимались впоследствии Д.Данцинг, В.С.Немчинов, А.Л.Лурье,
А.Г.Аганбегян, Р.Беллман, Р.Гомори, Г.Кун, Д.Б.Юдин, Л.Форд и дру-
другие отечественные и зарубежные ученые.
Линейное программирование охватывает методы решения экстре-
экстремальных задач (задачи оптимизации), имеющих дело со многими ли-
линейно взаимосвязанными величинами, подчиняющимися определенным
линейным ограничениям. Поэтому "Линейное программирование" как
предмет или раздел математики изучается студентами экономических,
технических и прочих (тем более математических) специальностей.
Если первые учебники и учебные пособия были ориентированы боль-
больше в научном направлении, то последующие авторы стали учитывать
дидактический и методический аспекты. В настоящем пособии автор
старался учесть наилучшие качества пособий, список которых приве-
приведен в конце книги.
Ограничимся кратким описанием названных качеств. Структура
книги позволяет обойтись без учебника, если речь идет о решении
задач. Каждый из девяти параграфов содержит краткую и вместе с
тем достаточную теоретическую информацию, приведены все "работа-
"работающие" теоремы или утверждения (они обозначены буквой У), позво-
позволяющие приступить к решению соответствующих задач. Графический
(геометрический) метод решения задач излагается традиционно, хотя
в пособии приведено много задач, решение которых можно свести к
этому наглядному способу.

Предисловие
Что касается наиболее значимого "симплексного метода", то тут
изложение материала преподнесено более экономным, методически
оправданным способом. Симплексные таблицы, применяемые в боль-
большинстве пособий, на наш взгляд, слишком громоздки, переход от
одной таблицы к другой на самом деле прерывает цельность решения,
а двойная запись в клетке для большей части студентов является
сложным действием для внимания.
Мы рекомендуем применять таблицу Гаусса (см. пособие [1]) как
в линейной алгебре, так и в линейном программировании. В таблице
Гаусса целевую функцию помещаем в последней строке, а базисные
неизвестные (переменные) легко узнаются по единичному столбцу.
Теорема оптимальности допустимого решения выражается в терминах
знаков целевой функции, и при этом отпадает необходимость допол-
дополнительных оценок, а таблица Гаусса компактна, вполне обозрима, и
занимает в 2 - 3 раза меньше места, чем обычные симплексные таб-
таблицы, не говоря об экономии времени на их составление. Случаи,
когда задача не имеет решения по тем или иным причинам (неограни-
(неограниченность функции или несовместность условий ограничений задачи),
также обнаруживаются в таблице.
Мы допускаем симплекс-преобразование с отрицательным разре-
разрешающим коэффициентом в случае, когда начальное базисное решение
недопустимо. При обсуждении проблемы двойственности легко уста-
устанавливается связь между решениями пары сопряженных задач, а также
между основными переменными одной задачи и дополнительными пе-
переменными другой. Добавим еще в этом пункте, что мы отказываемся
от метода дополнительных переменных для получения допустимого
решения в канонической задаче как методически неоправданного.
Транспортную задачу представляем почти стандартным способом,
используя лишь метод наименьших тарифов для получения начального
опорного решения. Что касается теоремы оптимальности, то решение
транспортной задачи оптимально, если среди оценок свободных клеток
нет отрицательных (нам это представляется более естественным).
В каждом параграфе предусмотрена система вопросов, которые
должны формировать прием мыслительной деятельности "синтез" —
умение делать выводы из той или иной информации. Ответы на по-
поставленные вопросы следует искать в теоретической части, в решении
примеров, или узнавать у преподавателя.
В заключение отметим, что в книге представлено 170 задач, из
которых 29 решены, остальные снабжены ответами. Это может обеспе-
обеспечить проведение аудиторных, домашних, зачетных и экзаменационных
работ. Практика показывает, что студенты охотно отзываются на пред-
предложения преподавателя о составлении "текстовых задач" по линейному
программированию, исходя из опыта, приобретенного в повседневной
жизни (надо минимизировать время на дорогу, оптимизировать еже-
ежедневную деятельность, добиться эффективности во всей дальнейшей
жизни).

Глава 1
ОБЩЕЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
§ 1. Постановка задачи линейного программирования
1.1. Общая задача линейного программирования формулируется
следующим образом.
Найти набор (наборы) действительных чисел X = (х\,Х2,... ,хп),
доставляющий экстремум (максимум или минимум) линейной целевой
функции
L(X) =c\x\ + с2х2 + ... + спжп	A.1)
и удовлетворяющий системе ограничений
пг2Х2 + ... + ainxn = bi, (i = 1,2,... , га), A.2)
2X2 + ... + CLinXn < bi,
(i = ra + l,m + 2, ...,m + s),	A.3)
2X2 + ... + ainxn > bit
(i = m + s+l,m + s + 2, ...,m + s+p),	A.4)
x^O, x/2^0, ..., %>0 (k^n).	A.5)
Условия A.5) означают неотрицательность /с компонент вектора X.
Запись X > 0 означает неотрицательность всех компонент X, т. е.
Ж1 >0,ж2 ^0,...,хп >0 или ж, >0 (J = 1,2, ...,п).
Допустимым решением (планом) задачи линейного программиро-
программирования называется любой n-мерный вектор X = (#i,#2> ••• >#п)> удовле-
удовлетворяющий системе ограничений A.2)-A.4) и условиям неотрицатель-
неотрицательности. Множество всех допустимых решений задачи образуют область
допустимых решений (сокращенно ОДР).
Решение (план) называется оптимальным, если оно допустимое и
доставляет экстремум целевой функции A.1).
1.2. Задача линейного программирования называется канониче-
канонической, если ограничения задачи состоят из системы уравнений и усло-
условий неотрицательности всех п переменных. Каноническая задача запи-
записывается в виде
L(X) = с\Х\ + С2Х2 + ... + спхп —> max (min),

Гл. 1. Общее линейное программирование
CL\\X\ + ai2^2 + ... + CL\nxn = Ь\,
' 2'	A-6)
j = 1,2,..., п.
Условие j = 1, 2,..., п будем записывать иногда так: j = 1, п.
1.3. Задача линейного программирования называется симметриче-
симметрической, если она имеет вид
п
L(X) = y^CjXj -^ max,
A.7)
^bi, г =1,2,...,г, Х>0
или
A.8)
1.4. Общая задача линейного программирования может быть при-
приведена к каноническому виду при помощи следующих утверждений.
УЛ. Неравенство а\Х\ + ... + апхп ^ Ь равносильно равенству
а\х\ + ... + апхп + жп+1 = Ь
и простейшему неравенству хп+\ ^ 0.
У.2. Неравенство а\Х\ + ... + апхп ^ Ь равносильно равенству
а\Х\ + ... + апхп — хп+\ = Ъ
и простейшему неравенству хп+\ ^ 0.
Переменные, вносимые в задачу при помощи этих утверждений,
называются дополнительными, или вспомогательными. Они вносятся
также и в целевую функцию с коэффициентами, равными нулю.
У.З. Каждую переменную, на которую не наложено условие неотри-
неотрицательности, можно представить в виде разности двух неотрицатель-
неотрицательных переменных:
Xj e R <& Xj = х- - х", х- > 0, x'j > 0.
1.5. Каноническую задачу A.6) можно привести к симметрическому
виду A.7) или A.8), и это имеет смысл только если в A.7) или в A.8)
число ограничений меньше т. Приведение можно осуществить при

1. Постановка задачи линейного программирования	9
помощи следующего приема. Систему уравнений, составляющую систе-
систему ограничений канонической задачи, необходимо разрешить относи-
относительно некоторого полного набора базисных переменных х\, Х2, ••• ,хг;
следовательно, остальные переменные жг+1,жг+2> ••• Дп становятся
свободными. Таким образом, система A.6) равносильна системе
х\ = C\ — (а\^г+\хг-\-\ + а\^г+2хг+2 + ... + &\пхп)>
a2,r+]xr+l a2,r+2Xr+2 ... а2пхп ,	^
/у* 	 / "л 	 f f\l	-* /j*	-* __!__ t\l	r\ li^	r\ —I—	—I— f\l	li^ 1
разрешенной относительно базисных неизвестных х\,Х2,... ,хг. Выра-
Выразим теперь целевую функцию L{X) через свободные неизвестные при
помощи A.9). Используя неотрицательность базисных неизвестных,
можно наложить условия их неотрицательности на правые части A.9),
опуская при этом х\, Х2,..., хг.
При необходимости можно использовать следующие равносильные
соотношения:
L(X) —> max <^> -L(X) -^ min,
L{X) —> min <^> —L{X) -^ max.
1.6. Задачи, сформулированные выше, на самом деле представ-
представляют собой линейные математические модели общих задач оптими-
оптимизации, которые заключаются в нахождении в заданной области то-
точек наибольшего и наименьшего значения некоторой линейной функ-
функции, зависящей от большого числа переменных. Такие задачи воз-
возникают в самых разнообразных областях человеческой деятельности,
главным образом в практике планирования и организации производ-
производства. Ниже будут рассмотрены некоторые задачи с экономическим
содержанием, математические модели которых описываются линей-
линейными функциями в выпуклых областях, ограниченных линейными
границами.
Пример 1.1. Следующую задачу линейного программирования при-
привести к каноническому виду:
L{X) = 3xi ~ 2х2 -хз^ extr,
х\ +2x2 = 3,
х\ +3ж3 > -2,
хх > 0, х3 ^ 0.

10	Гл. 1. Общее линейное программирование
Решение. В системе ограничений имеем одно уравнение (ра-
(равенство), которое сохраним. Второе ограничение — неравенство. Его
заменим согласно У. 1 равенством
Зх\ — Х2 +^з +^4 = 5
и простейшим неравенством х^ ^ 0. Третье ограничение (неравенство)
заменим согласно У.2 системой
!х\ + Зх3 -х$ = -2,
На переменную х^ не накладывается условие неотрицательности.
Заменим ее согласно У.З разностью
х2 = х'2- х%, х'2 > 0, xf2 > 0.
Каноническая задача содержит шесть переменных и имеет вид
(напомним, см. У. 1 и У.2, что дополнительные переменные х\ и х^
входят в L(x) с нулевыми коэффициентами):
L(X)=3x\- 2х'2 + 2х% - х3 -> extr,
xi + 24 - 24х = 3,
Зх\ — х'2 + ^2 + жз + ^4 = 5,
х3 > 0, х4 > 0, х5 > 0.
Пример 1.2. Следующую каноническую задачу линейного програм-
программирования привести к симметрическому виду:
L(X) = —2х\ + Х2 — Зжз + 4^4 — ^5 + 2^6 -^ max,
—Х\ + 2^2 + Хз — #4 + 2^5 + 3^6 = 3,
Xi + 2^2 — Жз + 2^4 — Жб = 1 1,
2ж1 - Зх2 + 2ж3 - 2ж4 + ж5 = 9,
ж/ > 0, j = Т7б.
Решение. Методом Жордана-Гаусса (с которым читатель должен
быть знаком из курса линейной алгебры, см., напр., [4]) приведем
систему ограничений исходной задачи к равносильной системе, раз-
разрешенной относительно трех каких-либо неизвестных. Для этого вос-
воспользуемся таблицей Гаусса (табл. 1.1), в которую вносим и целевую
функцию в виде уравнения
—2х\ + Х2 — Зжз

1. Постановка задачи линейного программирования
11
При этом следует иметь в виду, что разрешающий элемент брать из
последней строки нельзя; это дополнительная строка целевой функции,
которую впоследствии назовем индексной строкой и выделим в рамку:
Таблица 1.1
Х\
-1
1
2
-2
-5
©
2
0
0
1
0
0
0
1
0
0
Х2
2
2
-3
1
8
2
-3
-2
18
2
-7
-2
-9
-7
11
16
ж3
1
-1
2
-3
-3
-1
2
-1
-8
-1
4
-1
4
3
-4
-9
х4
-1
2
-2
4
3
2
-2
2
13
2
-6
2
-13/2
-9/2
7
15
2
0
Ci)
-1
0
0
1
0
0
0
1
0
0
0
1
0
Xq
3
-1
0
2
3
-1
0
2
О)
-1
2
2
1
0
0
0
св. чл.
3
11
9
L
-15
11
9
L + 9
40
11
31
L + 9
-20
-9
71
L + 49
Заметим, что последняя строка соответствует уравнению
\6х2 - 9х3 + 15х4 = L(X) + 49.
Из последнего блока таблицы можем записать задачу в следующей
форме:
L(X) = \6х2 - 9х3 + \5х4 - 49 -> max,
9
з 2
= 71 —
= -20
13
—
0, j = Т7б.

12	Гл. 1. Общее линейное программирование
Учитывая неотрицательность переменных х\, х$ и х§, отбросим
их, накладывая условия неотрицательности на правые части соот-
соответствующих равенств. Получим систему неравенств, которую сле-
следует согласовать с условием задачи: неравенства должны иметь
направление ^, поскольку задача ставится на максимум. Тем самым
приходим к эквивалентной задаче, записанной в каноническом виде:
L(X) = 16^2 — 9^з + 15^4 — 49 —> max,
9
-lx2 + Зж3 - - Х4 < -9,
+ 7^
4
-9х2 + 4х3 - у ха < -20,
Xj^O, j = 2,4.
Комментарий к таблице Гаусса (для тех, которые недостаточно
владеют методом Жордана-Гаусса решения линейных систем).
1)	В первом блоке таблицы записаны коэффициенты исходной си-
системы уравнений и целевой функции (в последней строке, выделенной
в рамке). Выбирается разрешающий коэффициент (он должен быть
отличен от нуля), обводится кружком. Столбец и строка, содержащие
этот коэффициент, называются разрешающими. Цель преобразования
Жордана-Гаусса — превратить разрешающий столбец в единичный
(с единицей вместо разрешающего коэффициента и нулями вместо
остальных).
2)	Второй блок таблицы получен следующим образом:
а)	разрешающая строка, умноженная на —2, прибавляется к первой
(получили первый нуль в разрешающем столбце);
б)	вторая строка переписывается (она уже содержит нуль в разре-
разрешающем столбце);
в)	разрешающая строка сохраняется (разрешающий коэффициент
равен единице);
г)	разрешающая строка, умноженная на 1, прибавляется к четвер-
четвертой (индексной, или целевой функции).
Получен первый единичный столбец (столбец переменной х$; этот
столбец называется базисным). Выбираем новый разрешающий коэф-
коэффициент и обводим его кружком.
3)	Третий блок таблицы получен следующим образом:
а)	разрешающая строка, умноженная на 5, прибавляется к первой;
б)	вторая (разрешающая) строка сохраняется;
в)	разрешающая строка, умноженная на —2, прибавляется к тре-
третьей;
г)	четвертая строка сохраняется (в разрешающем столбце имеем
нуль).

1. Вопросы	13
Получен второй единичный столбец (столбец второй базисной пере-
переменной х\). Выбираем новый (третий) разрешающий коэффициент —2
и обводим его кружком.
4) Четвертый блок получен аналогично. Разница в том, что раз-
разрешающая строка делится на —2, ибо в разрешающем столбце надо
получить на месте разрешающего коэффициента единицу. Пересчет
остальных коэффициентов блока лучше выполнять по формулам Жор-
дана-Гаусса. которые приведены в п. 4.1. Преобразования можно вы-
выполнять также по схеме, изложенной выше, но такие преобразования
несколько сложнее из-за того, что разрешающий коэффициент отличен
от единицы.
Вопросы
1.1.	Может ли система ограничений общей задачи ЛП включать
строгие неравенства?
1.2.	Может ли целевая функция задачи ЛП содержать нелинейные
выражения из переменных?
1.3.	Может ли допустимое решение задачи ЛП содержать отрица-
отрицательную компоненту?
1.4.	Чем отличается оптимальное решение задачи ЛП от допусти-
допустимого?
1.5.	Чем отличается канонический вид задачи ЛП от общего?
1.6.	Какая задача ЛП называется систематической?
1.7.	Каждая ли симметрическая задача может быть приведена к
каноническому виду? Если да, то как это делается?
1.8.	В чем состоит преобразование Жордана-Гаусса?
1.9.	Может ли единичный столбец состоять из одних нулей?
1.10.	Может ли каноническая задача быть приведена к общему
виду?
Являются ли следующие задачи задачами линейного программиро-
программирования? Ответ обосновать.
1.11.	Даны координаты трех вершин треугольника ABC:
АB,-3), ?C,6), СD,-1).
Найти точку М(х,у), минимизирующую сумму расстояний
МА + МВ + МС.

14
Гл. 1. Общее линейное программирование
1.12.
L(X) = Зх\ - Х2 —> max,
!х\ +х2 < 3,
1.13.
хх > О, ж2 > О.
L(X) = х\ -\- 2x2 + ^з -^ min,
Г Ж1 +2ж2 < 3,
1.14.
О, ж2 > О.
+ х\ ^ 5,
О, х2 > О.
1.2.
1.3.
Упражнения
Следующие задачи привести к каноническому виду.
1.1.	L(X) = 3^1 + 2x2 — %з -
хх +2ж2 < 7,
3^1 + Х2 — 2х% = 8,
2х\ +х3^ -5,
Ж1 ^ О, ж2 > О.
mm,
2х{
<	4,
<	8,
-2,
ж2 -2ж4 = 11,
ж/ ^ о, j = Т7^.
max,
ж2 + ^з = 5,
ж3 < 12,
Зж2 — жз
О, ж2 > О.
4,

1. Упражнения	15
1.4.	L(X) = 2х{ + Зж2 - 5ж3 -> extr,
i - хз < 7,
1 — 2^2 + 5^з =11,
^1 + Х2 — х$ ^ 2,
1.5.	L(X) = Зх\ + 2жз —> min,
X\ + 3^2 — Ж4 = 4,
Xi + ^2 — X3 ^ 6,
Xi > О, Ж4 > 0.
1.6.
xi > 0, ж2 > 0, ж3 > 0.
1.7.	-kpO = ~2ж2 + Зжз -^ max,
Л^2 ~r ^4 ^ —^),
1.8.	L(X) = 4^2 + хз -^ min,
I ^2 — X3 ^ 7,
Ti > 0 To > 0 Tq > 0
Следующие канонические задачи записать в симметрической
форме.
1.9.	L(X) = 2х\ — Х2 + Зжз + 2^5 + 4 ^ max,
-xi + 2^2 + 3^4 = 4,
Xj ^0, j = 1, 5.

16	Гл. 1. Общее линейное программирование
1.10.	Ь(Х) = 4х\ - Ъх2 + хз + 2ха —> min,
!3ж1 — 2^2 + жз + 4^4 = 6,
—7^1 + 10^2 + Зжз — 4^4 = 2,
1.11.
1.12.
f 2an-
1
{ 9xi-
2xi -
4ж1 -
\Х\ + И
Ь7ж2 +
Ь5х2 +
5 ^ °'
= 2ж1 -
3^2 + i
6^2 + '
j = l,5.
0х2 + хз 4
- Зх3 + х4
¦ 2х3 + 2х<
-х3 + 7хА
j = T74.
5^2 + 3 -
5хз + 7x4
2хз + 3x4
- 7x4 — 2 —> max
= 6,
1=4,
= 2,
-> min,
= 1,
= 2,
ж/ > 0, j = T74.
1.13.	L(X) =5ж1 -ж3
!Ж1 + Ж2 + 2^з — Х4 = 3,
ж2 + 2ж4= 1,
ж/ > 0, j = T74.
1.14.	L{X) = Ж1 + Х2 — хз — 3^4 — 7^5 -^ max,
—Х\ + Ж2 + Хз + 2^4 — 3^5 = 4,
Ж1 + Ж2 + 4^з + Х\ — 8^5 = 3,
х2 + х3 - 4ж5 = -4,
ж/ ^ о, j = 17^.
Ответы
1.1.	L(X) = Зж1 +2ж2 -Ж3 + Ж3 -^ max,

1. Ответы
17
1.2.
Х\ + 2X2 + Х4 = 7,
3xi +X2 -2xf3 + 2xf^ = 8,
2х\ + 4 — #з ~ Ж5 — 5,
хх 7*0, х2^ О, 4 > О,
4 > О,
О,
О.
= х\ — 1X2 — &хъ + Х4 — ха ~^ mm,
хх + 2^2 — Зжз + ^5 = 4,
хх + Х2 + 34 — 34х + жб — 8,
-х7 = -2,
24= И,
Тл > 0	Го > О	То > О	ГХ, > О
^Г/Х > О	^г > О	Гп > О	Т*7 > О
«^4 ^ ' 5 ^ ^» *^6 ^ ^' **^7 ^ ^*
2^2-2^
1.3.
= 2х{
max,
1.4.
1.5.
2ж2+Жз -Жд +Ж4 = 12,
2^1 — 3^2 — х'ъ + ^з — ^5 = 4,
Ж1 > 0, ж2 > 0, 4 > О,
жз > 0, ж4 > 0, хъ > 0.
= 2х\ - 2х'[ + 34 - 34 -> extr,
х\ - х'[ - Х3+Х4 = 7,
х\ - х'[ - 24 + 24 +
Ъх\ — Ъх'[
х'2 — х*2 — хз — х$ = 2,
х\
0, х'[
о, хА
0,
о,
4
О,
о.
min,

18
Гл. 1. Общее линейное программирование
1.6.
= х\
max,
| 4ж1 + Зж2 + 2ж3 - ^ + 4х = 5,
х\ ^ 0, ж2 > О, ж3 ^ О, 4 > О' 4 > О.
1.7.	Задачи со строгими неравенствами не относятся к задачам
линейного программирования.
1.8.	L(X) = 4x2 + %з -^ min,
!xi +ж2 +ж3 = 8,
Х2 — Х3 — Х4 = 7,
ж/ ^ 0, j = T74.
1.9.
1.10.
11	11	14
Х\ ~г ~~^~ Х§ -\- ——- —
3	3
5х4 - Юх5 < 16,
16^4 — 5^5 < 6,
-13ж4+ 17ж5 < -2,
Х4 ^ О,	ХЪ > 0.
= —2хх — 5^4 + 9 —> min,
I 	w, 	9t/i ^^ 	4
I	С*«Лу |	Z/Ov4 ^	^»
Ж1 > 0, ж4 > 0.
1.11.
35 51	70
= — —-хз + —гЖ4 + —г -^ max,
11	11	11
-жз + 9х
х3 > 0,
<-2,
10,
>0.
1.12.
L(X)=2xi -5x2
min,
-2хх +3ж2 > -1,
Ж1 > 0, ж2 > 0.

2. Построение математических моделей	19
1.13.	L(X) = 10-4ж3 -unin,
( -2х3 + Зх4 > -2,
х3 ^ О, хА > О.
1.14.
= х4 - хъ - 22 -> max
§ 2. Построение математических моделей
простейших экономических задач
2.1.	Для составления модели задачи линейного программирования,
заданной в текстовой форме, необходимо:
1)	ввести обозначения для неизвестных задачи;
2)	проанализировать и зафиксировать ограничения для них (напри-
(например, неотрицательность);
3)	составить систему ограничений задачи;
4)	составить целевую функцию и установить вид экстремума.
2.2.	Как правило, в задачах с экономическим содержанием ма-
математическая модель имеет симметрический вид (см. A.7) и A.8));
некоторые ограничения (неравенства) могут иметь противоположные
направления или быть равенствами.
Составить математические модели следующих задач с экономиче-
экономическим содержанием.
Пример 2.1. Для трех видов продукции П\, П^ и П% используется
три вида сырья С\, С^ и С%. Предприятие может израсходовать 32 т
сырья С\, не менее 40 т сырья С^ и не более 50 т сырья С%. Нормы
расхода сырья на единицу продукции того или иного вида приведены в
таблице 2.1. Здесь же указаны трудовые и энергетические затраты на
производство единицы продукции Яь Я2 и Яз.
Определить количества продукции видов П\, П^ и /7з, которые
следует производить при минимальных затратах энергетических и тру-
трудовых ресурсов.

20
Гл. 1. Общее линейное программирование
Таблица 2.1
Сырье
с2
Запасы (т)
32
40
50
Расходы (руб.)
Нормы расхода на единицу продукции (т)
Пх
2
4
3
4
3
1
1
5
0
2
3
6
Решение. Для построения математической модели этой задачи
обозначим через х\, ж2, #з количества продукции видов П\, /72 и /7з
соответственно, которые предполагается производить. Тогда целевую
функцию и ограничения задачи можно записать в виде
L{X) =
mm,
= 32,
40,
50,
Как видим, математическая модель задачи сводится к минимизации
некоторой линейной функции при ограничениях, записанных в виде
равенств и неравенств. Решение задачи будет приведено в § 5.
Пример 2.2 (задача о наилучшем использования ресурсов или о
максимальном доходе производственного предприятия). При производ-
производстве и видов продукции Р\, Р2, ..., Рп используется т видов сырья: S\,
52, ..., Sm. Запасы каждого вида сырья составляют Ь\, 62, ..., Ьш единиц
соответственно. Известно количество а^ единиц сырья с номером г
(г = 1,2, ...,т), необходимого для изготовления единицы продукции
вида j (j = 1,2, ...,п). Кроме того, известна прибыль, получаемая от
реализации единицы продукции каждого вида: с\, с2, ..., сп.
Требуется составить план выпуска п видов продукции Р\, Р2, ...,
Рп, при котором прибыль от реализации всей продукции была бы
максимальной.
Решение. Для построения математической модели сформулиро-
сформулированной задачи обозначим через х\, ж2, ..., хп количества единиц п
видов Р\, Р2, ..., Рп продукции, которую необходимо производить.
Условия х\ ^0, Х2 ^ 0, ..., хп ^ 0 (кратко X = (х\,Х2,... ,xn) ^
^ 0) означают, что количество производимой продукции не может быть
отрицательным числом.

2. Построение математических моделей
21
Условия задачи для удобства их анализа поместим в таблицу 2.2.
Таблица 2.2
Вид
сырья
Si
s2
Запасы
сырья
Ьх
ь2
Ьт
Прибыль
План выпуска
Виды продукции
Р\
аи
ат\
С\
Х\
Р2
а\2
&т2
С2
Х2
Рп
0>1п
&2п
&тп
Сп
Хп
Ограниченность запасов каждого вида сырья влечет ограниченность
различных видов производимой продукции:
S\ : а\\Х\ + а\2Х2 + ... + а\пхп < Ь\,
S
A22^2
ат\х\
При плане выпуска в Xj единиц продукции вида с/ прибыль пред-
предприятия равна CjXj.
Общая прибыль, получаемая от реализации всей продукции, может
быть представлена линейной целевой функцией, или функцией цели
L(X) = C\X\ +С2Х2 + ... +СПЖП.
Таким образом, надлежит найти набор неотрицательных чисел X =
= (х\,Х2,...,хп), удовлетворяющий системе ограничений, построенной
выше, и такой, что он доставляет максимальное значение целевой
функции L(X): L(X) -^ max.
Пример 2.3 (задача о рационе питания). Для сохранения здоровья
и работоспособности человек должен употребить в пищу в течение
суток (недели, месяца, года и т.д.) определенное количество белков,
жиров, углеводов, витаминов, микроэлементов и др.
Пусть имеется п различных продуктов Р\, Р2, ..., Рп и перечень
из т необходимых питательных веществ S\, S2, ..., Sm. Обозначим
через ajj (в единицах массы) количество питательного вещества Si (i =
= 1,2, ...,m), содержащегося в единице продукта Pj (j = 1,2,..., n).
Требуется организовать питание так, чтобы удовлетворялась норма
потребности в питательных веществах и чтобы стоимость использован-
использованных продуктов была минимальной.

22
Гл. 1. Общее линейное программирование
Таблица 2.3
Питательные
вещества
Si
s2
Стоимость
1 единицы
продукта (руб.)
Количество
единиц
продукта
Виды продукции
Pi
an
ат\
с\
XI
Р2
п\2
^22
@"т2
С2
х2
Рп
1
с.
X.
Суточная
потребность
1 человека
Решение. Для наглядности задачи ее данные поместим в табли-
таблицу 2.3. Исходя из обозначений, введенных в таблице, математическую
модель этой задачи можно представить в следующем виде.
Требуется найти набор чисел
X = (xi,x2,...,xn), (xi^O, x2^0, ..., хп^0),
удовлетворяющий системе ограничений
а\\Х\ + а\2х2 + ... + а\пхп ^ Ь\,
+	+ ... + а2пхп ^ Ь2,
ат\х\ + ат2х2 + ... + атпхп > Ьт
и доставляющий минимум целевой функции
L(X) = с\х\ +с2х2 + ... + спжп.
Пример 2.4 (задача о структуре товарооборота). Предположим, что
для реализации п групп товаров торговое предприятие располагает
т видами ограниченных материально-денежных ресурсов в количе-
количествах b\, b2, ..., Ьш единиц соответственно. При этом для прода-
продажи первой группы товаров на единицу товарооборота (например, на
10000 руб.) расходуется ресурсов первого, второго, ..., ш-го вида
в количествах аи, а2\, ..., ат\ единиц соответственно, для прода-
продажи второй группы товаров на единицу товарооборота расходуется

2. Вопросы	23
ресурсов первого, второго, ..., m-го вида в количествах соответственно
а\2, CL22, •••, CLm2 единиц, и так далее; для продажи n-й группы товаров
на единицу товарооборота расходуется ресурсов а\п, а2П, ..., атп
единиц. Известно, что прибыли от реализации соответствующих групп
товаров составляют с\, С2, ..., сп рублей.
Требуется определить плановый объем и структуру товарооборота,
при котором прибыль торгового предприятия от реализации всего то-
товара была бы максимальной.
Решение. Математическая модель этой задачи строится по ана-
аналогии с предыдущими. Пусть X = (х\,Х2, ••• ,хп) — план товаро-
товарооборота предприятия (предполагается реализовать х\ единиц товара
первой группы, Х2 единиц товара второй группы, ..., хп единиц товара
n-й группы. Тогда необходимо максимизировать прибыль от реализа-
реализации всех этих товаров:
L(X) = с\Х\ + С2Х2 + ... + спхп —> max.
При этом ограничения, связанные с материально-денежными ресур-
ресурсами, приводят к следующей системе неравенств:
а\\Х\ + а\2Х2 + ... + а\пхп < b\,
CL2\X\ + CI22X2
am\X\ + am2X2 + ...
X\ > 0, X2 > 0, ... , Xn > 0.
Вопросы
2.1.	В чем состоит схема построения математической модели задачи
с экономическим содержанием?
2.2.	В чем состоит смысл неотрицательности переменных задачи
ЛП?
2.3.	Есть ли какая-либо связь между числом переменных и числом
ограничений задачи с экономическим содержанием?
2.4.	Что понимается под выражением «неотрицательный вектор»?
2.5.	В чем состоит экономический смысл: а) целевой функции?
б) системы ограничений?

24
Гл. 1. Общее линейное программирование
Упражнения
2.1. Магазин планирует реализовать четыре вида товаров Т\, Т%,
Тз, Т\. Известны затраты на реализацию единицы товара, оплата
продавцов, ограничения на торговые площади и складские помещения,
а также прибыль от реализации единицы того или иного товара.
Требуется определить плановый объем и структуру товарооборота,
при котором прибыль магазина оказалась бы максимальной. Цифровые
данные приведены в таблице 2.4.
Таблица 2.4
Виды ресурсов
Рабочее время
продавцов
(человеко-дни)
Торговая
площадь (м2)
Складские
помещения (м2)
Прибыль (руб.)
Стоимость единицы товара
2
6
4
6
5
2
8
7
3
9
6
9
6
8
5
3
Суммарный
объем
50
200
40
max
Таблица 2.5
Вид ресурса
Сталь (кг)
Алюминий (кг)
Цветные металлы (кг)
Станко-токарные (ч)
Станко-фрезерные (ч)
Станко-шлифов. (ч)
Объем
ресурса
800
600
300
4800
5600
600
Прибыль (ден. ед.)
А
15
8
3
60
80
6
30
Норма расхода
на единицу ресурса
В
20
15
6
80
70
10
40
С
40
10
4
120
28
12
60

2. Упражнения
25
2.2 (задача о рационе питания). Животные должны получать еже-
ежедневно определенный набор из т питательных веществ в количе-
количествах не менее соответственно Ь\, Ъ^, ..., Ът единиц. Животные пи-
питаются кормами п видов К\, К^, ..., Кп. Известно количество пу
питательного вещества с номером г (г = 1, 2,..., га) в единице корма Щ
(j = 1, 2,..., п), а также стоимость с/ (j = 1, 2,..., п) единицы корма Щ.
Необходимо составить суточный рацион кормления животных при
минимальных затратах на покупку кормов.
2.3.	Для изготовления изделий А, В и С в качестве сырья исполь-
используется сталь, алюминий и цветные металлы, объемы которых ограни-
ограничены. Изделия производятся на токарных, фрезерных и шлифовальных
станках.
Требуется составить план выпуска продукции, при котором будет
достигнута максимальная прибыль от реализации всей продукции.
Составить математическую модель задачи при данных, приведенных в
таблице 2.5.
2.4.	Предприятие для выпуска данной продукции применяет три
технологии (способа производства) и использует три вида ресурсов.
Известно: Ь{ ед. (г = 1,2,3) — запасы ресурсов; а^ ед./ч (г = 1,2,3;
j = 1,2,3) — затраты г-ro вида ресурса на 1 ч работы с использова-
использованием j-й технологии; Cj руб./ч (j = 1,2,3) — прибыль предприятия от
реализации продукции, выпускаемой за 1 ч работы с использованием
j-й технологии; Т (ч) — общее время работы предприятия по всем
технологиям.
Требуется найти время работы предприятия, необходимое по каж-
каждой технологии, чтобы обеспечить максимальную прибыль от реализа-
реализации выпускаемой продукции. Составить математическую модель задачи
при Т = 300 ч по исходным данным, приведенным в таблице 2.6.
Таблица 2.6
Вид ресурса
1
2
3
Запасы ресурса bj (ед.)
800
1800
1100
Прибыль Cj (руб./ч)
Затраты работы а^ за 1 ч
работы по технологии
№ 1
8
12
12
600
№ 2
5
10
11
800
№ 3
10
9
5
750

26
Гл. 1. Общее линейное программирование
2.2.
2.3.
2.4.
Ответы
2.1.	L(X)=6x{+7x<2
6x\ +2^2 +
4x\ +8^2 +
r • > 0
= с\х\
а\\х\ +
жз + 3^4 —> max,
+ 4ж4 < 50,
+ 8ж4 < 200,
+ 5^4 ^ 40,
min,
j = 1, m.
L(X) =
max,
< 600,
300,
< 4800,
< 5600,
600,
хх ^ 0, х2 > 0, х3 > 0.
= 600^1
max,
8а>1 + 5x2
\2xx + 10.
12^1 + 11.
X\ -\- X2 ~\-
x\ ^ 0, ж
+ 10ж3 < 800,
г2 + 9ж3 < 1800,
Г2 + 5жз ^ 1100,
х3 < 300,
2^0, Х3 ^ 0.

3. Графический метод решения	27
§ 3. Графический метод решения
задач линейного программирования
3.1. Рассмотрим задачу линейного программирования с двумя пе-
переменными
L(X) = с\Х\ + С2Х2 —> extr,
а\\х\ +а{2Х2 < (» Ь\,
+C122X2
Q"ml%l ~Ь &т2%2 ^ (^) ^m»
x\ > О, ж2 > О.
Такая задача может быть решена графически (геометрически) ввиду
того, что в этом случае легко строить ОДР (область допустимых
решений). Она представляет собой многоугольник (ограниченный или
нет, либо вовсе пустое множество), стороны которого лежат на прямых,
получаемых из системы ограничений задачи
Экстремальные значения целевой функции достигаются в угловых
точках ОДР, принадлежащих опорным прямым к ОДР, т. е. крайним
линиям уровня целевой функции по отношению к ОДР.
3.2.	Алгоритм графического решения задачи линейного программи-
программирования состоит в выполнении следующих действий.
1)	Построить ОДР.
2)	Построить вектор нормали п= (сьсг) целевой функции (он
указывает на направление возрастания целевой функции).
3)	Построить нижнюю и верхнюю опорные прямые р и q, т. е.
крайние линии уровня целевой функции, имеющие общие точки с ОДР.
4)	Определить координаты экстремальных точек (Р = р П ОДР,
Q = q П ОДР) и вычислить значения целевой функции в них.
Примечания.
1)	Если ОДР — пустое множество, то задача не имеет решения
ввиду несовместности системы ограничений.
2)	Если ОДР неограничена по направлению вектора п= (сьсг),
то сама целевая функция неограничена сверху в этой области, и
принимаем LmaiiX(X) = +oo. Если ОДР неограничена в направлении,
противоположном п, то принимаем Lm-m(X) = —оо.
3.3.	Графически может быть решена также задача линейного
программирования, заданная в канонической форме, при условии
п — г ^ 2 (п — число переменных, г — ранг системы уравнений).
Для этого задачу надо привести к симметрическому виду. Графический

28
Гл. 1. Общее линейное программирование
метод можно распространить и на более общие ситуации, например, в
случае, когда условия неотрицательности распространяются не на все
переменные.
Решим графически задачи линейного программирования (приме-
(примеры 3.1-3.7).
Пример 3.1.
L{X) = 4xi + 7x2 + 6 —> extr,
1)
2)
3) <
4)
5)
' 2Х!
х\ -
2xi
2Х!
Xi S
-Зх2
VX2 <
+ 2х2
-Х2;
ю,
>з
^о,
Х\ > 0,
0.
Решение.
а) Область допустимых решений, которую обозначим буквой G,
построим следующим образом. Построим прямые с уравнениями
1)
2)
3)
4)
2xi — 3x2
Х\ + Х2 —
2xi+ 2х2 =
2xi — Х2
= 6,
ю,
з,
= 0,
Xi
Х2
XI
Х2
XI
Х2
XI
х2
0
-2
0
10
0
3/2
0
0
3
0
10
0
3/2
0
1
2
5)-7)
=6,
= 0,
2 = 0.
Прямые пронумерованы, а рядом с соответствующим уравнением
приведены координаты двух точек, через которые проходит прямая.
Номер прямой имеется также на чертеже (рис. 3.1).
б) Каждое неравенство, фигурирующее в системе ограничений,
определяет полуплоскость, причем эта полуплоскость содержит точку,
координаты которой удовлетворяют соответствующему строгому нера-
неравенству.
Легко видеть, что первые два и четвертое неравенства систе-
системы ограничений удовлетворяются координатами точки 0@,0). Поэто-
Поэтому три полуплоскости содержат начало координат системы Ох 1X2.

3. Графический метод решения
29
1)
V
Рис. 3.1
На соответствующую полуплос-
полуплоскость указывают стрелки, иду-
идущие от каждой прямой. Жир-
Жирной линией выделим границу
ОДР — выпуклый шестиуголь-
шестиугольник ABCDEF. Заметим, что
последние неравенства х\ ^ О,
Х2 > 0, означающие неотрицатель-
неотрицательность переменных задачи, опре-
определяют первую четверть плоско-
плоскости Ох\Х2-
в)	Строим теперь нормаль-
нормальный вектор целевой функции
п = D,7). Подчеркнем, что его
направление указывает на на-
направление возрастания целевой
функции L(X) = 4х\ + 7x2.
Прямая с уравнением 4х\ +
-\- 7x2 — О представляет собой «нулевую» линию уровня функции z =
= 4х\ +7x2. Эта прямая проходит через начало координат и перпен-
перпендикулярна нормальному вектору п = D,7). Передвигаем эту прямую
параллельно себе, или перпендикулярно п, и фиксируем два ее крайних
положения.
Эти крайние прямые, которые обозначим буквами р и q, должны
иметь с границей G либо общую вершину, либо общий отрезок, причем
направление от р к q совпадает с направлением п. В нашем случае р
проходит через точку A, a q — через точку Е. Эти прямые называются
соответственно нижней и верхней опорными прямыми для G.
г)	Определим координаты точек А и Е. На чертеже видим, что
точка А лежит на прямых 3) и 7), а Е — на 2) и 4). Именно поэтому
мы пронумеровали уравнения прямых и их изображения. Теперь легко
составить системы уравнений для определения координат этих точек.
Запишем это так:
А:
2 = 3,
х2 = 0,
АC/2,0);
Е:
?A0/3,20/3)
Х\ + Х2 = Ю,
2х\ -х2=0.
Вычислим значения целевой функции в точках А и ?:
LC/2,0) = 12, L( 10/3,20/3) = 66.
Этим задача решена.
Ответ: Lmin = LC/2,0) = 12, Lmax = L( 10/3,20/3) = 66.

30
Гл. 1. Общее линейное программирование
Пример 3.2.
О
L(X) = 15 - хх -
extr,
1)
2)
3)
-2хх + з
Хх — 2^2
Зж1 + Ах
Хх + Х2 1
 < 4,
2 > 12,
Решение. Четвертое неравен-
неравенство системы не учитываем, так как
оно тривиальное.
Рис. 3.2	Область допустимых решений
G представляет собой область,
неограниченную в направлении,
противоположном вектору целевой функции п = (—1,-2) (рис. 3.2).
Верхняя опорная прямая проходит через точку А.
Нижняя опорная прямая р не существует, так как каждая прямая с
уравнением —х\ — 2^2 = С при С < — 6 имеет общие точки с G. Дру-
Другими словами, для области G нет прямой, которая бы ее ограничивала
в направлении, противоположном п.
Имеем
А:
Зхх +4х2 = 12,
хх - 2ж2 = 2,
ЛA6/5,3/5),
LA6/5,3/5) = 53/5.
Ответ: Lm[n = —оо, Lmax = 1/A6/5,3/5) = 53/5.
Пример 3.3.
2)
3)
4)
L{X) = 2xx +x
—Х\ + Х2
2xi + х2
х{ - 2х2
Хх + Х2 ^
хх >0,
2 —> ех1
<6,
>4,
<4,
; ю,
Х2 >0.

3. Графический метод решения
31
Решение. Область G представляет собой шестиугольник
ABCDEF (рис. 3.3). Вектор п = B, 1) показывает, что целе-
целевая функция L(X) = 2х\ + х2 принимает максимальное значе-
значение в точке G(8,2), а минимальное — во всех точках отрез-
отрезка AF (нижняя опорная прямая р совпадает с прямой AF,
ее уравнение 2х\ + х2 = 4).
Таким образом,
Задача на минимум имеет
бесконечное множество реше-
решений, каждое из них представ-
представляет собой выпуклую линейную
комбинацию решений Х\ = B,0)
и Х2 = @,4); записываем это
в виде
X = tXx + A -t)X2, te [0,1].
Рис. 3.3
Ответ: Xmax = (8,2), Xlm[n = B,0), X2,min = @,4), Xm[n =
= ?B,0) + A - t)@,4), Lmax = 18, Lmin = 4.
Пример З.4.
= \+2x\- 3x2 -^ extr,
2)
3)
4)
X\
1 + Х2 ? 4,
2х2^ -1,
¦ Х2 ^ -^5
Решение. Заметим, что
полуплоскости, определяе-
определяемые системой неравенств
данной задачи, не имеют
общих точек. ОДР — пустое
множество (рис. 3.4).
Ответ: задача не имеет решения по причине несовместности усло-
условий задачи.
Рис. 3.4

32
Гл. 1. Общее линейное программирование
Пример 3.5. Графическим методом решить задачу:
L(X) = Зх\ + 2х2 — жз + 5^5 —> extr,
xi + 2ж2 - Зх3 + 11ж4 + 8ж5 = -8,
—2^1 + Х2 + Хз — 7^4 + 9^5 = 6,
х\ -\- Х2 + х% -\- 2х\ — 6^5 = 27,
xj ^ о, j = 17^.
Решение. Система ограничений состоит из трех уравнений с
пятью неизвестными (п = 5, т = 3, п — т = 2). Систему уравнений
решим относительно каких-либо трех неизвестных. Сделаем это при
помощи таблицы Гаусса (табл. 3.1), которая приведена ниже. Одновре-
Одновременно мы выразим и целевую функцию через свободные неизвестные
решенной системы.
Таблица 3.1
®
-2
1
3
1
0
0
0
1
0
0
0
1
0
0
0
х2
2
1
1
2
2
E)
-1
-4
0
1
0
0
0
1
0
0
х3
-3
1
1
-1
-3
-5
4
8
-1
-1
(з)
4
0
0
1
0
11
-7
2
0
11
15
-9
-33
5
3
-6
-21
3
1
-2
-13
х5
8
9
-6
5
8
25
-14
-19
-2
5
-9
1
-5
2
-3
13
св. чл.
-8
6
27
L
-8
-10
35
L + 24
4
-2
33
L+ 16
7
9
11
L-28
Из последнего блока таблицы 3.1 получаем систему, разрешенную
относительно базисных переменных х\, х2 и х%\

3. Графический метод решения	33
и целевую функцию, выраженные через свободные переменные
L(X) = -13ж4 + 13ж5 + 28.
Систему (*) заменим системой неравенств (х\ ^ 0, х2 ^ 0, жз ^ 0):
7 — 3^4 + 5^5 ^ О,	f 3^4 — 5^5 ^ 7,
9 - х4 - 2х5 > 0, => < ж4 + 2ж5 < 9,	(**)
ж4 + 3ж5 > -11,
^ ^ 0, j = 4, 5.
Первоначальная задача может быть переформулирована так:
при заданных ограничениях в виде системы неравенств с
двумя переменными найти экстремум линейной целевой функции
L(X) = -13ж4+ 13ж5 + 28.
Очевидно, что третье неравенство системы можно отбросить как
тривиальное: если ж4 ^ 0 и х$ > 0, то 2^4 + 3^5 > — 11.
Построив ОДР (это четырехугольник в плоскости Ох^х^, постройте
его самостоятельно), обнаруживаем, что целевая функция достигает
максимального значения в точке А@; 4,5) и минимального в точке
{3^4 — 5^5 = 7,
х4 + 2х5 = 9,
т.е. в точке 5E9/11,20/11). При этом L(A) =86,5, L(B) = -199/11.
Вспомним, что наша задача имеет пять неизвестных. Находим
значения остальных неизвестных из уравнений, выражающих значения
х\, Х2, хз через х\ и х*>. Получаем:
если х4 = 0, хъ = 4,5, то х\ = 7 - 3 • 0 + 5 • 4,5 = 29,5, х2 = 0,
х3 = 28,5;
если х4 = 59/11, хъ = 20/11, то х\ =0, х2 = 0, х3 = 299/11.
Задача решена полностью.
Ответ: Lmin = L@,0,299/11,59/11,20/11) = -199/11,
Lmax = LB9,5; 0; 24,5; 0; 4,5) = 86,5.
2 К. Н. Лунгу

34
Гл. 1. Общее линейное программирование
Пример 3.6. Графическим методом решить задачу:
L{X) = 2х\ + Х2 — Зжз + 2^4 —> max,
2х\ — Х2 + Зжз + ^4 = 4,
#1 + 2^2 + 3^3 + 2^4 = 6,
Ъх\ + 3^2 + жз ^ 6,
—2#i + ^2 — Зжз — 2^4 ^ 4,
х\ > 0, ж2 > 0.
Решение. Заметим, что в задаче отсутствуют условия неотрица-
неотрицательности для переменных х% и х\. Этим она отличается от задачи 3.5.
1) Приводим сначала задачу к неполному каноническому виду. Для
этого используем предложения У. 1 и У.2 из п. 1.4 (с их помощью
переходим от неравенств к равенствам). Новая задача, условно говоря,
полуканоническая, потому что условия неотрицательности переменных
жз и %4 остаются невыполненными. Задача имеет следующий вид
(коэффициенты при дополнительных переменных х$, х§ и xj в целевой
функции принимаются равными нулю):
F(X) = 2х\ +х2- Зх3 + 2х4 + 0х5 + 0xQ + 0х7 -^ max,
2х\ — Х2 + Зжз + ^4 = 4,
Ж1 +2ж2 + 3ж3 + 2ж4 = 6,
3^1 — Х2 — 2х% + Х4 — Х$ = 2,
5х\ + 3^2 + хз + xq = 6,
— 2^1 + Х2 — 3^3 — 2^4 + Х7 = 4,
Ж1 > 0, ж2 > 0, ж5 ^ 0, жб > 0, ж7 > 0.
2) Дальнейшая схема решения такова. Те переменные, на которые
условия неотрицательности не распространяются (это х% и х±), бу-
будем исключать из системы условий. Воспользуемся таблицей Гаусса
(табл. 3.2).
Последняя строка третьего блока таблицы соответствует целе-
целевой функции, написанной в виде уравнения со свободным членом
F + 46. Разрешим систему относительно х% и х±. Из последнего блока
таблицы 3.2 получаем:
— Xq,

3. Графический метод решения	35
2
1
3
5
-2
2
-13
-14
13
5
13
17
-13
12
26
5
-13
43
-1
2
-1
3
1
1
-10
-7
5
3
10
10
-10
13
15
3
-10
30
х3
3
3
-2
0
-3
-3
0
0
0
2
0
0
0
0
0
1
0
0
Табли
Х\
1
2
1
0
-2
2
(I)
3
1
0
-2
2
1
0
0
0
0
0
ца 3.2
0
0
-1
0
0
0
0
0
-1
0
0
0
0
0
-1
0
0
0
х6
0
0
0
1
0
0
-3
-3
2
1
3
3
-3
3
5
1
-3
9
х7
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
св. чл.
4
6
2
6
4
F
-14
-12
14
6
22
F+18
-14
16
28
6
-6
F + 46
Переменные х% и х\ в остальные уравнения и в целевую функцию
не входят. Временно опуская полученные уравнения системы (*), сфор-
сформулируем новую задачу:
F(X) = 43xi + 30ж2 + 9х6 - 46 -> max,
+ Sxq = 16,
- х5 + 5жб = 28,
+ 3^6 — Х7 = 6,
Х\ > 0, Х2 > 0, #5 ^ О,
жб ^ 0, х7 > 0.
Эта задача записана в канонической форме. Число неизвестных
п = 5, число уравнений т = 3ип — т = 2(г = т = 3), поэтому задачу
можно решить геометрически.

36
Гл. 1. Общее линейное программирование
3) Далее воспользуемся схемой решения задачи 3.5. Разрешая по-
последнюю систему относительно х$, xq, Х7, получаем
Х5 = --
16 12
20
13
= 18 + 37xj + 37x2,
a F(X) = 7xi ~ 9х2 + 2 -> max.
Условия #5 > 0, Жб > 0, ^7 > 0 приводят к неравенствам
а 20	4
6>
12
13
16
ИЛИ
—Ю,
2,
16,
-Зх2 > -Ю,
В последней и предпоследней системах имеется в виду, что х\
0
и Х2 ^ 0.
Теперь видно, что задачу можно решить графически (предлагаем
сделать это самостоятельно) и Fm8i^(X) = FD/3,0) = 34/3. Зная экс-
экстремальные значения х\ = 4/3 и Х2 = 0, находим значения остальных
неизвестных из систем (**) и (*). Опуская значения дополнительных
неизвестных х$, х§, xj, получаем хз = —2/3 (условие Х3 ^ 0 отсут-
отсутствует), х\ = 10/3.
Ответ: Lmax(X) = LD/3,0, -2/3, 10/3) = 34/3.
Пример 3.7. При составлении суточного рациона кормления скота
используют сено и силос. Рацион должен обладать определенной пита-
питательностью и содержать белка не менее 1 кг, кальция не менее 100 г
и фосфора не менее 80 г. При этом количество питательного рациона
должно быть не менее 60 кг. Содержание питательных компонентов
в 1 кг сена и силоса приведено в таблице 3.3. В ней указана также
стоимость единицы того или иного корма.
Требуется определить оптимальный суточный рацион кормления
животных, обеспечивающий минимальную стоимость корма.
Решение. Обозначим через х\ и Х2 количества килограммов се-
сена и силоса соответственно, составляющих рацион на одно живот-
животное в течение суток. Тогда условие задачи означает, что необходимо

3. Вопросы
37
Таблица 3.3
Название
ингридиента
Белок
Кальций
Фосфор
Норма (г)
1000
100
80
Стоимость ед. корма (ден. ед.)
Содержание ингридиента
в 1 кг корма (г/кг)
Сено
40
1,25
2
12
Силос
10
2,5
1
8
минимизировать функцию стоимости L(X) =
следующих ограничениях:
+
mm при
1)
2)
3)
4)
( 40^1 + \0х2 > 1000,
l,25xi +2,5ж2 > 100,
2х\ + х2^ 80,
хх + х2 >60.
Этим условиям могут удовлетворять только неотрицательные числа
х\ и х2, поэтому ограничения х\ ^ 0, х2 ^ 0 не указаны отдельно.
Задача с двумя переменными может быть решена графически. Со-
Соответствующая область допустимых решений неограничена (убедитесь
в этом сами), но нам надлежит найти минимум целевой функции,
который достигается в точке.
При этом
А:
АB0,40)
и Lmin = LB0,40) = 560 ден. ед.
Ответ: Оптимальный суточный рацион содержит 20 кг сена
и 40 кг силоса, при этом его минимальная стоимость 560 ден. ед.
Вопросы
3.1.	Какое максимальное число неравенств может содержать задача
ЛП с двумя переменными?
3.2.	Как строится ОДР задача ЛП с двумя переменными?
3.3.	Может ли ОДР быть невыпуклым многоугольником?
3.4.	Может ли ОДР быть открытым множеством? пустым?

38	Гл. 1. Общее линейное программирование
3.5.	Какая прямая называется опорной к ОДР?
3.6.	Чем отличается верхняя опорная прямая от нижней?
3.7.	Может ли линия уровня целевой функции быть параллельной
вектору целевой функции?
3.8.	Может ли задача ЛП с двумя переменными иметь два и только
два оптимальных решения?
3.9.	В каком случае задача ЛП с двумя переменными не имеет
решения?
3.10.	Каков геометрический смысл коэффициентов при неравен-
неравенствах в системе ограничений? Каков смысл коэффициентов целевой
функции?
3.11.	Какой вывод можно делать из того, что ОДР не ограничена
по направлению, противоположному вектору целевой функции?
3.12.	Можно ли решить графически симметрическую задачу с
тремя переменными?
3.13.	Сколько переменных может содержать задача линейного про-
программирования, которую можно решить графически?
3.14.	Можно ли решить графически задачу линейного програм-
программирования, если на некоторые ее переменные не наложены условия
неотрицательности?
3.15.	Определить соотношения между числом переменных и числом
ограничений, чтобы задачу можно было решить графически.
Упражнения
3.1. Найти максимальное значение линейной функции L(X) =
= 2х\ + 2^2 + 11 при ограничениях
Зхх +х2 -3 >0,
О ^ х\ ^ 3, Х2 ^ 0.
3.2. Найти минимальное значение линейной функции L(X) = Зх\ +
^2 + 10 при ограничениях
Ж1 +ж2 >2,
хх - х2 < 0,
Ж1 > 1/2, 0<ж2 <4.

3. Упражнения
39
3.3.	Найти максимальное и минимальное значения линейной функ-
функции L{X) = Зх\ + 7x2 ПРИ ограничениях
—х\ — 5x2 ^ О,
Зх\ — Х2 > О,
7х\ + 5x2 ^ 35,
6xi + 14x2 ^ 21,
Xi ^ О Х9 ^ 0.
3.4.	Найти максимальное и минимальное значения линейной функ-
функции L{X) = 2^1 + 3^2 + 1 при ограничениях
^, 	2т* <С 2
2ж1 -ж2 > -2,
х 0 < Ж1 < 4, 0 < Х2 < 4.
3.5.	Найти наибольшее и наименьшее значения линейной функции
L(X) = 2х\ — 4x2 при ограничениях
12,
9,
—7х\
Х\ -\-
14,
2,
Решить следующие задачи линейного программирования.
3.6.	L(X) = 15xi + 21х2 -^ extr,
2xi + Х2 ^ 6,
Xi + 2X2 ^ 6,
3.7.
ЦХ)-
- *1 т т^2 п^
4xi — ^2 ^
Xi — 2X2 ^
3xi+ 4x2
xi ^ 0, Х9
0,2 -> extr
-4,
S5,
-2,
^ 12,
^0.

40
Гл. 1. Общее линейное программирование
3.8.
L(X) = Зх\ — 15x2 —> min,
-х\ + Зх2 < 9,
2х\ + х2 > 10,
-ХХ + 4х2 >0,
хх ^ 0, х2 > 0.
3.9.
3.10.
- 20 -> extr,
—7x\ + 2x2 ^ 14,
X\ + 11X2 ^ 13,
#i + ^2 ^ 3,
4xi + 5x2 ^ 20,
хх ^ 0, x2 > 0.
= 2xi — 11x2 -
X\ — X2 ^ 6,
xi +x2 > 9,
-7xi + 2x2 > '
xi +x2 < 2,
xi ^ 0, х2 > 0.
Графически решить данные задачи линейного программирования.
3.11.
L(X) =х\- Зх2 - х3 - х4 - х5
—2xi +X2 +хз = 2,
—xi + 5x2 + %4 = 87,
5xi +X2 +Х5 = 49,
3xi — 4x2 + Хб = 11,
3xi + 4x2 — xj = 19,
128
max,
j = 1,7.
3.12.
min,

3. Упражнения
41
3.13.
L(X) = 33 — Зх\ + 2^2 — 3x4
Зх\ — 2^2 — хз + ^4 = 2,
4#i — #2 + #4 + #5 = 21,
4^1 — Ж2 — #4 + #5 = 1^'
#1 + Х2 — Xq = 3,
xj ^ о, j = Т7б.
max,
3.14.
= xi + 3^2 — 1 -^ max,
2х\ — Х2 + ^5 + Хб = Ю,
2ж1 + 2ж2 + ж4 + х6 = 25,
2^1 — 3^2 — жз + ^5 = —9,
6^2 + Х% + Х4 = 36,
^ > о, j = Т7б.
3.15.	L(X) = -
х2 + ж3 = 20,
3ж2 +ж4 = 12,
4^2 — х$ = 16,
min,
3.16.
= х\ -\- Х2 — хз — 3^4 — 7^5 -^ max,
—xi + Х2 + хз + 2^4 — 3^5 = 4,
Xi + Х2 + 4^3 + Х4 — 8^5 = 3,
Х2+х3 - 4ж5 = -4,
^ ^ о, j = 17^.
3.17.
6 —> min,
= 5,
Х\ + 2^2 — Хз + 7X4 + 3^5 = 2,
-Ж1 + Ж2 + Хз - Х4 = 4,
Xj ^ 0, j = T75.

42
Гл. 1. Общее линейное программирование
3.18.
3.19.
3.20.
0, j = 175.
max,
х\
= 4,
j = 1,5.
L(X) = Зх\ -
min,
х\ Л
4х,
4ж,
X
- ж2 - ж6
-Х2 + 1
-Х2-2
-2х2-
i>0,
= 3,
4 п^ «^
Ч + X
Ж3 +
7 =Т
г =
г =
x^--
7б.
19,
13,
= 2,
Составить математические модели следующих задач с экономиче-
экономическим содержанием и решить их.
3.21. При производстве трех видов продукции используют три вида
сырья. Составить план выпуска продукции, обеспечивающий максимум
прибыли. Исходные данные приведены в таблице 3.4.
Таблица 3.4
Запасы сырья
100
80
120
Прибыль (ден. ед.)
Расход сырья на единицу продукции
1
2
3
3
п2
2
1
1
4
Я3
1
2
2
1

3. Упражнения
43
3.22. В рационе животных используется два вида корма. Животные
должны получать четыре вида питательных веществ. Составить ра-
рацион питания животных, обеспечивающий минимальные затраты, при
исходных данных, заданных таблицей 3.5.
Таблица 3.5
Необходимое количество
питательного вещества
Пит. вещ. № 1
Пит. вещ. № 2
Пит. вещ. № 3
Пит. вещ. № 4
Норма
(ед. массы)
20
24
32
2
Стоимость единицы корма (ден. ед.)
Содержание питательного
вещества в единице корма
Корм 1
1
3
2
1
4
Корм 2
5
2
4
0
6
3.23.	Для изготовления изделий двух типов А и Б имеется 200 кг
металла. На изготовление одного изделия типа А расходуется 2 кг
металла, а одного изделия типа Б — 4 кг. Составить план произ-
производства, обеспечивающий получение наибольшей выручки от продажи
изготовленных изделий, если одно изделие типа А стоит 50 руб.,
а одно изделие типа Б стоит 70 руб., причем изделий типа А можно
изготовить не более 60, и изделий типа Б — не более 30.
3.24.	Из пункта А в пункт Б ежедневно отправляются пассажир-
пассажирские и скорые поезда. В таблице 3.6 указаны наличный парк вагонов
разных типов, из которых ежедневно можно комплектовать данные
поезда, и количество пассажиров, вмещающихся в каждом из вагонов.
Таблица 3.6
Поезда
Скорый
Пассажирский
Число
пассажиров
Парк вагонов
Количество вагонов в поезде
Багаж.
1
1
12
Почтов.
1
8
Плацк.
5
8
58
81
Купейн.
6
4
40
70
Мягкий
3
1
32
26
а) Определить оптимальные количества скорых и пассажирских
поездов, при которых число перевозимых пассажиров достигает макси-
максимума.

44	Гл. 1. Общее линейное программирование
б) Определить оптимальное число поездов (скорых и пассажир-
пассажирских), обеспечивающее максимальное количество перевозимых пасса-
пассажиров, при условии, что в день железная дорога не может пропускать
более шести пассажирских поездов.
Ответы
3.1.Lmax = LC,15/2)=32.
3.2.	Lmin = L(l/2,3/2) = 13.
3.3.	Lmin = 1,G/16,21/16) = 10,5; Lmax = ?C5/22,105/22) =
= 420/11.
3.4.	Lmin = L(l,0) = 3; Lmax = LD,4) =21.
3.5.	Lmin = LC/7, 8) = -218/7; Lmax = LC3/4, 3/4) = 27/2.
3.6.	Lmin = L@,2) = 42; Lmax = LB,2) = 72.
3.7.	Lmin = L(8/5,9/5) = 9; maxL(X) = +oo.
3.8.	mmL(X) = -oo.
3.9.	Задача не имеет решения по причине несовместности системы
ограничений задачи.
3.10.	Система ограничений несовместна.
3.11.	Fmax(X) = 100; Xmax = (8,9,9,0,23,41).
3.12.	Xm[n = A0/3,7/3,5/3,0,0); Lmin = 20.
3.13.	Xmax = A,2,0,3, 14,0); Lmax = 20.
3.14.	Xmax = C,6,0,0,3,7); Lmax = 20.
3.15.	Lmin = ?F,8,0,0,28).
3.16.	L(X) = LE,0,0,6, 1) = -20.
3.17.	L(X) = L(l,2,3,0,0) = -3.
3.18.	L(X) = L@,0,6,28, 3) = 159.
3.19.	L(X) = LB,6, 33,0,0) = 22.
3.20.	L(X) = L(l,2,0,3, 14,0) = 22.
3.21.	Lmax = LB0,40,0) =220.
3.22.	Lmin = LD,6)=52.
3.23.	Lmax = LF0,20) = 4400 (руб.).
3.24.	a) E,7); 6) F,6).

4. Симплексный метод	45
§ 4. Симплексный метод решения
задач линейного программирования
4.1. Симплексный метод применяется при решении задач линейного
программирования, заданных в канонической форме (см. п. 1.2).
Симплексный метод основан на том факте, что целевая функция
достигает экстремума на допустимом базисном решении. Таким обра-
образом, дело сводится к перебору базисных допустимых решений системы
ограничений-равенств задачи.
Симплексный метод позволяет переходить от одного допустимого
базисного решения к другому так, чтобы значение целевой функции
уменьшалось (увеличивалось) в задаче на минимум (максимум). Все
необходимые базисные решения целесообразно получить в таблице
Гаусса. В первый блок таблицы заносятся данные исходной задачи.
При необходимости некоторые уравнения системы ограничений следует
умножать на —1 (чтобы все свободные члены уравнений были неотри-
неотрицательными).
Последнюю строку, которую назовем индексной, заполняем коэф-
коэффициентами целевой функции, представленной в виде уравнения
с\х\ + с2х2 + ... + спжп = L(X) - с0,
где со — свободный член L(X). Вместо L — со записываем в первом
блоке только —со и характер задачи (max или min), а в последующих
блоках — результаты вычислений.
Первый блок таблицы Гаусса представлен в таблице 4.1.
Таблица 4.1
Х\	Х2	...	Хп	СВ. ЧЛ.
аи	а\2	...	а\п	Ь\
С\	С2	...	Сп	-С0
min(max)
Каждая итерация, т. е. переход от одного блока таблицы к другому
осуществляется известными элементарными преобразованиями Жорда-
на-Гаусса для строк. Они сводятся к следующим действиям:
1)	Сначала выбирается разрешающий (ведущий) коэффициент
apq ф 0. Разрешающий коэффициент нельзя брать в индексной строке.
2)	Разрешающая строка делится на apq, а разрешающий столбец
заменяют единичным с 1 вместо apq.

46	Гл. 1. Общее линейное программирование
3) Все остальные элементы (коэффициенты) блока пересчитывают-
ся по формулам
Q , . 	 Q ¦ ¦ 	 	LJL	_	/V 	 П ¦ 	 	±	—	VI	*^r>n
аИ
aiq
Cj = Cj	^-^ , tytp, 3 ТЪ	lJ	щ
apq
напоминающим известное мнемоническое правило прямоугольника
(см. схему), или арифметическими действиями над строками блока
таблицы при помощи разрешающей строки, если это возможно.
При этом надо следить за тем, чтобы новые свободные члены
уравнений оставались неотрицательными (об этом см. п. 4.3 ниже).
4.2. Часть итераций предназначена для получения первого (началь-
(начального) базисного решения. Предположим, что оно получено и имеет вид
тогда соответствующий блок таблицы имеет вид таблицы 4.2.
Таблица 4.2
X1 Х1^ ... Xffi— \ Xffi	XfYi-L. \	...	Xfi	СВ. ЧЛ
1
0
0
0
0 ...
1 ...
0 ...
0 ...
0
0
1
0
0
0
0
1
&т-\,т+\
О 0 ... О 0	7m+i ... In
При этом /?i > 0, C2 > 0, ..., (Зт > 0.
Если все компоненты базисного решения положительны (мы пред-
предполагаем, что ранг системы уравнений-условий задачи равен т,
г = т), то решение называется невырожденным, в противном слу-
случае — вырожденным.
Теорема 4.1 (теорема оптимальности решения). Допустимое ба-
базисное решение Х\ = (/Зь/32,... ,/Зт,0,0,... ,0) является оптималь-
оптимальным в том и только в том случае, когда среди коэффициентов
индексной строки нет положительных в задаче на максимум (нет
отрицательных в задаче на минимум).
Если коэффициенты индексной строки имеют разные знаки, то
соответствующее допустимое базисное решение не является оптималь-
оптимальным как в задаче на максимум, так и в задаче на минимум, и,
следовательно, следует переходить к другому базисному допустимому
решению (плану).

4. Симплексный метод	47
4.3.	Очередное допустимое базисное решение (план) получается
тем же способом, но с учетом некоторых особенностей. Ограничимся
случаем задачи на максимум, поскольку задача на минимум решается
по аналогичной схеме.
1)	Разрешающий столбец надо выбирать так, чтобы не приобретать
лишних положительных коэффициентов в индексной строке (хотя это
иногда неизбежно, см. теорему оптимальности).
Иногда в качестве разрешающего берут столбец максимального
коэффициента индексной строки.
2)	Неправильный выбор разрешающей строки может привести к
недопустимому решению. Правильный ее выбор состоит в следующем.
Предположим, что выбран разрешающий столбец. Составим отно-
отношения Ощ свободных членов bi уравнений (строка целевой функции
здесь не участвует) к положительным коэффициентам а,щ разреша-
разрешающего столбца. Найдем минимальное из этих отношений, которое
обозначим в (в соответствующей таблице оно подчеркивается). Строку
с этим числом надо считать разрешающей. Если таких строк несколько,
то выбор среди них безразличен.
3)	Если ведущий (разрешающий) коэффициент выбран правильно,
то соответствующие элементарные преобразования приводят только к
допустимому решению.
При необходимости процедура нахождения базисного допустимого
решения повторяется до получения оптимального решения, если оно
существует.
Заметим, что принцип выбора разрешающей строки следует соблю-
соблюдать и при поиске первого базисного допустимого решения.
4.4.	Рассмотрим несколько ситуаций, в которых получение опти-
оптимального решения недостижимо.
1)	Предположим, что полученное базисное решение задачи на мак-
максимум не оптимально: в индексной строке имеется, например, один
положительный коэффициент. Тем самым определена переменная, ко-
которую следует ввести в базис. Вместе с тем коэффициенты разрешаю-
разрешающего столбца неположительны. Следовательно, ввести эту переменную
в базис нельзя: это приводит к недопустимому решению. В таком
случае задача не имеет решения по причине неограниченности целевой
функции в ОДР.
2)	Предположим, что при поиске первого базисного решения натал-
наталкиваемся на недопустимые решения и не удается получить допустимого
решения. В таком случае задача не имеет решения по причине несов-
несовместности условий-ограничений задачи.
Симплексным методом решим следующие примеры задач линейного
программирования.

48
Гл. 1. Общее линейное программирование
Пример 4.1.
L(X) =
max,
—Х\
= 4,
о, j = п>.
= 4,
= 3,
Решение. Задача задана в канонической форме. Заполняем пер-
первый блок таблицы Гаусса (табл. 4.3) и приступаем к поиску первого
(начального) базисного допустимого решения.
Таблица 4.3
Х\
-1
0
(i)
1
0
0
1
0
0
0
1
0
0
0
1
0
Х2
1
-1
1
1
2
-1
1
0
-3/4
-1/4
-1
1/4
-1/4
-1/4
-3/4
-3/4
х3
1
-1
4
-1
5
-1
4
-5
9/4
-1/4
2
-19/4
3/4
-1/4
5/4
-7/4
х4
2
0
1
-3
3
0
1
-4
(з)
0
1
-4
1
0
0
0
хъ
-3
4
-8
-7
-11
©
-8
1
0
1
0
0
0
1
0
0
св. чл.
4
4
3
max
7
4
3
-3
18
1
11
-4
6
1
5
20
в
4:
3i
7:
4i
18
11
1
I
2
4
3
1
Пояснения:
а)	первый разрешающий коэффициент (в таблице он обведен круж-
кружком) брали в первом столбце, этот столбец наиболее простой, в нем
имеем один нуль;
б)	во втором блоке в качестве разрешающего брали столбец с
положительным коэффициентом индексной строки;

4. Симплексный метод	49
в)	в базис можно ввести либо х±, либо х$, хотя ввести нужно Х2,
поскольку только при Х2 коэффициент индексной строки положителен.
С другой стороны, ввести х^ нельзя, потому что все коэффициенты
этого столбца отрицательные — это приведет к недопустимому реше-
решению. Поэтому в базис ввели х\\
г)	получено первое базисное допустимое решение. Оно оптимально,
так как в индексной строке нет положительных коэффициентов.
Замечание: в дополнительном столбце в отношениях свободных
членов уравнений к коэффициентам ведущего столбца отрицательные
его коэффициенты (и нули) не участвуют.
Оптимальное решение Х\ = E,0,0,6, 1) получено одновременно с
первым базисным решением. При этом Lmax = —20.
Ответ: X = E,0,0,6,1), Lmax = -20.
Пример 4.2.
L(X) = —7х\ — 8^2 — 11#з + Ж4 + 2^5 — xq —> min,
6х\ + 11#2 + &сз — Х4 — х$ = 36,
4х\ + 2^2 + 7жз — #5 + #6 — 21,
х\ — х^ -\- xq = 42,
ж^о, i = 1,6.
Решение. Составим рабочую таблицу Гаусса (табл. 4.4). При
поиске начального базисного допустимого решения в качестве разре-
разрешающего имеет смысл брать столбец с отрицательным коэффициентом
индексной строки, так как при решении задачи на минимум (min обо-
обозначен в индексной строке первого блока, но в целях экономии места в
дальнейших блоках это будем опускать) положительные коэффициенты
нужно сохранять (см. теорему оптимальности). При выборе разреша-
разрешающей строки следует соблюдать рекомендации п. 4.3 (минимальное
значение в подчеркнуто).
Каждая итерация выполнена по правилу прямоугольника, вычис-
вычисления — по формулам Жордана-Гаусса. Первое допустимое базисное
решение оказалось оптимальным.
Ответ: Хх =A5/8,9/4,0,0,0,9), Lmin = L(XX) = 135/8.
Пример
4.3.
L{X)
1
1
= 2х\ -х2 +
Х\ + 2^2 — ¦
[ —Х\ + Х2 +
ж3 - 2х4 -
ж3 + 7ж4 +
- 10:
6Х5 «
Зх5 s
40,
Г5 —> max,
= 20,
S50,
0, j = T75.

50
Гл. 1. Общее линейное программирование
6
4
8
-7
6
4
4
-3
6/11
32/11
8/11
3/11
0
0
1
0
Х2
11
2
8
-8
(и)
2
6
-6
1
0
0
0
1
0
0
0
х3
8
7
12
-11
8
7
5
-4
8/11
61/11
7/11
4/11
1/4
3
7/8
1/8
Таблица
-1
0
-1
1
-1
0
-1
1
-1/П
2/11
-5/11
5/11
3
2
-5/8
5/8
х5
-1
-1
-1
2
-1
-1
0
1
-1/П
-9/11
6/11
5/11
-1/2
3
3/4
1/4
4.4
XQ
0
(l)
1
-1
0
1
0
0
0
1
0
0
0
1
0
0
св. чл.
36
21
42, min
-57
36
21
21
-36
36/11
159/11
15/11
-180/11
9/4
9
15/8
-135/8
0
21:1
42:1
36:11
21:2
21:6
36/11:6/11
159/11:32/11
15/11:8/11
Решение. Применить непосредственно симплексный метод к этой
задаче нельзя, ее форма не каноническая. Введем три дополнительных
переменных х§, xj, x$ и запишем задачу в канонической форме:
L(X) = 2х\ -х
- 2х4 -
0х7 + 0xs
= 20,
max,
Х\
= 40,
xj > 0, j = 178.
Заметим, что система ограничений приведена к единичному базису,
а значит, решение Х\ = @, 0, 0, 0, 0, 20, 50, 40) — базисное до-
допустимое. Оно неоптимально, потому что среди коэффициентов L{X)
при свободных переменных есть положительные (см. теорему опти-
оптимальности). Составим таблицу Гаусса (табл. 4.5) и найдем базисные
решения, для которых коэффициенты L(X) будут неположительными
(в тривиальных ситуациях столбец 0 не обозначен):
В каждом блоке таблицы имеем базисные допустимые решения.
Одно из них, Х\, отмечено выше. Далее, Х2 = B0,0,0,0,0,0,30,60)

(J)
1
-1
2
1
0
0
0
1
0
0
0
1
0
0
0
-1
2
1
-1
-1
(з)
0
1
0
1
0
0
0
1
0
0
х3
2
-1
1
3
2
-3
3
-1
1
-1
0
0
0
0
1
0
4. Симплексный
Таблица
х4
-2
7
1
2
-2
9
-1
2
1
3
-1
-1
4/3
8/3
-1/3
-1
х5
-6
3
0
-10
-6
9
-6
2
3
3
-6
-1
5
1
-2
-1
метод
4.5
XQ
1
0
0
0
1
-1
1
-2
2/3
-1/3
1
-3
1/3
0
1/3
-3
х7
0
1
0
0
0
1
0
0
1/3
1/3
0
-1
1/3
1/3
0
-1
х8
0
0
0
0
0
0
1
0
0
0
1
0
0
1/3
1/3
0
Ы
св. чл.
20
50
40
max
20
30
60
-40
30
10
60
-50
10
30
20
-50
неоптимально. В третьем блоке имеем первое оптимальное решение
Х3 = C0, 10,0,0,0,0,0,60) с L(X3) = 50. Заметим, что один из ко-
коэффициентов при свободной переменной х% можно ввести в базис,
не изменяя при этом значение L(X). Это приводит к другому опти-
оптимальному решению: ХА = A0,30,20,0,0,0,0,0) с L(X3) =50.
Таким образом, задача имеет бесконечное множество решений.
Прежде чем записать их, отбросим дополнительные переменные
xq, X7, х%. Получаем вырожденное оптимальное решение Х3 =
= C0, 10,0,0,0) и невырожденное решение ХА = A0,30,20,0,0), а из
них — общее решение X = t • Х% + [\ — t) • Х4, 0 ^ ? ^ 1, Lmax = 50.
Ответ: X = t • Х3 + A - t) • Х4, 0 < t < 1, Lmax = 50, Х3 =
= C0, 10,0,0,0), Х4 = A0,30,20,0,0).
Примечание. Заметим, что каждый раз разрешающий коэффициент
мы брали, исходя из простоты последующих вычислений. Однако неже-
нежелательно, чтобы простота вычислений приводила к дополнительным
положительным коэффициентам индексной строки. Именно этого мы
старались избегать.

52	Гл. 1. Общее линейное программирование
Пример
4.4.
L(X) = п
ZX-X2-X
Х2 ~ ЗХА +
Х3 + ЗХ4 +
- 2X2 + X
¦3 + ЗХ4 - 5
4^5 =И>
6x5 — 33,
3 + Юх4 -
5X5
-> extr,
= 2,
Xj >0, j = 1,5.
Решение. Эта задача задана в канонической форме. Она может
быть решена симплексным методом. Имеем п — т = 2, ранг системы
уравнений равен г = т = 3, поэтому ее также можно решить гра-
графически. В единой таблице Гаусса (табл. 4.6) выполним все нужные
нам операции по разрешению системы условий относительно трех
базисных неизвестных, скажем, х\, Х2, х%, и выражение линейной
формы через свободные неизвестные #4, ^5- В четвертом блоке полу-
получим решение задачи на минимум, в пятом — на максимум. Систему
условий, полученную в четвертом блоке, используем для графического
решения.
Из четвертого блока таблицы выписываем допустимое базисное
оптимальное решение на минимум:
Xmin = B,9,24,0,0), Lmin(X) = -3l.
Из пятого блока выписываем допустимое базисное оптимальное
решение на максимум:
Хтах = A4, 15,0,6,0), Lmax(X) = 17.
Из четвертого блока получаем решение системы условий относи-
относительно х\, Х2, #з, а линейную функцию L(X) выражаем через свобод-
свободные переменные х\ ИЖ5:
Х\ = 2 + 2^4 — #5,
Х2 = 9 + Ж4
= 24 — 4^4 — 3^5-
Используя неотрицательность базисных переменных, задачу можно
сформулировать геометрически:
найти экстремум линейной целевой функции
extr,

4. Симплексный метод
53
Таблица 4.6
Из рис. 4.1 видно, что целевая функция
двух переменных х\ и х$
L(X) = -31 + 8х4 + 3х5
достигает максимального значения в
точке АF,0) и минимального значения
в начале координат 0@,0). Значения
остальных неизвестных находим из си-
системы (*). При Х4 = 6, х$ — О находим
О
х\ = 14, х2 = 15,
= О,
а при #4 = 0, х$ = 0 находим
хх =2, ж2 = 9, ж3 = 24.
Х\
©
0
-2
1
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
Х2
1
1
-2
-1
1
®
0
-2
0
1
0
0
0
1
0
0
0
1
0
0
х3
0
1
1
-1
0
1
1
-1
-1
®
1
1
0
0
1
0
0
0
1/4
-1
х4
-3
3
10
3
-3
3
4
6
-6
3
4
12
-2
-1
0
8
0
0
1
0
хъ
4
6
-5
-2
4
6
3
-6
-2
6
3
6
1
3
3
3
5/2
15/4
3/4
-3
св. чл.
11
33
2
1
11
33
24
-11
-22
33
24
55
2
9
24
31
14
15
6
-17
Рис. 4.1
Л?"

54	Гл. 1. Общее линейное программирование
Таким образом, базисному допустимому решению, полученному
симплексным методом, соответствует вершина многоугольника G,
представляющего геометрическое изображение ОДР.
Решение. Условия задачи имеют смешанный характер, они со-
состоят из равенства и неравенств разных направлений. Кроме того,
заметим, что на переменную х% не накладывается условие неотрица-
неотрицательности. Решение задачи возможно несколькими способами.
Способ 1. Приведем задачу к каноническому виду и решим
ее симплексным методом. Для этого положим х% = х\ — х$, где
х\ ^ 0, #5 ^ 0- Тем самым, все переменные задачи стали неотрицатель-
неотрицательными. Остается перейти к условиям-равенствам:
L(X) = 2х\ + 3^2 — Х4 + #5 -^ max,
Х\ — Х2 + Х4 — Х$ = 5,
— ^5 + Хб = 12,
— Х4 + х$ — xj = 4,
х2 > 0, ж4 > 0,
жб > 0, х7 > 0.
Построим таблицу Гаусса (табл. 4.7).
Рассматривая второй блок таблицы, видим, что в базис можно
ввести только х\. Разрешающий коэффициент а\\ = 3 приводит к
недопустимому решению Х\ = C,0,0,-2, 10,0). Из четвертого блока
получаем базисное допустимое вырожденное неоптимальное решение
Х2 = A1,6,0,0,0,0).
Сначала отметим эффект второй итерации. Разрешающий коэффи-
коэффициент аи = 3 должен привести к недопустимому решению, так как
не соблюдено правило выбора разрешающей строки. В самом деле,
свободный коэффициент третьего уравнения отрицателен, но при этом
переменные х2, х%, х-? — допустимые.
Решение Х2 = A1,6,0,0,0,0) — вырожденное, базисное, допусти-
допустимое решение; оно неоптимально, так как в индексной строке имеем
один положительный коэффициент при xj. В базис нужно ввести толь-
только эту переменную xj. Но коэффициенты этого столбца отрицатель-
отрицательны, а это приведет к недопустимому решению. Поэтому дальнейшие

Х\
1
0
2
2
©
2
2
0
?2
-1
2
-3
3
-4
-1
-3
6
4.
Х4
1
1
-1
-1
0
0
-1
0
Симплексный
Таблица
хъ
-1
-1
©
1
0
0
1
0
XQ
0
1
0
0
0
1
0
0
метод
4.7
х7
0
0
-1
0
-1
-1
-1
1
55
св. чл. в
5
12
4
max
9 9:3
16 16:2
4 4i2
-4
1
о
о
-4/3 О
(б/з) О
-1/3 -1
О
О
1
о
1
о
-1/3
-1/3
-1/3
3
10
-2
О О
О
1
-4
1
О
О
О
1
О
О
О
-1
О
о
1
О -3/5
3/5 -1/5
О -2/5
11
6
О
О 0 -18/5 11/5
-40
итерации прекращаются с выводом: задача не имеет решения по при-
причине неограниченности целевой функции, т.е. max L{X) = +oo. Зна-
Значит, к первоначальным переменным х\, Х2, х^ можем не возвращаться.
Способ 2, геометрический, предлагаем реализовать самостоятельно,
используя следующие рекомендации. Рассмотрим систему ограничений
Здесь замена х% = х\ — х^ не произведена, т.е. х^
знака. Из первого уравнения исключаем х%\
Х% = 5 — Х\ + Х2,
и это выражение подставляем в линейную функцию:
L(X)= 3?i+2?2 -5.
произвольного

56
Гл. 1. Общее линейное программирование
Оставшаяся система из двух уравнений может быть представлена (с
учетом равенства хз = 5 — х\ + х2) в виде
( х6 = 7 +xi -Зх2,
(система неравенств получена из условий х§ ^ 0 и xj ^ 0), и задача
может быть решена графически.
Обратим внимание на то, что по ходу решения задачи на максимум
maxL(X) = +оо
в таблице Гаусса легко обнаружить решение задачи на минимум
bmin = LC,0) =4, xi=3, x2 = 0, х3 = 2.
Это решение было найдено в третьем блоке таблицы 4.7.
Ответ: maxL(X) = +оо.
Пример 4.6. Для изготовления четырех видов продукции Р\, Р2,
Рз и Р\ используются три вида сырья S\, S2, S3. Запасы сырья,
нормы расхода сырья на единицу продукции и получаемая прибыль от
реализации единицы продукции заданы в таблице 4.8.
Таблица 4.8
Вид сырья
Si
s2
S3
Прибыль (ден. ед.)
Нормы расхода
Р\
4
2
3
15
2
10
0
6
Рз
1
6
6
12
Ра
8
0
1
24
Запасы
сырья
1200
600
1500
max
Определить оптимальный план выпуска продукции, при котором
прибыль от ее реализации будет максимальной.
Решение. Обозначим через X = (х\,х2,хз,Х4) план выпуска про-
продукции (xj ^ 0 — количество единиц продукции вида j, которое пред-
предполагается производить). Требуется найти тот план X = (х^х^х^х^),
при котором прибыль будет максимальной, т.е. тот набор неотрицатель-
неотрицательных чисел, который доставляет наибольшее значение целевой функции:
L(X) = \5х\ + 6х2
24^4 —> max,

4. Симплексный метод	57
при следующих ограничениях, связанных с имеющимися запасами
сырья:
' 4ж1 +2ж2+х3 + 8ж4 < 1200,
хх + 10ж2 + 6ж3 < 600,
ж1 +6ж3+ж4 < 1500,
ж, > 0, j = Т~4.
Решение. Приводим задачу к каноническому виду:
L(X) = \5х\ + 6х2 + 12ж3 + 24ж4 + 0х5 + 0жб + 0х7 -^ max,
4xi + 2x2 + ^з + 8ж4 + ж5 = 1200,
2х\ + 10ж2 + 6х3 + жб = 600,
Зж1 + 6ж3 + ж4 + ж7 = 1500,
xj > 0, j = Т7Т.
Заносим данные задачи в таблицу Гаусса (табл. 4.9), выполним
необходимые симплексные преобразования, приводящие к оптимально-
оптимальному решению.
Таблица 4.9
Х\
4
2
3
15
1/2
2
3
3
11/24
1/3
1
0
Х2
2
10
0
6
1/4
10
0
0
1/24
5/3
-10
-15
х3
1
6
6
12
1/8
F)
6
9
0
1
0
0
х4
®
0
0
24
1
0
0
2
1
0
0
0
хъ
1
0
0
0
1/8
0
0
-3
1/8
0
0
-3
XQ
0
1
0
0
0
1
0
0
-1/48
1/6
-1
-3/2
х7
0
0
1
0
0
0
1
0
0
0
-1
0
св. чл.
1200
600
1500
max
150
600
1500
-3600
275/2
100
1400
-4500
Полученное решение X = @,0, 100,275/2,0,0, 1400) - оптималь-
оптимальное (индексная строка не содержит положительных коэффициентов).
Оставляем первые четыре компонента (в задаче имеем только четыре

58	Гл. 1. Общее линейное программирование
вида продукции). Получаем X = @,0, 100,275/2). При этом прибыль
равна
L@,0, 100,275/2) = 4500 (ден. ед.).
Посмотрим, как этот план сказывается на использовании сырья.
План предусматривает производство 100 единиц продукции Р% и
275/2 единиц продукции Р±\ продукции Р\ и Р2 производить не нуж-
нужно. При этом сырье S\ использовано полностью A00 + 8-275/2 =
= 1200 ед.), сырье S^ использовано полностью F • 100 = 600 ед.), а
сырье 5з использовано неполностью F • 100 + 1 • 275/2 = 737,5 ед.;
762,5 ед. сырья 5з остается неиспользованным).
Ответ: X = @,0, 100,275/2), 1,@,0, 100,275/2) = 4500 ден. ед.
Вопросы
4.1.	Какую роль играет в симплексном методе разрешающий (веду-
(ведущий) коэффициент?
4.2.	Чем отличается вырожденное решение от невырожденного?
4.3.	При каких условиях допустимое базисное решение является
оптимальным?
4.4.	Может ли оптимальное решение быть вырожденным?
4.5.	В чем состоит симплексный метод решения задач ЛП?
4.6.	Каким образом следует выбирать разрешающий столбец при
переходе от одного к другому базису?
4.7.	Каким образом следует выбирать разрешающую строку?
4.8.	Какие последствия влечет отрицательность коэффициентов
системы ограничивающего столбца?
4.9.	Может ли симплексный метод приводить к бесконечному мно-
множеству решений?
4.10.	Какой вывод можно сделать из того, что задача не имеет
допустимого базисного решения?
4.11.	Можно ли симплексным методом решить заданную симмет-
симметрически задачу линейного программирования?
4.12.	Можно ли симплексным методом решить задачу линейного
программирования, если на некоторые ее переменные не наложены
условия неотрицательности?

4. Упражнения	59
Упражнения
Симплексным методом решить следующие задачи линейного про-
программирования, заданные в каноническом виде.
4.1.	L(X) = х\ + 2x2 + хз — Х4 — 6 —> max,
-х\ + 5ж2 + ж3 + Х4 + х5 = 10,
2х\ — Х2 + х% — 3^4 = 6,
^з + 2ж4 + Зж5 = 25,
4.2.	-Ц-^О = ^1 + 2^2 + Х4 + ^5 "^ max,
2х\ — Х2 — хз = — 1,
#2 + ХА — 6,
Ж1 +Ж2 — ^5 = 25,
4.3.	^(-^) — 5^1 + Х2 — Зжз + 2^4 -^ min,
Г Зх\ + 2ж2 + ж3 + Х4 = 7,
I 5ж1+3ж2+жз + 2ж4 = 11,
^ >0, j = 1,4.
4.4.	L(X) = 2xi - х2 + Зж4 + 2ж5 + 4 -> min,
xi — 2^з + 2^4 — 3^5 = 2,
2х\ + #2 + 4^з + ^5 = 6,
—#1 + 2^2 + 3^4 = 4,
^ ^ о, j = 17^.
4.5.	i'(-X') = -2#i + 6ж2 + 2ж4 -^ max,
3xi — 3^2 + 4жз — 2^4 = 30,
—Х\ + 2^2 — Жз + Х4 = 5,
^ > 0, j = Т~4.

60	Гл. 1. Общее линейное программирование
4.6.	Ь(Х) = 2х\ + Зх2 + 2ж3 + 4x4 —> min,
Г -Ж1 + 2х2 + х3 + 6ж4 = 140,
1 Ж1 + 2ж2 + Зх3 + 2ж4 = 100,
^ >0, j = 1,4.
Симплексным методом решить следующие задачи линейного про-
программирования, записанные в общем или симметрическом виде.
4.7.	L(X) = х\ — Х2 — Зжз -^ min,
L(X) = 6х\ + 5x2 + 9^з -^ max,

4. Упражнения	61
4.14.
4.16.
4.12. L(X) = 2xi + ж2 - Зж3 + 2х4 + 1Ож5 -^ min,
1 — Х2 + 2^з — 2^4 — 6^5 = 2,
1 + 2^2 — Хз + 7X4 + 3^5 = 5,
—Х\ + Х2+ Хз — Х4 = 4,
Xj ^ О, j = ТЛ
4.13. ^(-^) — 2^1 + Х2 — хз + Х4 — х$ -^ max,
Xj ^ 0, j = 1~4.
4.15.
= —6^1 + 3^2 + 3^4 -^ max,

62
Гл. 1. Общее линейное программирование
4.17.
4.18.
4.19.
4.20.
4.21.
4.22.
L{X) = 6#i — 2x2 —
2 — ^з ^ —2,
min,
= 4,
х2
6,
Xj > 0,
= 2x,+
-2x{+l
X1 + 2X2
2X] — X2
Xj ^ 0,
= 4x,+
-3xi +;
-X! + 2:
X\ - 3X2
i = i
¦ 4^2 + X
lx2 + жз
+ 2жз ^
— Зжз ^
3 = 1
6x2 + 4:
C2 + 2^3
+ ^3 <
,3.
<36,
:45,
:30,
7з.
^3 ^ 1
$10,
^70,
10,
max,
, j = 1,3.
X) = 4 + 2^2 + ?3 + 4^4 + Ж5 —> max,
3^i — 3^2 + Зжз — 6x4 — 2^5 = 0,
2ж2 - x3 + Зж4 + 2ж5 = 6,
3#i — 3^2 + 2^3 — ЗЖ4 = 6,
xj ^ 0, j = 17^.
L(X) = 49xi + 64ж2 + 60ж3 + 0, 8 -> min,
J x2 x3 /
I Ax 1 + 5^2 + 5жз ^ 6,
x^O, j = l3.

4. Упражнения
63
4.23.	L(X) =х\-хз- Зх4 -> max,
' Ъх\ ~\- Х2 — 5^4 ^ О,
х^ _|_ Жо _|_ 2^3 + ^4 ^ 2
2^2 + б^з + 3^4 ^ 3,
3^1 + 3^2 + 3^3 — Х4 ^ 4
(условия неотрицательности а^- отсутствуют).
4.24.	-^РО = 2^1 + жз — ^4 -^ max,
Зх\ + 3^2 + Жз + ^4 = 12,
г . > 0 'j — T~i
<JU о ^>- vy, J — 1 , т:.
4.25.
L(X) =х\+ 2x2
min,
6,
5,
4.26. Предприятие располагает ресурсами сырья, рабочей силы и
оборудования, необходимыми для производства любого из четырех ви-
видов производимых товаров. Затраты ресурсов на изготовление единицы
данного вида товара, прибыль, получаемая предприятием, а также
запасы ресурсов указаны в таблице 4.10.
Таблица 4.10
Вид ресурса
Сырье (кг)
Рабочая сила (ч)
Оборудование (станко-часы)
Прибыль на ед. товара (ден. ед.)
Вид товара
1
3
22
10
30
2
5
14
14
24
3
2
18
8
56
4
4
30
16
48
Объем
ресурсов
60
400
130
max
По этим исходным данным решить следующие задачи:
а) выяснить, какой ассортимент товара надо выпускать, чтобы при-
прибыль была максимальной;

64
Гл. 1. Общее линейное программирование
б)	определить оптимальный ассортимент при дополнительном усло-
условии: первого товара выпустить не более 7 ед., второго — не менее 8 ед.,
а третьего и четвертого — в отношении 1 :2;
в)	определить изменение в оптимальном ассортименте, найденном в
случае а), если ресурсы сырья увеличены на 50%, а ресурсы рабочей
силы и оборудования — на 30%;
г)	определить в случае а), как повлияет на максимальную прибыль
увеличение каждого из видов ресурсов на 1 ед.
4.27.	Для изготовления изделий № 1 и № 2 имеется 180 кг метал-
металла. На изготовление одного изделия № 1 расходуется 2 кг металла, а
изделия № 2 — 3 кг. Составить план производства, обеспечивающий
получение наибольшей выручки от продажи изделий, если отпускная
цена одного изделия № 1 равна 13 руб., а изделия № 2 — 17 руб.,
причем изделий № 1 требуется изготовить не более 60, а изделий
№ 2 — не более 40.
4.28.	Для изготовления трех видов продукции Яь Я2, Я3 использу-
используются три вида сырья S\, S2, S3, запасы которых указаны в таблице 4.11.
Известны количества единиц сырья Si, S2, S3, необходимые для про-
производства единиц продукции Яь Я2, Я3 соответственно, и стоимость
реализации каждой единицы готовой продукции.
Таблица 4.11
Вид сырья
Si
S2
Запасы
(ед. объема)
2106
2340
650
Стоимость продукции (ден. ед.)
Виды продукции
П{
3
10
5
80
п2
3
9
5
60
Я3
9
15
1
50
Составить план выпуска продукции, обеспечивающий максималь-
максимальную прибыль.
Ответы
4.1.	Lmax(8,0, 11,7,0) =6.
4.2.	Lmax = +00.
4.3.	Lmin@,0,3,4) = -l.
4.4.	LminB2/13, 34/13,0,2/13,0) =68/13.
4.5.	Lmax@, 10, 15,0) =60.

4. Ответы	65
4.6.	Lmin = L@,0,20,20) = 120.
4.7.	Lmin = L(l,ll,12) = -46.
4.8.	Lmax = L@, 12,0,6) = 126.
4.9.	L@,4/3,6) = 182/3.
4.10.	Lmax = ?@,5/6,22/9) = 182/3.
4.11.	Lmin = L@, 1/2,7/6) = 112/3.
4.12.	Lmin = A,3,2,0,0) = 1.
4.13.	LC0,20,0, 10,0) = 90.
4.14.	L@,0,11,70) = 136.
4.15.	Система условий несовместна.
4.16.	L(8,4,0,0) = LD, 8,0,0) = 12.
4.17.	LminB,6,8) = -64.
4.18.	Xx = (9, 18,0), X2 = B1, 12,0), Lmax(X) = 90.
4.19.	Lmax = +oo.
4.20.	Lmin = -oo.
4.21.	Lmax = L@,0, 12,6, 5) = 40.
4.22.	Lmin = L@, 1/20,23/20) = 73.
4.23.	Lmax = LD,0, -7/5, 19/5) = -6.
4.24.	Lmax = LB,2,0,0)=4.
4.25.	Lmin = LA4/3,0,0, 1/3) = 16/3.
4.26.	a) x3 = 16,25, Lmax = 910;
б)	x2 = 8, x3 = 6,45, x4 = 0,9, L(X) = 286,4;
в)	xs = 21,25, L(X) = 1183;
r) xs = 16,375,
Указание. Таблица Гаусса канонической модели представлена таб-
таблицей 4.12.
4.27.	Lmax = LF0,20) = 1120.
4.28.	Lmax = LA14,0,80) = 13120.
3 К. Н. Лунгу

66
Гл. 1. Общее линейное программирование
Х\
3
22
10
30
1/2
-1/2
5/4
-40
Х2
5
14
14
25
3/2
-35/2
7/4
-73
Таблица
2
18
(§)
56
0
0
1
0
х4
4
30
16
48
0
-6
2
-64
4.12
хъ
1
0
0
0
1
0
0
0
х6
0
1
0
0
0
1
0
0
х7
0
0
1
0
0
-9/4
1/8
-7
св. чл.
60
400
130
max
27
107,5
16,25
-910
§ 5. Двойственность в линейном программировании
5.1. Предположим, что задача линейного программирования задана
в следующем виде:
L(X) = с\Х\ + С2Х2 + ... + спхп —> max (или min),
а\\х\
Ь\
ат\х\
(или
(или
(или
Ът)
У\
У2
Ут
E.10)
Составим другую задачу линейного программирования, число
переменных которой равно числу ограничений данной задачи, т. е. т.
Обозначим их буквами у\, г/2, ..., ут (они записаны справа от системы
ограничений приведенной задачи). Эта задача имеет вид:
F(Y) = biyi+b2y2-
«112/1 + «212/2 + ••• -
-&22У2 + ... "
Ъту
У\
у2
-> min (или max)
(или ^ с2)
ь (ИЛИ < Cm)
Ут > 0.
E.11)

5. Двойственность в линейном программировании	67
Вторая задача называется двойственной, или сопряженной для
первой, а первая — прямой, или основной.
Если для второй задачи составить двойственную задачу, то получим
первую. Таким образом, сформулированные задачи составляют пару
взаимно двойственных, или взаимно сопряженных задач линейного
программирования.
Отметим особенности пары взаимно двойственных задач.
1)	Если основная задача — задача на максимум (минимум), то
система ограничений должна состоять из неравенств вида < (>), и в
таком случае двойственная задача должна быть задачей на минимум
(максимум), а ее система ограничений должна состоять из неравенств
вида > «).
2)	В основной задаче все переменные должны быть неотрицатель-
неотрицательными.
3)	Коэффициентами целевой функции F(Y) двойственной задачи
являются свободные члены системы ограничений основной задачи, и
их число равно т.
4)	Основная матрица системы ограничений двойственной задачи по-
получается транспонированием матрицы системы ограничений основной
задачи.
5)	Свободными членами системы ограничений двойственной задачи
являются коэффициенты целевой функции основной задачи.
6)	Все переменные двойственной задачи неотрицательные.
5.2. Предположим теперь, что основная задача задана в ослаб-
ослабленной форме, т. е. среди ее переменных имеются переменные произ-
произвольного знака (на них не наложено требование неотрицательности),
а система ограничений содержит неравенства противоположных на-
направлений и, возможно, равенства. Построение двойственной задачи в
таком случае основано на следующих правилах.
1)	Все неравенства системы ограничений основной задачи следует
привести к одному направлению: ^ в задаче на минимум или ^ в
задаче на максимум.
2)	Если в системе ограничений основной задачи имеется равенство
(уравнение), то та переменная yi, которая соответствует этому г-му
ограничению-равенству, может быть произвольного знака. Запишем
это соответствие так:
ацх\ +ai2X2 + ... + ainxn = bi —> yi е R.
3)	Если на некоторую переменную Xj основной задачи не наложено
условие неотрицательности, то соответствующее ей ограничение двой-
двойственной задачи является равенством:
Xj e R -> a\j у\ + a2j У2 + • • • + amj ym=Cj.

68	Гл. 1. Общее линейное программирование
5.3. Для основной задачи линейного программирования и двой-
двойственной к ней задачи справедливы следующие теоремы.
Теорема 5.1. Если одна из пары двойственных задач линейного
программирования имеет решение, то и другая задача имеет ре-
решение, и при этом значения целевых функций этих задач равны:
()	()
Теорема 5.2. Произвольное допустимое базисное решение одной
задачи из пары двойственных оптимально тогда и только тогда,
когда система ограничений двойственной задачи совместна.
Теорема 5.3. Если целевая функция одной из пары двойственных
задач неограничена снизу (сверху), то система ограничений другой
задачи этой пары несовместна.
5.4. Если основная задача линейного программирования допускает
экономическую интерпретацию, то аналогичную интерпретацию можно
придать и двойственной задаче. Обратимся к одной из множества таких
возможностей. Предположим, что основная задача представляет собой
задачу наилучшего использования сырья (см. пример 2.2). Математи-
Математическая модель этой задачи описывается условиями E.10) (задача на
максимум с системой неравенств направления ^).
Двойственная задача
Предположим, что имеется второй производитель, который хочет
перекупить сырье, а следовательно, ему нужно минимизировать сум-
суммарные затраты на приобретение всех видов сырья. Введем величины
оценок (цен) всех видов сырья S\, S2, •••, Sm, которые обозначим через
у\, г/2, ..., Ут {у% ~ стоимость единицы сырья Si, biyi — стоимость
запаса hi этого сырья). Стоимость всего сырья равна
F(Y) = Ъху\ + Ъ2у2 + ... + Ътут -> min,
и она подлежит минимизации.
Первому производителю невыгодно продавать сырье, если суммар-
суммарная стоимость всех видов сырья, расходуемых на каждый вид про-
продукции, меньше прибыли cj, получаемой при реализации этого вида
продукции. Таким образом, приходим к системе ограничений, совпада-
совпадающей с системой E.11):
«212/2 + -.. +С1т\Ут > С\,
Условия yi > 0, г = 1,2,..., ш, вполне естественны.
Этим установлена связь между двумя взаимно двойственными за-
задачами линейного программирования.

5. Двойственность в линейном программировании	69
Для следующих задач линейного программирования построим со-
соответствующие им двойственные задачи.
Пример 5.1.
L(X) = 2х\ + 3^2 — хз —> min,
2х\ — Х2 + 2жз ^ — 1,
Ж1 + Зж3 > 2,
#1 > О, Х2 > 0, Жз > 0.
Решение. Прямая задача удовлетворяет условиям п. 5.1.
а)	В прямой задаче имеем три ограничения. В двойственной задаче
имеем три переменные у\, г/2, уз (они уже записаны в условиях прямой
задачи).
б)	Целевая функция строится по свободным членам системы огра-
ограничений прямой задачи, а сопряженная задача — задача на максимум:
F(Y) = Зу\ -У2 + %Уз -> max.
в)	Поскольку переменные прямой задачи неотрицательны, система
ограничений двойственной задачи состоит только из неравенств, про-
противоположных неравенствам прямой задачи, а коэффициенты систем
ограничений двойственной и прямой задач составляют транспониро-
транспонированные матрицы:
' 2/i + 2у2 + 2/з < 2,
22/1 - У2 < 3,
г) Так как система ограничений прямой задачи состоит только из
неравенств, то переменные двойственной задачи неотрицательны:
2/1 >0, У2> 0, уз > 0.
Ответ:
F(Y) 3	2 max,
У1
Пример 5.2.
\+х\— 2x2 + Зжз — 5^4 -^ min,

70
Гл. 1. Общее линейное программирование
—2х\ —
= 5,
хх > 0,
—5,
> 0.
Решение. Задача не отвечает требованиям п. 5.1. Будем дей-
действовать согласно рекомендациям п. 5.2. Сначала преобразуем систему
ограничений: равенство сохраним, а неравенства приводим к виду ^.
Имеем
х\ + 2x2 —
4 = 5,
4 > 2,
5.
2/1
Сопряженная задача содержит три переменные у\, г/2, уз, причем у\ мо-
может быть произвольного знака (первое условие в системе ограничений
есть равенство). Второе и четвертое условия в системе ограничений
двойственной задачи будут равенствами (на Х2 и х\ не распростра-
распространяется условие неотрицательности). Получаем (свободный член L(X)
становится свободным членом F(Y)):
F(Y) = 1 + Ъу\ + 2у2 + 52/з —> max,
у\ -\- 2у2 — Зуз ^ 1»
22/1 +У2~Уз = -2,
-2/1 - %2 + 22/з < 3,
[ 2^1 + 2/2 = -5,
2/2 ^ 0, 2/з > 0.
Пример 5.3. Дана основная задача линейного программирования
L(X) = 2х\ + 3^2 -^ max,
- Зж2 < 6,
-^2^4,
0, j = ТД
Составить двойственную задачу и решить обе эти задачи.
Решение. Основную задачу можно решить графически. Исходя
из построенного чертежа (рис. 5.1), заключаем, что задача не име-
имеет решения по причине неограниченности целевой функции в на-
направлении п в области допустимых решений задачи. Таким образом,
maxL(X) = +оо.
xeG y J

5. Двойственность в линейном программировании
71
G
1)
Рис. 5.1
Рис. 5.2
Составим теперь двойственную задачу. Она имеет вид
F(Y) = 62/1 + 42/2 -> min,
Г 2/i - 2/2 > 2,
[ -32/1 +2/2^3,
2/j > 0, j = T72.
Очевидно, что эту задачу также можно решить графически. Исходя
из построенного чертежа (рис. 5.2), заключаем, что она не имеет
решения по причине несовместности системы ограничений в области
неотрицательных значений переменных.
Пример 5.4. Для задачи линейного программирования составить
двойственную задачу и решить обе эти задачи. Сопоставить экстре-
экстремальные значения соответствующих целевых функций, а также значе-
значения основных и дополнительных переменных в основной и двойствен-
двойственной задачах.
L{X) = Ах\ + 3^2 + 2^з —> max,
Ъх\ + 8^9 + 4жз :
300,
< 200,
Решение.
1) Сначала приведем исходную (основную) задачу к каноническому
виду и решим ее симплексным методом. Очевидно, что для получения
канонического вида необходимо прибавить три дополнительные неот-
неотрицательные переменные #4, х$, х§ соответственно к первому, второму
и третьему неравенствам системы ограничений. Поэтому можно сразу

72
Гл. 1. Общее линейное программирование
обратиться к таблице Гаусса (табл. 5.1) и заполнить соответствующие
блоки.
Таблица 5.1
Х\
5
5
(ш)
4
х2
8
5
2
3
х3
4
6
5
2
х4
1
0
0
0
хъ
0
1
0
0
х6
0
0
1
0
св. чл.
400
300
200
max
0
0
1
©
4
1/5
3/2
7/2
1/2
1
0
0
0
1
0
-1/2
-1/2
1/10
300
200
20
0
0
0
1
0
11/5
1
0
0
0
0
3/14
37/14
65/35
-33/7
0
-4/7
-1/35
-11/35
0
0
1
0
0
-2/5
-1/14
-3/14
4/35
-17/70
-80
300/7
200/7
80/7
-1220/7
Таким образом, Хот = (80/7,300/7,0), Lmax = 1220/7. Значения
основных переменных равны: х\ = 80/7, х% = 300/7, х% = 0, значения
дополнительных переменных: х\ = 0, х^ = 200/7, х§ = 0.
2) Составим двойственную задачу. Это задача на минимум:
F(Y) = 400?/i + 300?/2 + 200?/з -> min,
yi + Ьу2 + 2^з > 3,
2/i + 6у2 + 5^/3 > 2,
^ > 0, j = ТД
Сначала изменяем направления неравенств системы условий задачи,
умножая каждое неравенство на —1. Затем приводим задачу к канони-
каноническому виду:
-52/1 - 52/2 - Юу3 < -4,
-82/1 - 52/2 - 22/з < -3, &
-42/1 - 62/2 - 52/з < -2
-52/1 - 52/2 - Юуз + У4 = -4,
-82/1 - 52/2 - 22/з + 2/5 = -3,
-42/1 - 62/2 - 52/з + 2/6 = -2,
2/i ^ 0, г = 176.

5. Двойственность в линейном программировании	73
Очевидно, что первое базисное решение недопустимо, а коэффи-
коэффициенты целевой функции положительны, т. е. удовлетворяют услови-
условиям оптимальности. Роль столбцов и строк этой задачи играют соот-
соответственно строки и столбцы предыдущей. Поэтому выбор ведущего
коэффициента в двойственной задаче надо выбирать, исходя из этих
условий. Дополнительный комментарий приведем в конце решения.
У\
-5
-8
-4
400
1/2
С-2
-3/2
300
0
1
0
0
У2
-5
-5
-6
300
1/2
-4
-7/2
200
3/14
4/7
-37/14
200/7
Уз
-2
-5
200
1
0
0
0
1
0
0
0
УА
1
0
0
0
-1/10
-1/5
-1/2
20
-4/35
1/35
16/35
80/7
Уъ
0
1
0
0
0
1
0
0
1/14
-1/7
-3/4
300/7
Уб
0
0
1
0
0
0
1
0
0
0
1
0
св. чл.
-4
-3
-2
min
2/5
-11/5
0
-80
17/70
11/35
33/7
1220/7
В первом блоке таблицы имеем недопустимое решение
Y\ = @,0,0,-4,-3,-2), в втором блоке — недопустимое решение
у2 = @,0,2/5,0,-11/5,0), в третьем блоке — допустимое решение
У3 = (П/35,0, 17/70,0,0,33/7). При этом F(Y3) = 1220/7. Отбрасывая
значения дополнительных неизвестных г/4, уъ и у§, получаем
оптимальное решение двойственной задачи УОпт = (П/35,0, 17/70) и
соответствующий минимум Fmin = 1220/7.
Отметим принцип выбора ведущего коэффициента в двойственной
задаче. Это делается по следующим правилам:
1)	в качестве ведущей строки берется та, в которой имеется наи-
наибольший из модулей свободных членов системы уравнений (ограниче-
(ограничений);
2)	ведущий столбец берется, исходя из минимума модулей отноше-
отношений коэффициентов индексной строки к соответствующим коэффици-
коэффициентам разрешающей строки.
Сравним последние блоки таблиц Гаусса в прямой и двойственной
задачах. Можно заметить, что коэффициенты индексной строки в оп-
оптимальном плане прямой задачи, взятые с противоположными знаками,
являются значениями переменных оптимального плана двойственной

74	Гл. 1. Общее линейное программирование
задачи. Коэффициенты индексной строки в оптимальном плане двой-
двойственной задачи являются значениями переменных оптимального плана
прямой задачи. При этом минимальное значение целевой функции
двойственной задачи равно максимальному значению целевой функции
прямой задачи.
Эти совпадения соответствуют следующему сопоставлению основ-
основных и дополнительных переменных прямой и двойственной задач:
Х\, Х2, Х%
основные
2/4, 2/5, 2/6
дополнительные
Х4, #5» Xq
дополнительные
2/ь 2/2, 2/з
основные
Таким образом, зная решение одной задачи, можно, не решая вто-
вторую задачу, найти ее решение.
Пример 5.5. Решение задачи примера 2.1.
Основная задача имеет вид
L(X) = Ах\ + 5x2 + б^з —> min>
Зж2 = 32,
ж2 + 2х3 > 40,
Х2 + Зжз < 50,
^ > 0, j = 17^.
Решение. Поскольку прямых задач было решено много, обратим-
обратимся сразу к двойственной задаче
40 50 -> max,
2/2 > 0, уз > 0.
(ограничение у\ ^ 0 отсутствует). Положим у\ = у[ —у", вводим до-
дополнительные переменные у4, у$, ув, приводим задачу к каноническому
виду и строим рабочую таблицу Гаусса (табл. 5.2).
Отбрасывая дополнительные переменные у4, уъ, Уб и определяя
ух = у[ — у'{ = 8/5, получаем решение двойственной задачи
, 1/5,0) =296/5.

у[
2
3
0
32
1/2
5/2
3/2
12
0
1
0
0
У"
-2
-3
2
-32
-1/2
-5/2
1/2
-12
0
-1
2
0
У2
4
1
-3
40
1
0
0
0
1
0
0
0
5. Вопросы
Таблица 5.2
Уз
-3
-1
0
-50
-3/4
-1/4
-9/4
-20
-7/10
-1/10
-39/20
-94/5
У4
1
0
0
0
1/4
-1/4
3/4
-10
3/10
-1/10
9/10
-44/5
Уъ
0
1
0
0
0
1
0
0
-1/5
2/5
-3/5
-24/5
Уб
0
0
1
0
0
0
1
0
0
0
1
0
7Ь
св. чл.
4
5
6
max
1
4
9
-40
1/5
8/5
33/5
-296/5
Имея в виду связь переменных прямой и двойственной задач,
получаем
bminPO = Д44/5,24/5,0) = 296/5.
Ответ: Fmax(y) = F(8/5, 1/5,0) = 296/5, Lm[n(X) =
= ?D4/5,24/5,0) =296/5.
Вопросы
5.1.	Можно ли для задачи ЛП, содержащей в системе ограничений
неравенства разных направлений, построить двойственную задачу?
5.2.	Если в основной задаче отсутствуют условия неотрицатель-
неотрицательности переменных, то какие последствия это влечет в сопряженной
задаче?
5.3.	Чем отличаются матрицы систем ограничений в паре двой-
двойственных задач?
5.4.	Какова связь между экстремальными значениями пары двой-
двойственных задач ЛП?
5.5.	Что можно сказать о решении двойственной задачи, если
решение основной задачи не существует по причине несовместимости
ее системы ограничений?
5.6.	Можно ли производить симплексное преобразование, исполь-
используя отрицательный разрешающий коэффициент?

76
Гл. 1. Общее линейное программирование
5.7. Могут ли обе двойственные задачи быть задачами на макси-
максимум.^
Упражнения
Построить двойственные задачи.
5.1.
5.2.
5.3.
5.4.
5.5.
L(X) = х\ + 2^2 — 3^4 —> max,
2х\ - Зх2 + 4ж3 + ж4 < 12,
Ж1 - 2х3 + Зж4 < 10,
-Х\
9,
0, j = Т4.
min,
2^3 ^ 6,
Зх\
0,
Ю,
= 10
Х\
0, j = 1,4.
\х3 -хБ = 3,
0,
0, х4 > 0,
min,
—Xi + Ж2 + Хз — Х4 = О,
Зх\ +3ж2 + ж3 +ж4 = 12,
Xj > 0, j = Т~4.
* max,

5. Упражнения
77
5.6.
5.7.
L(X) = А-2х2- Sx3 + 4ж4 - хъ -> min,
—	3^4 = 16,
—	2^4 — 7х$ = 10,
жз — 3^4 — 2х$ = —6,
Х2 — 2хз -\- Х4 — х$ = 18,
xj ^ 0, j = 175.
= -2х\
3 -^ min,
5.8.
-7,
—Х\ + Х2
^ > о,
6,
L(X) = \х\ - \Х2 + 4ж3 - 5ж4 —> min,
!6xi + 2^2 — Зжз + 4^4 = 15,
2х\ + Зж2 - 4ж3 + 5ж4 = 19,
Xj ^ 0, j = Т~4.
Для каждой из следующих задач линейного программирования
составить двойственную задачу и решить обе эти задачи.
5.9.
5.10.
L(X)
[
\
f-x
I 2xx
= 2x{
2xi-
-xi-
i >0,
f х2Л
-X2
+ 3^2 -^ max,
ж2 < -2,
- Ж2 < -6,
x2 >0.
2х2-хъ-
•2 - 2x3 <
-2x3 < 17,
+ 2хз = 4,
> max
12,
х, > 0, j = ТД

78	Гл. 1. Общее линейное программирование
5.11.	L(X) = —2х\ + Х2 — Зжз + 2^4 + 10^5 + 6 —> min,
Х\ — Х2 + 2^3 — 2^4 — 6^5 = 2,
Х\ + 2^2 — Хз + 7^4 + 3^5 = 5,
—Х\ -\- Х2 ~\- Хз — Х4 = 4,
5.12.	L(X) = Ъх[ - Х2 - 4жз —> min,
kjJu\ \^ «^2 ^^ ^3 — '
5.13.	^РО — 14^1 — 26^2 — 16жз + 20^4 -^ min,
Г xi — ^2 — Зжз + 2^4 = 15,
I Х\ — 2^2 — Хз + Х4 = Ю,
Xj >0, j = 1,4.
5.14.	-^РО = 7^1 — 42^2 + 14жз — 7x4 + 21^5 -^ max,
-2х\ -\- Х2 -\- хз =2,
jju\ \^ KJJU2 \^ Jo4 — ^^,
С\ — 2^2 +Ж5 = 4,
5.15.	-^(-^) = ~х\ -\- Х2 -\- 5жз + 2^4 + #5 "^ mm'
!Xi + #2 "~ ^3 "~ Х4 — ХЪ — "~ 15,
5.16.	-^(-^) = 4х\ + 14^2 -^ max,
Г 2ж1 -Зж2 > -12,
хх > 0, х2 > 0.

5. Упражнения	79
Для каждой из следующих задач составить двойственную и, решая
одну из них, найти решение обеих задач.
5.19.
5.17.	L(X) = 8x\ + 6x2 + 5жз —> max,
1053,
< 1170,
325,
^ >0, j = 1,3.
5.18.	L(X) = 6х\
2х\ — Х2 + х% — 3^4 = 6,
5.20.	L(X) = 2x\ — X2 + ЗЖ4 + 2^5 + 4 —> max,
-x\ + 2x2 + ЗЖ4 = 4,
5.21.	L(X) = 4xi + 5ж2 + 6ж3 -> max,
xi + Зж2 + 6ж3 < 240,
ж1 +ж2 + 2ж3 < 100,
ж1 + Зж2 + 4ж3 < 80,
xj ^ 0, j = U.

80	Гл. 1. Общее линейное программирование
5.22.	L(X) = 6xi + 5ж2 + 4ж3 -> max,
6xi + Зж2 + 2ж3 < 240,
4ж1 +2ж2 + 4ж3 < 100,
8х{ +6ж2 + 4ж3 < 160,
^ >0, j = 1,3.
5.23.	L(X) = 100 + 4х\ + 5ж2 + 6ж3 - 5ж4 -^ max,
xi + Зж2 + 6х3 + ж4 = 100,
ж1 + 2ж2 + 4ж3 < 200,
xi + Зж2 + 4ж4 < 60,
Xj > 0, j = Т~4.
5.24.	L(X) = xi - ж2 - Зж3 -^ min,
^1 — Ж2 +Ж3 ^ 1,
ж1 -2ж2 +ж3 > -2,
^1 +жз < 5,
Xj > 0, j = Т7^.
5.25.	L(X) = х\ — Х2 — х% + Х4 — 2х$ + Жб -^ min,
+ 2^4 — 3^5 — 2^6 = 5,
+ 3^4 — 2^5 — 4^6 = 6,
- 4ж4 - ж5 + 2xQ = 3,
^ ^ о, j = Т7б.
5.26.	-^(-^) = —2^1 — 8ж2 — жз — 5^4 -^ max,
-Зх3+х4 > 18,
4ж3 + 2ж4 > 24,
+ 4ж2 + 2жз — 3^4 ^ 30,
Xj >0, j = 1,4.
5.27.	L(X) = -2хх +х2- Зх3 + 2ж4 + 10ж5 + 6 -> min,
xi — ж2 + 2жз — 2^4 — 6^5 = 2,
х\ + 2ж2 — жз + 7^4 + 3^5 = 5,
—Х\ + Х2 + Х% — Х4 = 4,
Xj ^ О, j = Цэ.

5. Упражнения
81
5.28.
L(X) = х\
extr,
хз + х\ = 2,
^з — х\ = 8,
j >0, j = 1,4.
5.29.
extr,
хх
5.30.
^2 ^ 3,
2 < 13,
2 >3,
ж2 < 6,
Xj ^ 0, j = ТД
—#1 + 3^2 +^4 = 13,
2х\ — Х2 +^5 = 9,
#1 + 4^2 — xq = 9,
^ ^ о, j = Т7б.
- 42 -> extr,
5.31.
= х\ —
extr,
2 — Хз = 16,
0,
0,
= 3,
4 ^ 0.
5.32.	Производственная мощность сборочного цеха составляет
60 изделий типа Аи 180 изделий типа Б в сутки. Технический
контроль пропускает в сутки 100 изделий того или другого типа (без-
(безразлично). Изделия типа А вчетверо дороже изделий типа Б. Требуется
спланировать выпуск готовой продукции так, чтобы предприятию была
обеспечена наибольшая прибыль.
5.33.	Для изготовления изделий двух видов склад может отпустить
металла не более 150 кг, причем на изделие 1-го вида расходуется
5 кг, а на изделие 2-го вида — 3 кг металла. Требуется спланировать
производство так, чтобы была обеспечена наибольшая прибыль, если
изделий 1-го вида требуется изготовить не более 20 штук, а изделий
2-го вида — не более 25 штук, причем одно изделие 1-го вида стоит
7 руб., а 2-го вида — 8 руб.

82
Гл. 1. Общее линейное программирование
5.34. Для откорма животных употребляют два вида кормов. Сто-
Стоимость 1 кг корма 1-го вида — 20 руб., а корма 2-го вида — 25 руб.
В каждом килограмме корма 1-го вида содержится 5 единиц питатель-
питательного вещества А и 4 единицы питательного вещества Б, а в каждом
килограмме корма 2-го вида — соответственно 3 и 12 единиц. Какое
количество корма каждого вида необходимо расходовать ежедневно,
чтобы затраты на откорм были минимальными, если суточный рацион
предусматривает не менее 150 единиц питательного вещества типа А
и не менее 180 единиц питательного вещества типа Б?
Ответы
5.1.
5.2.
5.3.
= 122/1 +
' 2j/i + у
-3yi +
Юу2 + Ууз —> min,
г~Уз^ 1,
Уз >%
4j/i - 2у2 + Зу3 ^ 0,
2/1 +3у
) = 6у, -
m+sy2,
2yi - 2у2
-Уч.- 2уз
= 10 + 3yi
У\ + Зу2
2yi - уз
Зг/i - 2У
-У\ + 2у
2^-3,
?/2 + IO2/4 -^ max,
- 2^з + 2/4^3,
+ З2/3 + 2/4^2,
+ 2/4^0,
+ 9^/2 + 42/з -> min
-42/з>1,
= -2,
2 + З2/3 > 3,
>2,
/2 + 3?/з > -1,
, у3 > 0.
5.4.
F(Y) = Ayx + 72/2 -
max,

5. Ответы
83
5.5.
5.6.
5.7.
5.8.
2/1 + 4^/2 - 2уз < 3,
22/i - 4у2 + З^з < 2,
-32/1 -2/3 = -1,
) = 122/2 -> max,
-2/1 + З2/2 < 0,
2/1 + Зу2 < -2,
2/1 + 2/2 < -1,
-2/1 +2/2^1-
F(Y) = 4 + I62/1 + Ю?/2 - 62/3 + 18y4 ^ max,
( З2/1 +4?/2 -52/4 > 1,
-2/1 - 2/2 - 22/3 - 52/4 < -2,
22/1 + З2/2 + Уз ~ 2y4 < -3,
-32/1 -2^2-3^3 + 4^^4,
max,
F(y) = 3 + 2/1 + 72/2 + 62/3
2/1 + 22/2 - 2/3 < -2,
-З2/1 -4?/2 + 4?/з < 1,
22/1 - 2/2 + Зуз < 6,
2/2 > 0, 2/3 > 0.
F(Y) = 152/i + 192/2 -> max,
f 62/1 + 2^/2 < 4,
22/1 + З2/2 < -4,
-З2/1 - 42/2 < 4,
42/i + 52/2 < -5.
5.9.	maxL(X) = +00. Двойственная задача не имеет допустимых
решений.
5.10.	Lmax = LD,4,0) = 12.
5.11.	Lmin = L(l,3,2,0,0) = 1.
5.12.	Lmin = LC,9, 12) = -48.

84	Гл. 1. Общее линейное программирование
5.13.	Lmin = LB0,5,0,0) = 150.
5.14.	Lmax = L(8,2, 16) = FA4,2, 31) = 196.
5.15.	Lmin = L@,0, 5, 10,0) = F(-3/2, -2) = 45.
5.16.	Lmax = 1,A2/5,28/5) = FB, 8) = 88.
5.17.	Lmax = LE7,0,40) = 656.
5.18.	Lmax = LD0,0,57) = 696.
5.19.	Lmax = ?(8,0,11,7,0) = 6.
5.20.	Lmax = LB2/13, 34/13,0,2/13,0) =68/13.
5.21.	Lmax = LD0,0,0) = 160.
5.22.	Lmax = L@,0,40) = 160.
5.23.	Lmax = LC0,0,0,40) = 20.
5.24.	Lmin = L(l/3, 11/3, 1/4) = -46/3.
5.25.	Lmin = -oo.
5.26.	Lmax = L@, 12,0,6) = -126.
5.27.	Lmin = L(l,3,2,0,0) = 1.
5.28.	Несовместные ограничения задачи.
5.29.	Lmin = L@, 13/2) = -13/2; Lmax = LE1/7,20/7) = 19.
5.30.	Lmin = L(l,2,0,8,9,0) = 11; Lmax = L(8, 7, 16,0,0,27) =61.
5.31.	Lmin = L@, 19/8,-10/3,43/3,0) = -106/3; Lmax = @,0,
-93/24,287/24, 19/24) = -253/12.
5.32.	Lmax = LF0,40) =
5.33.	A5,25); Lmax = 305.
5.34.	B6,25; 6,25); Lmin = 681,25.

Глава 2
ТРАНСПОРТНАЯ ЗАДАЧА
§ 6. Постановка транспортной задачи
6.1. Имеются т пунктов отправления однородного груза А\, А2, ...,
Аш и п пунктов назначения того же груза В\, В2, ..., Вп. Предполага-
Предполагается, что из любого пункта Ai (i = 1,га) груз может быть доставлен в
любой пункт Bj (j = l,n). Обозначения:
ai > О — объем (запас) груза в пункте А^
bj > 0 — объем груза, необходимого в пункте Bj]
Cij ^ 0 — стоимость (тариф) перевозки единицы груза из Ai в Bj.
Требуется определить план перевозок груза из пунктов Ai в пунк-
пункты Bj так, чтобы:
1)	вывезти весь груз от отправителей А^
2)	удовлетворить потребность в грузе (спрос) каждого потребите-
потребителя Bj]
3)	транспортные расходы были минимальными.
Под планом задачи подразумевается матрица
Х\\ Х\2 ... Х\п \
X =
\
где Ху — количество единиц груза, который необходимо перевезти из
точки Ai в точку Bj.
Математическая модель сформулированной задачи, называемой
транспортной задачей, имеет следующий вид:
требуется найти неотрицательную матрицу X, удовлетворяющую
условиям
j=\	г=1

86	Гл. 2. Транспортная задача
и доставляющую минимум целевой функции
j=l i=\
где Су • Ху — транспортные расходы по перевозке Ху единиц груза из
пункта Ai в пункт Bj.
Теорема 6.1. Для разрешимости транспортной задачи необхо-
необходимо и достаточно, чтобы имело место условие баланса
ъ=\	j=l
6.2.	Неотрицательная матрица X, удовлетворяющая условиям зада-
задачи называется планом (или допустимым планом) задачи. Допустимый
план называется оптимальным, если он доставляет минимум целевой
функции.
Допустимый план, имеющий не более т + п — 1 отличных от нуля
компонентов Ху, называется базисным, или опорным. Опорный план,
имеющий ровно т + п — 1 отличных от нуля компонент, называется
невырожденным, а если число отличных от нуля компонент меньше,
чем т + п — 1, то план называется вырожденным.
Прежде чем приступить к решению транспортной задачи, необхо-
необходимо проверить условие теоремы 6.1. Если задача с неправильным
балансом (открытая), то:
т	п
1)	при У^сц > y^fy (спрос меньше предложения) необходимо
i=\	j=\
т	п
ввести «фиктивного» потребителя груза: Ъп+\ = У^сц — У^^'5
i=\	j=\
т	п
2)	при 2_\аг < У^bj (спрос больше предложения) необходимо
г=1	j=l
п	т
ввести «фиктивного» поставщика груза: am+i = 2_\h ~ /_\ai'
j=l	i=l
Стоимости перевозок от «фиктивного» поставщика до всех потре-
потребителей и от любого поставщика до «фиктивного» потребителя прини-
принимаются равными нулю.
6.3.	Решение задачи начинается с определения начального опорного
плана. Начальный и последующие планы заносятся в распредели-
распределительную таблицу, в которой заранее записываются исходные данные
задачи. Таблица с внесенными пунктами отправления Ai, их запа-
запасами ai, пунктами назначения Bj, их запросами bj и тарифами пу
(г = 1,2,... ,т; j = 1,2,... ,п) имеет вид таблицы 6.1.

6. Постановка транспортной задачи
87
Таблица 6.1
м
А2
Ат
Спрос
Б,
СП
С21
Ъх
в2
С\2
С22
ст2
ь2
вп
с2п
ьт
Запас
а\
а2
ат
Тарифы Су записаны в левом верхнем углу клетки, а величины
поставок Ху будут записываться в правом нижнем углу клетки.
Примечание. При введении «фиктивного» потребителя Вп+\ (по-
(поставщика Ат+\) соответствующий столбец (строка) заполняется нуля-
нулями, Т.е. Q,n+i = 0 (Cm+ij = 0).
Начальный план составляется методом минимальных тарифов, ко-
который заключается в следующем. Выбирается наименьший тариф, ска-
скажем, Су. В клетке (i,j) этого тарифа (в правом нижнем углу) за-
записывается максимально возможная поставка с учетом ограничений
этой строки и этого столбца: Ху = min(a^, fy). Этой поставкой либо
обеспечивается потребность одного потребителя, и тогда этот потре-
потребитель (столбец) исключается из дальнейшего рассмотрения, либо от
одного поставщика забирается весь груз, и тогда этот поставщик (стро-
(строка) исключается из дальнейшего рассмотрения. Исключаемый столбец
(или строка) нумеруется, и этот номер записывается на краю этого
столбца (или строки). Исключаемые одновременно строка и столбец
отмечаются одним номером.
Если имеются два или более одинаковых наименьших тарифов, то
заполняемая клетка берется произвольно среди них.
Описанная операция повторяется до тех пор, пока не будут за-
зачеркнуты все столбцы и строки. На последнем шаге одновременно
освобождаются строка и столбец, а следовательно, в благоприятном
случае должно быть т + п — 1 заполненных клеток. Полученный такой
план является невырожденным.
Примечание. При одновременном зачеркивании строки и столбца
(кроме последнего шага) число заполненных клеток меньше, чем т +
+ п— 1, и такой план является вырожденным. Его надо дополнить
до невырожденного плана нулями: нули надо записать в клетки,

Гл. 2. Транспортная задача
расположенные в строке или в столбце, которые одновременно исклю-
исключены из рассмотрения, т.е. имеют один номер. При этом, клетки, запол-
заполненные нулями, не должны составлять цикл с прочими заполненными
клетками (понятие цикла см. ниже).
Подчеркнем, что начальный план записывается в распределитель-
распределительной (первоначальной) таблице, и соответствующие поставки отделяют-
отделяются уголками для зрительного контраста.
В таблицах 6.2 и 6.3 показаны примеры невырожденного и вы-
вырожденного планов (в обеих таблицах т = 3, п = 4, т + п— 1=6;
при этом на дополнительные строку и столбец обращать внимание не
следует — о них позже).
Таблица 6.2
1)	2)	6)	5)
3)
4)
5)
Число положительных компонент начального плана равно
т + п — 1 = 6.
План невырожденный.
Таблица 6.3
1)	2)	5)	4)
3)
4)
5)
90
100
90
70
1
70
4
3
1
60
5
1
60
3
-2
80
6
3
5
80
2
70
1
4
4
20
40
10
1
щ
0
3
3
90
100
80
70
1
70
4
3
60
5
1
60
3
80
6
3
5
80
70
1
20
4
50
6

6. Постановка транспортной задачи
Число положительных компонент начального плана равно пяти. При
заполнении таблицы одновременно зачеркнуты вторая строка и четвер-
четвертый столбец. План вырожденный. Отмеченная уголком и звездочкой
клетка должна заполняться нулем (о роли звездочек см. ниже в п. 6.5).
6.4. После получения первого (начального) плана следует опреде-
п т
лить стоимость его реализации: L(X) = У^У^с^а^. Затем план про-
j=\ г=\
веряется на оптимальность методом потенциалов, который заключается
в следующем. Потенциалами данного плана называется набор изш + п
действительных чисел щ (г = 1,га) и Vj (j = l,n), удовлетворяющих
условиям щ + Vj = Су, где Су — тариф занятой клетки. Поскольку
число занятых клеток равно т + п — 1, то для однозначного опреде-
определения потенциалов один из них можно брать произвольно, например,
щ = 0. Потенциалы записываются в дополнительных строке и столбце.
Как правило, потенциалы определяются в уме. Именно эти потенциалы
занесены в табл. 6.2. Здесь мы приняли щ = 0. Остальные потенциалы
находятся последовательно следующим образом:
щ +v\ = с\\ = 1 (v\ = 1, так как щ = 0);
^1+^4= С\4 =1	(^4 = 1M
г^з +v4 = с34 = 4 (г^3 = 3);
^з + ^з = сзз = 5 (г^3 = 2);
Щ + V2 = С22 = 1	(Щ = —2).
Полученная система потенциалов позволяет проверить получен-
полученный план на оптимальность. Составляем разности Ау = Су — щ —
— Vj, для всех клеток таблицы. Поскольку для занятых клеток
Ау = 0 (по определению), то остается найти Ау для незанятых клеток.
Эти величины (числа) называются оценками клеток распределительной
таблицы, или плана.
Теорема 6.2 (теорема оптимальности). Опорный план X оптима-
оптимален в том и только в том случае, если среди оценок Ау- этого плана
нет отрицательных.
Если среди оценок А^- есть отрицательные, то план неоптимален
и его улучшают методом перераспределения поставок по циклу. Отме-
Отметим клетку с наименьшей отрицательной оценкой и построим цикл с
начальной вершиной в этой клетке.
6.5. Циклом с начальной вершиной в данной клетке называется
замкнутая ломаная, обладающая следующими свойствами:
1)	все ее вершины, кроме начальной, расположены в занятых
клетках;
2)	звенья (стороны) цикла расположены в строках и столбцах
таблицы;

90
Гл. 2. Транспортная задача
3)	в каждой вершине звенья соединяются под прямым углом;
4)	на звеньях цикла могут быть занятые клетки, но они не являются
вершинами цикла;
5)	два звена могут пересекаться в какой-либо клетке, но эта клетка
не должна быть занятой (иначе она является вершиной).
Примечание. Свойства 4 и 5 обеспечивают некоторую минималь-
минимальность цикла: он не должен распадаться на объединение двух или более
меньших циклов.
На рис. 6.1 изображено несколько циклов с началом в незанятой
клетке (именно такие циклы встречаются при исследовании плана на
оптимальность). Приняты обозначения: О — незанятая клетка (начало
цикла), ^ — занятая клетка; возможные места расположения занятых
клеток отмечены черным кружком на звеньях.
II
«	•—
i	•	s
О
II
Рис. 6.1
На рис. 6.2 изображено несколько замкнутых ломаных, не явля-
являющихся циклами: «так нельзя». Штриховыми линиями обозначены
возможности сокращения цикла или распада цикла на объединение
(сумму) нескольких циклов. Рис. 6.2 показывает, что в цикл нельзя
вовлекать «больше, чем надо» клеток.
о.
	*
Q	J
«	*!
Рис. 6.2

6. Постановка транспортной задачи	91
Примечание. Вспомним случай вырожденного плана и обратимся к
таблице 6.3. Для того чтобы план стал невырожденным, надо занять
одну клетку нулем (иначе нельзя определить потенциалы, а значит,
нельзя проверить на оптимальность полученный план). Нуль можно
записать либо в строке г = 2, либо в столбце j = 4, ибо они были
исключены одновременно в четвертую очередь (именно для этого была
нужна нумерация исключаемых строк и столбцов). В клетке B, 1), ко-
которая отмечена звездочкой, записать нуль нельзя: эта клетка образует
цикл с занятыми клетками A, 1), A,4) и B,4). Можно было занимать
либо клетку C,4), либо B,3), которые тоже отмечены звездочками.
Последняя клетка и была занята и отмечена уголком, хотя в качестве
занятой можно было бы брать и клетку C,4).
6.6. Итак, построен цикл с вершиной в отмеченной клетке с наи-
наименьшей отрицательной оценкой. Если таких клеток несколько, то сле-
следует брать одну из них произвольно, или клетку с меньшим тарифом.
В любом порядке перенумеруем вершины цикла. Тем самым вершины
разбиваются на две группы — с нечетными (отмеченная считается
первой, т.е. нечетной) и четными номерами. Найдем наименьшую из
величин поставок четных вершин (обозначим ее буквой в). Эту вели-
величину прибавим ко всем вершинам с нечетными номерами и отнимем
от вершин с четными номерами. Новое распределение поставок присо-
присоединяется к остальным занятым клеткам; таким образом, составляется
новый опорный план Х^ с L{X^) < L{X\). Этот план заносится в
новую таблицу и проверяется на оптимальность методом потенциалов.
В новой таблице необязательно записывать величины а^ и bj.
Улучшение новых планов проводят до тех пор, пока очередной план
не станет оптимальным. Для него все оценки клеток должны быть
неотрицательными. Цикл и перераспределение поставок рекомендуется
выносить за таблицу, т.е. рассматривать их отдельно. При заполнении
клеток тарифами, поставками, оценками рекомендуется для контраста
использовать разные цвета, а цикл в таблице выделять отдельным
цветом и штриховой линией.
Пример 6.1. Решить транспортную задачу по данным таблицы 6.2.
Решение. Перепишем здесь таблицу 6.2, опуская величины а^ и
bj. При этом буквы щ, Vj перенесем в правый нижний угол расширен-
расширенной таблицы (табл. 6.4).
1) Проверяем составленный план, взятый из таблицы 6.4 (заметим,
что он составлен из поставок, записанных в правом нижнем углу
клеток и отмеченных уголком),
70 0 0 30
Хх = | 0 60 0 40
0 0 80 10

92
Гл. 2. Транспортная задача
Таблица 6.4
1
0
70
4
0
3
-1
1
5
7
1
0
60
3
2
-2
6
3
5
4
i
0

80
2
1
4
—
А
0
0
0
20
40
10
1
0
3
3
на оптимальность, вычисляя оценки всех клеток таблицы. Для этого
оценки Ау = Су — щ — Vj, равные нулю для занятых клеток, вычислим
для всех незанятых клеток и результаты запишем в центре клетки. Эти
оценки уже занесены в таблицу, а теперь укажем способ их получения
(конечно, это надо делать в уме):
= С\2 — Щ — V2 = 5 — 0 + 2 = 7,
Ai3 = ci3 - щ - v3 = 6 - 0 - 2 = 4,
A21 — C21 — U2 — v\ — 4 — 3 — 1 = 0,
A23 = c23 - ^2 - ^з = 3 - 2 - 3 = -2 < 0 (!),
A3i =c3i -1x3-vi =3- 1 — 3 = —1 <0 (!),
A32 = C32 - ^3 - v2 = 3 - 3 + 2 = 2.
Подчеркнем, что если (г, j) — занятая клетка, то Ау = 0.
Получили две клетки с отрицательным оценками:
А31=-1, А23 = -2.
III
План неоптимален, будем его улучшать. Но
прежде определим стоимость реализации этого
плана:
L(X{) = 70 • 1 + 20 • 1 + 60 • 1 + 40 • 4+
+80-5+10-4 = 750 (ден. ед.).
2) Строим цикл с началом в отмечен-
отмеченной клетке B,3) с минимальной оценкой
А23 = -2.

6. Постановка транспортной задачи
93
Для его пересчета выносим цикл отдельно. Минимальная поставка
по четным вершинам равна в = 40. Эту величину вычтем из вершин
с четными номерами и прибавим к вершинам с нечетными номерами.
Старые поставки записаны вне цикла, а новые — внутри него. Клетка
B,3) была свободной, сейчас стала свободной клетка B,4).
3) Строим новую таблицу (табл. 6.5), в которую заносим новый
план, состоящий из старых поставок, не вовлеченных в цикл, и но-
новых — в вершинах рассмотренного цикла.
Таблица 6.5
1
г
О1
! 70
4 ;
2|
3 0
-1
1
5
5
1
0
60
_з
0
0
6
4
3
0
40
5
0
40
-2
1
¦0
! 20
4 ;
12
4._!
0
50
1
0
1
3
Этот план имеет вид
/70 0 0 20
Х2 = 0 60 40 0
V 0 0 40 50
и его стоимость равна
F(X2) = 70 • 1 + 20 • 1 + 60 • 1 + 40 • 3 + 40 • 5 + 50 • 4 = 670 (ден. ед.).
В таблицу 6.5 помещены также новые потенциалы, найденные при
условии щ = 0.
Определим оценки всех клеток (хотя на
самом деле они также присутствуют в таб-
таблице). Наличие одной отрицательной оценки
Аз1 = —1 означает, что этот новый план еще
не оптимальный. Замкнутый цикл с вершиной в
клетке C, 1) также отмечен в таблице 6.5. Его
пересчет произведем отдельно.
На этот раз перераспределяем поставку в
в = 50, это приводит к поставкам, обозначенным
внутри цикла.
50
IV

94
Гл. 2. Транспортная задача
4) Составляем новый план, заносим его в новую таблицу (табл. 6.6),
опять определяем новые потенциалы, новые оценки и делаем вывод об
оптимальности.
Таблица 6.6
1
0
20
4
3
3
0
50
-1
5
4
1
0
60
3
0
-1
6
3
3
0
40
5
0
40
-3
1
0
70
4
3
4
1
-1
0
0
-2
Отрицательных оценок нет: план оптимален. Его стоимость равна
L(X2) = 20 + 70 + 60 + 120 + 150 + 200 = 620 (ден. ед.).
Ответ:
20 0 0 80 \
Х3= \ 0 60 40 О
50 0 40 О
L(X3) = 620.
Задача решена.
Примечание 1. Визуально проанализируйте этот план, сравните его
с начальным и обнаружите преимущества оптимального плана.
Примечание 2. При пересчете стоимости нового плана можно огра-
ограничиться пересчетом только тех поставок, которые участвовали в цик-
цикле. Экономия на цикле переносится на весь план. Это важно, когда
задачи, а значит, и таблицы, громоздкие. Иногда в цикл может быть
вовлечена значительная часть заполненных клеток.
Пример 6.2. Решить задачу, заданную табл. 6.3.
Решение. Перепишем здесь эту таблицу с клеткой B,3), запол-
заполненной нулем (табл. 6.7). Занятая клетка нужна для того, чтобы можно
было определить потенциалы. Потенциалы определяем в уме и заносим
в эту же таблицу:

6. Постановка транспортной задачи
95
=0, Щ + V4 = 1 => V4 = 1,
v\ + г^2 = 3 => г^2 = 2,
^2 + ^2 — 1 =^ ^2 — — 1 >
^1+^1 = 1 =Ф г?! = 1,
^2 + ^з = 4 => ^з = 2,
^з + ^з = 5 => г^3 = 3.
Таблица 6.7
1
г
О1
I 70
4 ;
Ц
/Г}
-1
1
5
6
1
0
60
_з
1
-1
6
4
4
! о
5 !
0
80
2
1
¦0
! 20
з J
0
50
6
2
1
0
2
3
Продолжим вычисления оценок всех незанятых клеток, а в табли-
таблице 6.7 запишем их в центрах клеток:
= 5-0+1=6, Ai3 = 6-2-0 = 4,
A2i =4-1-2=1, Л31 = 3 — 3 — 1 = —1,
А32 = 3-3+1 = 1, А34 = 3 - 3 - 1 = 2.
Имеем одну отрицательную оцен-
оценку. План неоптимален. Сначала опре-	VI
делим его стоимость, затем построим 70
цикл.
70 0 0 20
Хх = | 0 60 0 50
О 0 80 О
L(XX) = 700.
VI
20
50
©—
50
ттт
III
30
0
80
20
70
О
50
V
IV
II

96
Гл. 2. Транспортная задача
В цикл вовлечены почти все занятые клетки (кроме одной);
О = min(80, 50, 70) = 50.
После перераспределения поставки в в = 50 ед. получили невы-
невырожденный план, в нем имеем шесть отличных от нуля компонент,
тогда как в первом вырожденном плане было пять отличных от нуля
компонент.
Новый план заносим в новую таблицу (табл. 6.8), оценки клеток
показывают, что план оптимален.
Таблица 6.8
1
0
20
4
2
3
0
50
1
5
5
1
0
60
3
1
0
6
3
4
0
50
5
0
30
3
1
0
70
3
1
6
3
1
0
1
2
Ответ:
20 0 0 70
X, = I 0 60 50 0
50 0 30 0
г) = 650 (ден. ед.).
и стоимость равна
Пример 6.3. Решить задачу, заданную таблицей 6.9.
Таблица 6.9
40
30
90
40
3
5
3
20
2
6
4
30
3
7
1
60
4
5
2

6. Постановка транспортной задачи
97
Решение. Проверяем задачу на условие правильности баланса
(см. теорему 6.1). Имеем
з
v—>
г=\
аг = 40 + 30 + 90= 160,
= 40 + 20 + 30 + 60 = 150.
Задача открытая: она неразрешима в такой постановке.
Вводим «фиктивного» потребителя с потребностью Ъ$ = 10 и при-
принимаем Q5 = 0, г = 1,3.
Составим распределительную (транспортную) таблицу для новой
закрытой задачи (табл. 6.10). В ней построим первоначальный план,
определим его стоимость, вычислим потенциалы и проверим план на
оптимальность.
Таблица 6.10
40
30
90
vi
3
5
3
Ь)
40
20
20
0
3
2
20
20
6
4
2
1)
30
3
7
1
30
1
3)
60
4
5
2
60
2
10
0
0
10
0
-2
щ
0
2
0
4)
5)
3)
«Фиктивный» потребитель (или отправитель, если он был), рас-
рассматривается в последнюю очередь.
1) Определим начальный план. Минимальный тариф сзз = 1. По-
Положим жзз = minC0,90) = 30 и запишем эту поставку в клетке C, 3)
минимального тарифа. Столбец j = 3 зачеркнем под номером 1.
Минимальные тарифы с\2 = С34 = 2. Положим х\2 = 20, зачеркнем
под номером 2 столбец j = 2. Далее возьмем ж34 = 60 и одновременно
зачеркнем строку j = 3 и столбец j = 4 под номером 3. Учитывая с\\ =
= 3, запишем х\\ = 20 и зачеркнем строку г = 1 под номером 4.
Следующая поставка х^\ = 20 очевидна, и в последнюю очередь
рассматриваем «фиктивного» потребителя, записывая х^ъ = Ю. План,
как видим, вырожденный, потому что на третьем шаге зачеркнули две
линии (под линией понимается либо строка, либо столбец). В одну из
них запишем нуль, т.е. занимаем одну клетку либо в третьей строке,
4 К. Н. Лунгу

98	Гл. 2. Транспортная задача
либо в четвертом столбце так, чтобы она не составляла с другими
занятыми клетками замкнутый цикл. Из нескольких возможностей
выбираем х%\ = 0, потому что на момент зачеркивания этих линий в
столбце j = 1 сохранилась потребность в 20 ед. Полученный таким
образом начальный план вырожденный, но занятых клеток имеем нуж-
нужное количество: т + п — 1 = 7.
2) Потенциалы занятых клеток определим, исходя из начального
условия щ = 0. Остальные потенциалы определим без труда и занесем
их в эту же таблицу. Также в уме обнаруживаем, что среди оценок
отрицательных нет.
Первоначальный план
20 20 0 0 0
X = | 20 0 0 0 10
0 0 300 60 0
в котором «фиктивный» потребитель участвует, является оптимальным,
и стоимость этого плана равна
F(X) = 20 • 3 + 20 • 2 + 20 • 5 + 30 • 1 + 60 • 2 + 10 • 0 = 350.
Задача решена. Остается исключить «фиктивного» потребителя, не
влияющего на стоимость оптимального плана задачи.
Ответ:
20 20 0 0
X = | 20 0 0 0 | , F(X) = 350.
0 0 300 60
Вопросы
6.1.	Чем отличаются друг от друга транспортные задачи с правиль-
правильным и с неправильным балансом?
6.2.	В чем состоит метод наименьших тарифов построения началь-
начального решения (плана)?
6.3.	Чем отличается вырожденное решение от невырожденного?
Когда появляется то или другое?
6.4.	Можно ли проверять на оптимальность вырожденное решение?
6.5.	Каким образом получить невырожденное опорное решение?
6.6.	Как строится цикл? В чем состоит его математический смысл?

6. Упражнения
99
6.7.	Как проверить на оптимальность полученное опорное решение?
6.8.	Как улучшить неоптимальное решение транспортной задачи?
6.9.	Может ли транспортная задача иметь два решения? бесконечно
много решений?
6.10.	Каким образом решить открытую транспортную задачу?
Упражнения
Решить транспортные задачи, заданные таблицами 6.11-6.16.
6.1.
6.2.
6.3.
Таблица 6.11
Аг\
60
80
100
40
1
4
2
60
3
5
3
80
4
8
6
60
2
3
1
Таблица 6.12
200
150
130
170
150
3
9
1
6
140
7
2
5
4
190
2
1
7
8
Таблица 6.13
54
32
85
162
100
12
8
6
10
70
14
11
10
4
35
26
11
10
4
45
16
22
21
8
50
3
10
15
9

100
Гл. 2. Транспортная задача
6.4.
6.5.
6.6.
Таблица 6.14
60
36
90
84
20
18
8
4
9
10
2
2
3
4
60
8
3
5
16
30
3
12
7
5
70
2
4
14
8
Таблица 6.15
Аг \
222
188
210
300
125
20
10
2
3
75
18
10
17
9
200
11
5
8
17
380
8
2
4
8
220
3
4
3
4
Таблица 6.16
Ai\
180
160
120
40
100
3
5
6
12
130
8
3
5
9
150
5
6
7
10
60
6
8
3
8
60
7
7
4
12
Решить транспортные задачи, в которых заданы векторы запасов А
и запросов В и тарифные матрицы С.
6.7.	А = C0,40,90),	В = D0,20, 30,60),
3	6 7 2
С= I 5	4 1 5
7	3 3 4

6. Упражнения
101
6.8.
6.9.
6.10.
6.11.
А = D00, 300,900), В = D00,200, 300, 600),
А= A8,24,30), В = A2,18,24,18),
А = D0,40, 80), В = G0,20,60,60),
А = A00,250,300), В = A40,80, 120,240),
6.12.
А = B22, 188,210, 380), В = A25, 75,200, 380,220),
С =
I 20 12 10 8 3 \
7 7 5 2 4
2 6 8 4 3
\
3 9 21 8 4

102
Гл. 2. Транспортная задача
6.13.
6.14.
6.15.
А = E50, 150,325,200),	В = B00,280,485,235),
/ 1 7 3	2 \
4 5 8	1
2 3 2	7
\1 2 4	1/
С =
А = (80,120,315,75), В = A50,105,95,90,150),
/37	9 8	6\
1 4	12 3	5
7 11	7 1	2
\ 2 3	16	3/
С =
А = A90,310,260, 140), В = E00, 120, 180,200),
/8	23	21	19 \
28	16	5	7
7	15	4	5
\ 6	4	21	3 )
С =
6.16. А = F00, 360,900, 900), В = B00, 100,600, 300, 700, 860),
/ 13 2 1 3 2 6 \
5 3 3 7 4 8
4 2 6 3 14 7
\845539/
С =
6.17. А = B30, 380, 390, 100), В = B00, 300, 300, 150, 150),
/4366	6 \
3 4 5 5	8
2 5 4 7	9
1 2 3 8	10 )
С =

6. Упражнения
103
6.18. На четырех складах А, В, С, D находится соответственно
32, 30, 18, 20 т горючего, а в пунктах 1, 2, 3, 4, 5, 6 потребляют это
горючее в количествах 9, 10, 14, 20, 21, 26 т соответственно. Перевозка
1 т горючего со складов А, В, С, D в пункты 1, 2, 3, 4, 5, 6 задается
тарифной матрицей
8
Т =
/54
2 9 7
12 2 6
2 5\
5 3
10 7 4
\ 9 35 10 36/
Составить такой план перевозки горючего, при котором транспорт-
транспортные расходы будут минимальными, и указать эти расходы.
6.19.	В резерве трех железнодорожных станций А, В, С находятся
соответственно 90, 40, 30 вагонов. Составить оптимальный план пере-
перегона части этих вагонов к четырем пунктам погрузки хлеба, если пунк-
пункту № 1 необходимо 60 вагонов, №2 — 40 вагонов, №3 — 30 вагонов,
№4 — 20 вагонов. Стоимости перегонов одного вагона со станции А
в указанные пункты соответственно равны 200, 300, 100, 400 руб.; со
станции В - 400, 300, 300, 200 руб. и со станции С - 200, 300, 100,
400 руб. В ответе указать стоимость перегона вагонов.
6.20.	На четырех складах находится сортовое зерно, соответствен-
соответственно 30, 20, 10, 10 т, которое надо доставить в шесть пунктов: пункту
№1 - 20 т, №2 - 10 т, №3 - 10 т, №4 - 10 т, №5 - 10 т,
№6 — 10 т. Стоимость доставки одной тонны зерна с данных складов
в указанные пункты задается тарифной матрицей
/ 2 4 7 2 1 8 \
3 3 6 9 3 5
Т =
2 10 4 7 6
\ 3 5 3 564/
Составить план перевозок зерна со складов во все шесть пунктов,
минимизирующий стоимость перевозок, и указать эту стоимость.
6.21. На четырех базах имеется товар в количествах соответствен-
соответственно 72, 72, 68, 60 единиц. Пять магазинов могут реализовать ежедневно
соответственно 30, 10, 80, 40, 100 единиц. Стоимость перевозки одной
единицы товара от каждой базы до всех магазинов задается матрицей
/20 36 6 27 5\
С =
30 40 3 30 9
10 28 5 47 7
20 32 7 42 3

104
Гл. 2. Транспортная задача
Указать оптимальный план перевозок товаров от баз в магазины,
который минимизировал бы транспортные расходы, и указать эти рас-
расходы .
6.22.	Построить математическую модель транспортной задачи ли-
линейного программирования.
6.23.	Построить двойственную задачу для транспортной задачи
линейного программирования.
6.24.	Пояснить связь между симплексным методом решения транс-
транспортной задачи и методом потенциалов.
6.25.	Почему число занятых клеток распределительной таблицы не
должно быть меньше т-\-п— 1?
Ответы
0 0 60 0
6.1.	1=[ 0 0 20 60
40 60 0 0
F(X) = 840.
6.2.
Х =
/20 0	180 \
0	140	10
130 0	0
\ 0 0	0 /
F(X) = 840.
6.3.
X =
/0	0	0	0	50 \
15	О	О	О	О
85	О	О	О	О
0	70	35	45	О
F(X) = 1560.
6.4.
Х =
/О	0	0	0	60 \
О	0	26	0	10
20	10	34	О	О
\ 0	0	0	30	0 /
F(X) = 668.

6. Ответы
105
6.5.
6.6.
6.7.
X =
X =
/002 0	220 \
0 0 188 0 0
0 0 10 200 0
125 75 0 180 0 у/
/ 100 0 80 0	0 \
0 130 30 0	0
0 0 0 60	60
\ 0 0 40 0	0
F(X) = 4992.
F(X) = 2090.
О 0 0 30
X = | 0 0 30 10 , F(X) = 560.
40 20 0 20
6.8.
200 200 О О
X = | 200 О О О
О 0 300 600
F(X) = 3500.
6.9.
6.10.
О
о
О 18 О
О 6 18
12	18 О
О 0	18	О
Х9= \ 6 О	О
6 18	6
/ О	О	О 40
X = О	О	60 20
\ 60	20	О О
О
F(X) = 354.
F(X) = 520.
6.11.
О 0 0 100
Х=\ О О ПО 140
140 80 10 О
F(X) = 2150.

106
Гл. 2. Транспортная задача
6.12.
6.13.
6.14.
6.15.
X =
6.16. X
/ 0	0	12 0	210 \
О	0	188 О	О
О	О О	200	10
V 125	75 0	180	О
Х =
х =
I 200 0 240	85 \
О	0 8	150
О	80 245	О
у 0	200 О	О /
/ 80	О О О	О \
70	50 О О	О
О	0 75 90	150
\
О 55 20 О О /
X =
/ 190 О О О \
О 0 180 130
210 О О 50
\
О 120 0 20 /
F(X) = 5010.
F(X) = 2370.
F(X) = 1610.
F(X) = 5590.
/О	0	600	0	0 0 \
О	О О	О	О	360
200	100 0	300	0	300
V о	о о	о	700	200 у
F(X) = 11380.
6.17.
X =
/О О О	80	150 \
О	300	10	70	О
100 0	290	О	О
\ то о о	о	о у
F(X) = 3540.
6.18.	310 ден. ед.
6.19.	35000 руб.

7. Транспортная задача по критерию времени	107
6.20. 180 ден. ед.
/0	О	О	40	32 \
О	0	72	О	О
30	10	8	0	8
О	0	0	0	60 )
6.21. Х =
(ден. ед.).
§ 7. Транспортная задача по критерию времени
7.1. Транспортная задача по критерию времени связана со срочны-
срочными перевозками грузов. Имеется т поставщиков с запасами однородно-
однородного груза а\, CL2, ..., ат и п потребителей того же груза с потребностями
Ь\, &2> •••> Ьт. Известна матрица
Т =
промежутков времени, за которые грузы от г-го поставщика доставля-
доставляются j-му потребителю. Эта матрица напоминает матрицу С тарифов
из предыдущего параграфа, поэтому иногда для сравнения или сопо-
сопоставления действий матрицу Т будем ассоциировать с матрицей С.
Требуется составить такой план перевозок, который обеспечил бы
потребности всех потребителей, использовал бы все грузы поставщиков
и при котором перевозка осуществлялась бы за наименьшее время.
Решение. Проведем его по схеме общей транспортной задачи.
1)	Сначала составляем начальный опорный план X методом «наи-
«наименьших тарифов» (этот термин мы используем условно вместо терми-
термина «наименьших времен»).
2)	Оптимальность плана проверяем известным методом потенциа-
потенциалов. Если план оптимален, то его выводим в ответ, а минимальное
время его осуществления считаем равным наибольшему из значений Ц
из занятых клеток (наибольший из тарифов занятых клеток). В таком
случае задача решена.
3)	Если план неоптимален, то, как обычно, составляем оценки
незанятых клеток, строим цикл с вершиной в клетке с наименьшей
отрицательной оценкой и перераспределяем по циклу соответствую-
соответствующую поставку в. Одновременно с этим вычеркиваем все значения ty,
которые превышают время выполнения этого плана (или такие клетки
далее не рассматриваются).
4)	После перераспределения поставок по циклу получаем новый
план, он может быть оптимальным или нет. В первом случае решение

108
Гл. 2. Транспортная задача
задачи обеспечивается за время, равное максимальному значению ty
из занятых клеток (ясно, что это время не больше предыдущего,
потому что большие значения Ц удалены). Если план неоптимален, то
повторяем действие из п.З).
Пример 7.1. Четыре поставщика с грузами соответственно в 550,
250, 300, 100 единиц могут обеспечить четырех потребителей, которые
нуждаются соответственно в 400, 200, 150 и 450 единицах этих грузов.
Найти минимальное время на осуществление всех перевозок, если
матрица времен имеет вид
Т =
/ 1	7	3	2 \
6	9	8	1
2	3	2	7
VI	2	4	1/
Решение. Составляем рабочую таблицу (табл. 7.1).
Таблица 7.1
550
250
300
100
400
1
6
2
1
200
7
9
3
2
150
3
8
2
4
450
2
2
7
1
Методом «наименьших тарифов» строим первый опорный план,
заполняя последовательно клетки A,1), D,4), B,4), A,4), C,3),
C,2), A,2).
В таблицу 7.2, кроме опорного плана, внесены потенциалы занятых
клеток.
Вычисляя потенциалы незанятых клеток, получаем две отрицатель-
отрицательные оценки, поэтому план неоптимален. При этом время на его реали-
реализацию равно наибольшему из времен, записанных в занятых клетках,
т.е. наибольшему из чисел 1, 2, 3, 7. Время равно 7 ед. Наименьшая
отрицательная оценка соответствует клетке D,2). Строим цикл с на-
началом в этой клетке и вершинами в клетках A,2), A,4), D,4). Вели-
Величина поставки, которую надо перераспределить по этому циклу, равна
в = 50. Клетки с временами (тарифами) 8 и 9 можно вычеркивать или
просто не использовать в дальнейшем (при их использовании время
осуществления плана увеличивается).
Новый опорный план с соответствующими потенциалами заносим в
таблицу 7.3.

7. Транспортная задача по критерию времени
109
Таблица 7.2
550
250
300
100
vj
400
1
400
6
2
1
0
200
7
I 50
3 i
! 150
2i
! -4
6
150
3
8
2
150
4
5
450
2
1 ;
100
250
71
1 i
_i
100
l
щ
1
0
3
0
Таблица 7.3
1
400
4
2
1
0
7
5
3
50
2
50
2
3
8
2
150
4
1
2
1
150
250
7
1
150
1
1
0
1
0
Все оценки незанятых клеток неотрицательны, полученный план —
оптимальный.
Ответ: оптимальный план перевозок имеет вид
/ 400 0 0 150 \
0 0 0 250
О 50 150 О
0 50 0 150 )
Время на его реализацию равно t = 3.
X =

по
Гл. 2. Транспортная задача
Вопросы
7.1.	В чем состоит смысл транспортной задачи по критерию време-
времени? Каков критерий в обычной транспортной задаче?
7.2.	Могут ли быть открытые и закрытые задачи по критерию
времени?
7.3.	Надо ли считать стоимость выполнения плана в транспортной
задаче по критерию времени?
Упражнения
Решить следующие транспортные задачи по критерию времени.
7.1.	А = F0, 80, 100, 120), В = D0, 80, 100,240),
7.2.
Т =
/ 15 8
7 6
6 11
7 14 \
9 8
6 10
V
21 7 18 5
А = B00, 100,200, 300),	В = B00, 200,200,200),
/ 9 8 7	6 \
8 7 6	8
5 6 7	8
\ 6 8 7	5 /
Т =
Ответы
7.1.
7.2.
Х =
/ 0	60	0	0 \
40	20	0	20
0	0	100	0
\ 0	0	0	120 /
t(X) = 7.
t(X) = 8.

8. Целочисленное программирование. Метод Гомори	111
§ 8. Целочисленное программирование. Метод Гомори
8.1. Задача целочисленного программирования в канонической фор-
форме формулируется следующим образом:
найти экстремум линейной целевой функции
п
при условиях
\^ctijXj = bi i = 1,га,
Xj ^ 0, Xj — целые числа, j = \,п.
Метод Гомори (отсечения) решения задачи целочисленного про-
программирования заключается в следующем. Сначала задачу надо ре-
решить без условия целочисленности. Если решение целочисленное (все
требуемые компоненты задачи являются целыми числами), то задача
решена. Если решение содержит нецелые компоненты, то в задаче
необходимо ввести дополнительные ограничения.
Сначала напомним определения и способ нахождения целой и дроб-
дробной частей данного действительного числа. Целой частью числа а
называется наибольшее целое число [а], не превосходящее а. Разность
{а} = а — [а] называется дробной частью числа а. Например,
1)	если а =3, то [а] = 3, {а} = 0;
2)	если а = 3,7, то [а] = 3, {а} = 0, 7;
3)	если а = -2, 8, то [а] = -3, {а} = -2, 8 - (-3) = 0,2;
4)	если а = -2/7, то [а] = -1, {а} = -2/7 + 1 = 5/7.
Вернемся к методу отсечения. Предположим, что среди компонент
оптимального решения задачи имеются нецелые числа. Выбираем урав-
уравнение (строку последнего блока таблицы Гаусса), для которого дробная
часть свободного члена наибольшая. Если таких уравнений несколько,
то выбор такого уравнения не имеет значения (произвольный). Пусть
это уравнение имеет вид
j=m+\
В таблице Гаусса строка неизвестных и строка, соответствующая этому
уравнению, выглядят так:

112
Гл. 2. Транспортная задача
Х\
0
0
Хр
1
0
%>,га+1
Aрп
СВ.ЧЛ.
ьР
(неизвестное хр базисное, переменные хт+\, хт+2, •••, %п свободные).
Согласно этому уравнению составим следующее неравенство (огра-
(ограничение, отсечение):
Это неравенство заменим равенством (нам нужна каноническая форма)
или
Это уравнение присоединим к системе ограничений решенной за-
задачи, т.е. составим новую таблицу Гаусса с дополнительным столбцом
для нового неизвестного жп+ь содержащую последний блок табли-
таблицы решенной задачи и новую строку, соответствующую построенному
уравнению.
Если решение новой задачи целочисленное, то тем самым получено
решение исходной задачи (компоненту, соответствующую жп+ь отбра-
отбрасываем). Если новое решение нецелочисленное, то повторяем описан-
описанный алгоритм.
В последнем блоке таблицы Гаусса выбираем строку с наибольшей
дробной частью свободного члена. Составляем новое ограничение (от-
(отсечение), соответствующее этой строке, и решаем новую задачу. Про-
Процесс прекращается, как только все нужные компоненты оптимального
решения станут целыми числами.
Замечание. Иногда в исходной задаче требование целочисленности
всех компонент решения необязательно. В таком случае речь идет о
частичной целочисленности и решение сводится к получению только
нужных целых компонент. Если исходная задача задана не в кано-
канонической форме, то ее сначала следует привести к каноническому
виду введением дополнительных неизвестных. На эти дополнительные
неизвестные условия целочисленности не распространяется.
Пример 8.1. Решить задачу целочисленного программирования
L(X) = 2х\
max,

В. Целочисленное программирование. Метод Гомори
113
хх + 2х2
= 9,
= Ю,
0,
— целые числа, j = 1,4.
Решение. Имеем дело с канонической задачей линейного про-
программирования. Решим ее симплексным методом без учета требования
целочисленности. Таблица Гаусса (табл. 8.1), соответствующая реше-
решению задачи, имеет вид
Таблица 8.1
1
3
2
1/2
E/2)
3/2
0
1
0
х2
0
1
1
1
0
0
1
0
0
х3
1
0
0
1/2
-1/2
-1/2
3/5
-1/5
-1/5
Х4
0
1
0
0
1
0
-1/5
2/5
-3/5
св. чл.
9
10
0
9/2
11/2
-9/2
17/5
11/5
-39/5
Полученное оптимальное решение Х\ = A1/5, 17/5,0,0) не цело-
целочисленное, I/max(^l) = 39/5.
Применим метод Гомори. В последнем блоке таблицы определим
максимальную дробную часть свободных членов:
Составим ограничение, соответствующее уравнению (первой строки)
3	1	17
Оно имеет вид
5-5*3-5*4
К В)

114	Гл.2. Транспортная задача
Это неравенство заменим равенством (см. У. 1 из § 1)
2 3	4
- - - х3 - - х4 + хъ = О,
т.е.	3	4	2
—=х$--х± + хь = --=.
5	5	5
Составим новую таблицу Гаусса (табл. 8.2), содержащую последний
блок предыдущей таблицы, к которому присоединим построенное по-
последнее уравнение (в таблице вводится дополнительный столбец для
дополнительной неизвестной).
Xl
0
1
0
0
0
1
0
0
хч
1
0
0
0
1
0
0
0
Таблица
хъ
3/5
-1/5
-1/5
0
0
1
0
Х4
-1/5
2/5
-4/5
-3/5
-1
2/3
4/3
-1/3
8.2
хъ
0
0
1
0
1
-1/3
-5/3
-1/3
св. чл.
17/5
11/5
-2/5
-39/5
3
7/3
2/3
-23/3
Получили новое оптимальное решение с одной целой компонентой
Х2 = G/3,3,2/3,0,0) — нецелое оптимальное решение, Lmax(X2) =
= 23/3.
Забегая вперед, заметим, что из первого блока новой таблицы полу-
получаем недопустимое решение, поэтому приходится выполнить симплекс-
преобразование с отрицательным разрешающим коэффициентом. Дело
сводится к определению допустимого решения, поскольку условие оп-
оптимальности решения удовлетворяется.
Максимальная дробная часть свободного члена в последнем блоке
соответствует третьей строке, т.е. уравнению
4	5	2
*з+3*4-з*5=з-
Составим новое неравенство (отсечение):
или уравнение
-1-Х4-1-Х5+х& = -2-.

В. Целочисленное программирование. Метод Гомори
115
Новая рабочая таблица имеет вид таблицы 8.3 (заметим, что и здесь
выполним симплекс-преобразование с отрицательным разрешающим
коэффициентом, поскольку система ограничений содержит недопусти-
недопустимое решение, а условие оптимальности удовлетворяется).
Х\
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
х2
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
х3
0
0
1
0
0
0
0
1
0
0
2/3
-1/3
-1/3
1/3
0
Табл и
х4
-1
2/3
4/3
<э
-1/3
0
0
0
1
0
0
0
0
1
0
ца 8.3
хъ
1
-1/3
-5/3
-1/3
-1/3
2
-1
©
1
0
0
0
1
0
0
XQ
0
0
0
1
0
-3
2
4
-3
-1
-1/3
2/3
-4/3
-5/3
-1
св. чл.
3
7/3
2/3
-2/3
-23/3
5
1
-2
2
-7
11/3
5/3
2/3
4/3
-7
Некоторые компоненты оптимального решения (нас интересуют
только х\, Х2, хз и Х4) Х% = E/3, 11/3,0,4/3,2/3,0) не являются
целыми числами, при этом L{X%) = 7, поэтому надо строить очередное
отсечение, которое соответствует уравнению (второй строки). Новое
уравнение имеет вид
Третью строку, содержащую базисную неизвестную х$, отбрасы-
отбрасываем, так как х$ является дополнительной неизвестной, а в качестве
разрешающего будем брать новое уравнение, из которого найдем зна-
значение некоторой базисной неизвестной (табл. 8.4).

116
Гл. 2. Транспортная задача
0
1
0
0
0
0
1
0
0
0
Х2
1
0
0
0
0
1
0
0
0
0
х3
2/3
-1/3
1/3
fe/з)
0
0
0
0
1
0
Таблица 8.4
х4
0
0
0
1
0
0
0
1
0
0
XQ
-1/3
2/3
-5/3
-2/3
-1
-1
1
-1
1
-1
х7
0
0
0
1
0
1
-1/2
1/2
-3/2
0
св. чл.
11/3
5/3
4/3
-2/3
-7
3
2
1
1
-7
Оптимальное решение X* = B,3, 1, 1,0,0) имеет целые компоненты
(было бы достаточно, если бы целыми были только первые четыре
компоненты).
Отбрасывая значения дополнительных неизвестных, составляем от-
вет: Хопт = B, 3, 1, 1) и LmaxB, 3, 1, 1) = 7.
Вопросы
8.1.	В чем состоит идея получения целочисленного решения задачи
ЛП?
8.2.	Для каждой ли задачи ЛП можно получить целочисленное
решение?
8.3.	В чем состоит техническая сложность получения целочислен-
целочисленного решения задачи ЛП?
8.4.	Бывают ли нецелочисленные транспортные задачи?
Упражнения
Найти оптимальные целочисленные решения задач линейного про-
программирования.
8.1.
L(X) = 2х\
min,

8. Упражнения	117
Xj ^ О, х/ — целые числа, j = 1,3.
8.2.	L(X) = 2xi + 4х2 - 6х3 + 8ж4 -> max,
Г xi — ^2 + 2^з + 3^4 = 7,
1 #1 + 3^2 — #з + 2^4 = 5,
О, Xj — целые числа, j = 1,4.
8.3.	L(X) = -3xi - 5х2 + 4ж3 + ж4 -> max,
!—Xi + 5^2 + 3^3 + Ж4 ^ Ю,
^1 — %2 + 5^з + 3^4 < 14,
Xj ^ 0, Xj — целые числа, j = 1,4.
8.4.	L(X) = 5х\ + 4ж2 + х3 -^ max,
ж4 = 10,
Ж5 = И,
^з = 13,
0, Xj — целые числа, j = 1,5.
8.5.	L(X) = 5xi + 18x2 —> max,
25
-xi + -x2<2
x\ ^0, X2 ^ 0, x\$ — целые числа.
8.6.	L(X) = -4xi - 6x2 - 4x3 -^ min,
4xi + 3x2 ~^3 = 3,
-2xi - 3x2 + 2x3 = -2,
xi +2x2 -x3 < -,
0, Xj — целые числа, j = 1,3.

118	Гл.2. Транспортная задача
8.7.	L{X) = -2х\ + х2 + х3 -> min,
2х\ + Х2 — Зхз = 5,
Зх\ - 2х3 < 7,
4xi — Зхз ^ 15,
0, Xj — целые числа, j = 1,3.
8.8.	i'(-X') = 4xi + 4ж2 ^ max,
2	1	5
Г1 + Г2^2'
27
ж1 +3ж2 < у,
х\ ^0, ^2 ^ 0, х\$ — целые числа.
8.9.	L(X) = 3^1 — Х2 + 2жз + ^4 -^ max,
2х\ — Х2 + 4^3 + Ж4 = Ю,
-Зж1 + 2x2 + ^з - 2ж4 = 8, ,
\Х\ — Х2 — 2х% = #4,
х/ ^ 0, х/ — целые числа, j = 1,4.
8.10.	L(X) =х\+ \Х2 + х3 -^ max,
Г Xi — Х2 +Хз = 3,
I 2xi — 5x2 —^з=0»
0, Xj — целые числа, j = 1,3.
8.11.	L(X) = 6xi + 7х2 + 9^з -^ min,
i +2x2 + Зхз > 5,
i +x2 +x3 > 2,
i + 2x2 + 6x3 ^ 4,
Xj ^ 0, Xj — целые числа, j = 1,3.
8.12.	^РО — Ж1 — 6x2 + 2хз — Х4 + 3x5 —> max,

9. Контрольные задания	119
-2х\ +Ж2 +Жз = 1,
2х\ + 3^2 +Х4 = 11,
Х\ — 2X2 +^5 = 2,
Xj ^ О, х/ — целые числа, j = 1,5.
Ответы
8.1.X = B,l,2);Lmin = -7.
8.2.	Х = A,0,0,2); Lmax= 18.
8.3.	X = @,0,2,l);Lmax = 9.
8.4.	Х = B,2, 1,0, 1); Lmax = 19.
8.5.	X = (l,2);Lmax = 41.
8.6.	X = @,4/3, 1); Lmin = —12; целого решения не существует.
8.7.	Хх = C,2, 1), Х2 = B, 1,0); Lmin = -3.
8.8.	X = C,2);Lmax = 20.
8.9.	X = B8, 108,0,62); Lmax = 38.
8.10.	Х = E,2,0); Lmax = 13.
8.11.X = @,l,l);Lmin = 16.
8.12. X = D, 1,8,0,0); Lmax = 14.
§ 9. Контрольные задания
Содержание контрольных заданий:
а)	данные задачи линейного программирования решить геометриче-
геометрическим способом A-2);
б)	для каждой из данных задач составить двойственную и решить
обе задачи симплексным методом C-4);
в)	найти оптимальный план транспортной задачи с правильным или
неправильным балансом E-6).

120
Гл. 2. Транспортная задача
Вариант 1
1.1.
F(X) = 2х\ + 2х2 -> extr,
2х\ — 3^2 ^ 6,
Х\ +Х2 < Ю,
2х\ - 2х2 > 0,
Х\ < 6,
^ 0, ж2 > 0.
1.2.
1.3.
F(X) =
min,
—Ж1 + Х2 —
+ Ж4 = 3,
+ 2хА = 10,
^ >0, j = 1,4.
min,
2,
з + 3^4 > 4,
0, j = Т~4.
1.4.
max,
Xi — 3^2 +Жз ^ 1,
2ж1 - ж2 + 2ж3 < 7,
— 3^1 +#2 +#з ^ 1,
^ > о, j = Т7^.

9. Контрольные задания
121
1.5.
1.6.
Таблица 9.1
250
150
100
290
90
4
7
6
1
100
8
11
3
4
150
10
9
2
7
200
14
12
1
9
250
15
13
4
3
Таблица 9.2
30
30
40
50
25
4
3
2
3
25
6
5
4
2
25
3
2
1
1
15
4
5
6
4
30
1
3
2
3
Вариант 2
2.1.
extr,
2ж1 +ж2 < 15,
Х\ -\- Х2 ^ 5,
х2 < 7,
1 ^ 0, ж2 > 0.
2.2.
min,
2 — Хз — Х4 = —2,
0, j = Т~4.

122
Гл. 2. Транспортная задача
2.3.
F(X) = -7х{ ~
max,
10,
3ж4 < 21,
0, j = Т~4.
2.4.
2.5.
2.6.
F{X) = х\ —
max,
j = 1,3.
Таблица 9.3
180
200
300
320
100
2
3
9
4
140
6
5
7
8
260
4
6
3
5
90
12
9
2
5
210
7
3
5
2
200
11
10
2
9
Таблица 9.4
25
35
40
50
20
3
4
1
1
20
3
2
4
2
20
4
2
1
3
35
2
1
3
1
15
3
4
2
5

9. Контрольные задания
123
3.1.
3.2.
3.3.
3.4.
3.5.
Вариант 3
F(X) = 9х\ + 9х2 -> extr,
' -2xi +X2 <2,
Ж1 - 2ж2 < 2,
Ж1 +^2 > 1,
xi ^4, ^2 ^ 4,
Ж1 > 0, ж2 > О.
F(X) = -X!+5x2-
( Зх\ + 5х2 + 2ж
1 4xi 4
= 1,3.
F(X) = 5
Х\
min,
6,
5,
о,
Таблица 9.5
50
90
65
75
100
3
5
2
6
30
1
1
3
2
70
2
3
4
5
30
4
2
1
3
50
3
6
1
2

124
Гл. 2. Транспортная задача
3.6.
Таблица 9.6
а, ^\
23
27
25
95
40
4
1
3
4
40
2
1
4
5
20
2
5
3
3
10
3
4
5
3
30
1
2
3
2
Вариант 4
4.1.
4.2.
4.3.
4.4.
F(X) = 2хх - Зх2 -> extr,
= х\
min,
3^2
> 4,
= 12,
, j = 1,3.
min,

9. Контрольные задания
125
4.5.
4.6.
Таблица 9.7
а, \-
140
160
100
80
40
2
8
4
1
100
1
7
6
5
120
4
5
2
3
150
3
1
7
4
70
5
3
1
6
Таблица 9.8
150
250
200
300
300
3
3
4
2
300
1
2
1
2
100
4
2
5
3
250
2
1
3
1
200
1
3
2
4
Вариант 5
5.1.
5.2.
2х5 -^ min,
Ж1 + ж2 + 2ж3 - 2х5 = 2,
х\ - х2 + х3 + хА + ж5 = 3,
^ ^ о, j = 17^,

126
Гл. 2. Транспортная задача
5.3.
5.4.
F(X) =
7х2 + 8ж
min,
18,
+ 3^2 + 5жз — 3^4 ^ 10,
+ 3^2 — 2жз + х\ ^ 16,
^ > 0, j = Т~4.
Х\ - Х2 - Хз
max,
5.5.
5.6.
j = 1,3.
Таблица 9.9
100
200
150
150
100
1
3
5
1
100
3
4
2
3
200
5
3
1
2
120
6
7
8
5
80
8
3
2
4
Таблица 9.10
260
24
25
35
33
1
2
4
2
37
4
3
2
3
30
2
1
3
1
20
2
5
4
3
30
4
1
3
2

Список литературы
1.	Акулич И. Л. Математическое программирование в примерах и
задачах. — М.: Высшая школа, 1986. — 320 с.
2.	Барсов А. С. Линейное программирование в технико-экономиче-
технико-экономических задачах. — М.: Наука, 1964. — 278 с.
3.	Карпелевич Ф. И, Садовский Л. Е. Элементы линейной алгебры и
линейного программирования. — М.: Наука, 1967. — 312 с.
4.	Лунгу К. В., Макаров Е. В. Высшая математика. Руководство к
решению задач. — М.: Физматлит, 2004. — 212 с.
5.	Ляшенко И.Н., Карагодова Е.А., Черникова И. В., Шор Н.З.
Линейное и нелинейное программирование. — Киев: Вища школа,
1975. - 370 с.
6.	Пивоварчик А. А. Математическое программирование. — М.: Из-
Издательство МГОУ, 1997. - 300 с.
7.	Сборник задач по высшей математике для экономистов. Учебное
пособие / Под ред. В.И.Ермакова. - М.: ИНФРА-М, 2002.
8.	Юдин Д. Б., Голъдштейн Е. Г. Линейное программирование. —
М.: Наука, 1969.

Учебное издание
ЛУНГУ Константин Никитович
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.
РУКОВОДСТВО К РЕШЕНИЮ ЗАДАЧ
Редактор B.C. Аролович
Оригинал-макет: О.А. Кузнецов
Оформление переплета: А.Ю. Алехина
Подписано в печать 15.07.05. Формат 60x90/16. Бумага офсетная.
Печать офсетная. Усл. печ. л. 8. Уч.-изд. л. 8,8. Заказ №
Издательская фирма «Физико-математическая литература»
МАИК «Наука/Интерпериодика»
117997, Москва, ул. Профсоюзная, 90
E-mail: fizmat@maik.ru, fmlsale@maik.ru;
http://www.fml.ru
Отпечатано с готовых диапозитивов
в ФГУП «Производственно-издательский комбинат ВИНИТИ»
140010, г. Люберцы, Московская обл., Октябрьский пр-т, 403
ISBN 5-9221-0631-7
785922 106313