МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

519.8(07)
М91

Н.В. Муравьева

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Учебное пособие для самостоятельной работы студентов

Челябинск
2011
 Министерство образования и науки Российской Федерации
Южно-Уральский государственный университет
Кафедра прикладной математики

519.8(07)
М91

Н.В. Муравьева

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Учебное пособие для самостоятельной работы студентов

Челябинск
Издательский центр ЮУрГУ
2011
УДК 519.852(076.5)
М91

Одобрено
учебно-методической комиссией механико-математического факультета

Рецензенты:
Е.А. Суховиенко, Г.А. Ларионова

Муравьева, Н.В.
М91 Линейное программирование: учебное пособие для самостоятельной
работы студентов. – Челябинск: Издательский центр ЮУрГУ, 2011. –
50 с.

Пособие предназначено для организации самостоятельной работы

студентов экономических специальностей заочного факультета при
изучении дисциплины «Линейное программирование» в комплексе с
электронным учебно-методическим пособием «Линейное программ-
мирование» ([Link]). В пособии изложены и разъяснены ос-
новные моменты теории, разобраны типичные примеры, что позволяет
также использовать его автономно, без применения компьютера. От-
печатано с авторского оригинала.

УДК 519.852(076.5)

© Издательский центр ЮУрГУ, 2011

2
 Введение

Учебно-методическое пособие по линейному программированию со-

держит материалы, обеспечивающие реализацию государственного образо-
вательного стандарта высшего профессионального образования по дисцип-
лине «Математика» раздел «Линейное программирование». Пособие предна-
значено для организации самостоятельной работы студентов-заочников эко-
номических специальностей.
В настоящее время становятся наиболее актуальны задачи принятия
решения, задачи выбора наиболее эффективного (оптимального) варианта,
при котором был бы достигнут наилучший результат, обеспечивающий мак-
симум или минимум (по смыслу задачи) поставленной цели. Цели могут
быть самыми разнообразными. Применительно к хозяйственному объекту в
качестве цели могут выступать требования обеспечить максимум выпускае-
мой продукции при известном объеме имеющихся ресурсов, минимум затрат
на производство фиксированного набора продуктов, максимум прибыли и
т.п.
Разработкой и практическим применением методов наиболее эффек-
тивного управления различными объектами занимается научная дисциплина,
называемая исследование операций.
Исследование операций имеет важное методологическое значение в
системе подготовки современного экономиста. Именно в этом курсе четко
реализуется идея математического моделирования экономических процессов.
Математической моделью экономической задачи называется совокуп-
ность математических соотношений в виде уравнений и неравенств, описы-
вающих рассматриваемый экономический процесс. Совокупность условий
деятельности управляемой организационной системы (система ограничений)
определяет множество допустимых вариантов, а выбор оптимального вари-
анта осуществляется с помощью целевой функции, которая задает критерий
эффективности управления. Если критерий эффективности (целевая функ-
ция) и функции, входящие в систему ограничений линейны, то такая задача
является задачей линейного программирования.
Для эффективной организации самостоятельной работы студентов-
заочников экономических специальностей создано учебно-методическое по-
собие «Линейное программирование», которое находится на сервере Южно-
Уральского государственного университета по адресу [Link], для
доступа на который требуется предварительно получить логин и пароль у
преподавателя.
Главное меню учебного пособия включает разделы: главная, организа-
ция работы, теория, практикум, тестирование, помощь и выход.

3
 Главное меню высвечено на протяжении всей работы с пособием, за
исключением прохождения тестов. При наведении курсора мышки на инте-
ресующий раздел происходит нижнее подчеркивание названия, а при нажа-
тии левой клавиши мыши, открывается соответствующее окно. Разделы тео-
рии и практики состоят из тем, предназначенных для изучения, которые вы-
свечиваются в левой половине экрана во время работы с данным разделом.

Для перехода к интересующей Вас теме нужно щелкнуть мышкой на

выбранном пункте, тогда открывается соответствующее окно с учебным ма-
териалом.
Для навигации (перемещению) по учебнику используйте средства пе-
рехода по страницам и разделам:
• гиперссылки, в виде ключевого слова (нижнее подчеркивание) - для
перехода к другому окну;
• кнопки навигации Iternet Explorer и других браузеров, например кноп-
ку 'назад' ('back') или гиперссылку Назад – для возврата на предыдущую
страницу.
В разделе «Организация работы» приведены: выписка из государст-
венного образовательного стандарта высшего профессионального образова-
ния, общие требования к уровню освоения содержания дисциплины, пример-
ный тематический план самостоятельной работы со сроками и количеством
рекомендуемых часов для изучения, а также индивидуальный план самостоя-

4
тельной работы, который позволяет составить график изучения дисциплины
индивидуально для каждого пользователя.

Перед началом работы с пособием студент должен составить индивиду-

альный план самостоятельной работы. При нажатии левой клавиши мыши на
колонку «Сроки изучения» появляется календарь, в котором студент выбира-
ет дату следующим образом: при наведении курсора мыши на число меняется
цвет, тогда нажатием левой клавиши мыши производят выбор. Используя
стрелки, студент может изменить месяц. Часы, рекомендуемые на изучение
тем, уже стоят в индивидуальном плане.

Если студенту необходимо изменить это количество, то сначала он щел-

кает левой клавишей мыши по соответствующей ячейке, а затем изменяет ре-
комендуемое количество часов. После составления плана его обязательно
требуется сохранить.
Для начала изучения теоретического материала студент должен пройти
предварительный тест, который определяет степень владения базовыми зна-
ниями и навыками из школьной программы, а также курса «Линейная алгеб-
ра», необходимых для начала изучения курса. Первый тест состоит из 10 за-
5
дач, выполнение которых, в зависимости от сложности, оценивается в один
или два балла. Предварительный тест имеет два режима: режим обучения и
режим тестирования.

Режим обучения представляет собой не столько контролирующую систе-

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

6
 Решение задачи появляется на экране, после нажатия левой клавиши
мыши на ссылку (Решение). Номер текущей задачи выделен черным цветом,
номера задач, к которым не дано ответа, выделяются серым цветом, к кото-
рым даны правильные ответы – зеленым цветом, неправильные ответы –
красным. Если вы хотите закончить работу в режиме обучения, то должны
нажать левой клавшей мыши на кнопку «Завершить тест».
Предварительный тест считается пройденным, если в режиме тестирова-
ния студент набирает не менее 8 баллов (из 12 баллов). После прохождения
предварительного теста студенту предоставляются ссылки на те разделы
учебного материала, на вопросы по которым он ответил неверно, что позволя-
ет ему оценить свой уровень подготовки, ликвидировать недостатки, упуще-
ния и пробелы в усвоении понятий на требуемом уровне, используя режим
обучения.
Лекционный материал – это гипертекстовый учебник, выполненный в
виде блоков. Каждый блок соответствует главе лекционного материала. В
каждом блоке может быть одна или несколько ссылок (в виде ключевого
слова, кнопок перехода и др.), с помощью которых можно перейти в другие
блоки.
В теоретической части пособия использовалась анимация в разделах:
геометрический метод, симплекс-метод и транспортная задача. В тексте ани-
мация выделяется рамкой (голубой пунктир). Для того, чтобы активизиро-
вать картинку, надо щелкнуть по соответствующей гиперссылке левой кла-
вишей мышки. В геометрическом методе анимация позволяет наглядно, а не
мысленно увидеть движение прямой, в симплекс-методе и в транспортной
задаче анимация позволяет постепенно, пошагово заполнять таблицу, а не
давать ее сразу заполненной, что упрощает понимание сложного теоретиче-
ского материала.
Практический блок выполняет функции практических занятий и ими-
тирует общение преподавателя и студента. Он предназначен для закрепления
студентами теоретической части и имеет два режима:
– режим демонстрации решения задач;
– режим обучения.

7
 Режим демонстрации решения задач соответствует практическим зада-
чам, приводимым в качестве примеров на лекции. При решении практиче-
ской задачи студент сначала может проверить правильность своего решения,
нажав на ссылку «Ответ», в случае неверного ответа может проверить ход
своего решения, нажав на ссылку Решение.
В решении практических задач используются ссылки на соответст-
вующую теорию. При нажатии на них (ключевое слово выделяется голубым
цветом и нижним подчеркиванием) появляется окно, которое после исполь-
зования может быть закрыто (нажатием на ссылку Закрыть).

В режиме обучения (интерактивное решение) действия студента кон-

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

8
 Используя раздел «Тестирование», студент имеет возможность само-
стоятельно проверить уровень усвоения понятий и навыков, полученных при
изучении теоретической части и закрепленных практической частью. Тесты
располагаются соответственно главам курса, в них присутствуют задания
всех основных типов, а именно: задания с выбором ответа (одного или не-
скольких); задания, в которых студент должен ввести свой вариант ответа
для сравнения с правильным; задания на соответствие.
Целью изучения учебного материала является не только получение
знаний, но и успешная сдача экзамена по изученному курсу. Поэтому студент
может пройти итоговый тест, аналогичный билету на экзамене, по окончании
которого студента информируют не только о количестве правильных отве-
тов, но и об уровне подготовки его к экзамену. При прохождении итогового
теста контролируется время (90 минут), которое студент затрачивает на от-
вет. Итоговый тест состоит из 4 задач, оцениваемых, в зависимости от слож-
ности, в два, три и пять баллов. Для успешного прохождения итогового теста
требуется набрать семь и более баллов из двенадцати.
Количество попыток, отводимых на прохождение теста в режиме тести-
рования, указывается при запуске теста. При завершении любого тестирова-
ния необходимо нажать кнопку «ГОТОВО», если этого не произойдет, то от-
веты ко всем задачам не будут введены, а количество попыток уменьшится.

9
 Объем дисциплины и виды учебной работы

Вид учебной работы Всего часов

Общая трудоемкость 90

Аудиторные занятия 20

Лекции 10

Практика 10

Самостоятельная работа 70

Вид итогового контроля экзамен

Содержание курса

Прежде чем приступить к изучению нового материала, необходимо

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

Тема 1: Построение математических моделей

Ключевые понятия: задача линейного программирования (ЗЛП), це-

левая функция, система ограничений, условия неотрицательности.
Формируемые умения и навыки (компетенции): формирование на-
выков перехода от практической задачи к математической модели, способ-
ность к анализу и обобщению информации, формирование умений использо-
вать математический язык и математическую символику при построении
экономико-математической модели. Научиться составлять экономико-
математическую модель стандартных задач линейного программирования:
1) Задача о раскрое
2) Транспортная или распределительная задача
3) Задача об оптимальном использовании ресурсов

Теория

Предметом линейного программирования является разработка методов

решения задач на нахождение экстремума (минимума или максимума) ли-
нейной функции n переменных при наличии линейных ограничений в виде
уравнений и неравенств, связывающих эти переменные.
10
 Задача линейного программирования (ЗЛП) включает три элемента:
1) линейная функция minf =c1 x1 + c2 x2 +…+ cn xn = (c , x ) , которая на-
зывается целевой функцией, где c = (c1 , c2 ,..., cn ), x = ( x1 , x2 ,..., xn ) ;

2) система линейных ограничений в виде уравнений или неравенств

a 11
х1 + a12 х 2 ++ a1n х n ? b1 ,
a
 х + a22 х2 +  + a2 n хn ? b2 ,
21 1


⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅

 a m1
х1 + a m 2 х 2 ++ a mn х n ? bm .

или A⋅ x T
? B , где "?" означает один из знаков =, ≥ , ≤ ;

3) условие неотрицательности всех или некоторых переменных

x 1 , x 2, … , x n ;

Практика

Рассмотрим ЗЛП на примере:

Задача об оптимальном использовании ресурсов
Цех выпускает два вида изделий для производства которых используется
три типа ресурсов. Суточные ресурсы: 170 ед. производственного оборудо-
вания, 110 ед. сырья, 160 ед. электроэнергии. Расход ресурсов на производ-
ство одного изделия указаны в таблице. Прибыль от продажи одного изде-
лия вида А – 30 ден. единиц, изделия В – 50. ден. единиц. Найти оптималь-
ный план производства, обеспечивающий максимальную прибыль.
Расход ресурсов на 1
Ресурсы изделие
Изделие А Изделие В

1. Оборудование 2 5
2. Сырье 2 3
3. Электроэнергия 4 3
Решение:
Пусть цех выпускает в сутки x1 изделий вида А и x2 изделий вида В. То-
гда прибыль от продажи выпускаемых изделий равна f = 30x1 +50x2 и тре-
буется найти maxf . Оборудования на производство x1 изделий вида А по-
требуется 2x1, а на изделия вида В – 5x2. Так как есть суточные ограничения
на оборудование, то получим неравенство: 2x1 +5x2 ≤ 170. Аналогично по-
лучаем ограничение на сырье: 2x1 +3x2 ≤ 110 и ограничение на электро-
энергию: 4x1 +3x2 ≤ 160.
Также обе переменные должны быть неотрицательны x1 ≥ 0, x2 ≥ 0.
11
 Итак, получили
maxf = 30x1 +50x2 (1)
 2 x1 + 5 x 2 ≤ 170,

 2 x1 + 3 x 2 ≤ 110, (2)
 4 x + 3 x ≤ 160.
 1 2

x1 ≥ 0, x2 ≥ 0 (3)
Соотношения (1)-(3) образуют экономико-математическую модель.

Рекомендации по организации самостоятельной работы студентов

с помощью электронного учебно-методического пособия

В электронном пособии кроме задачи об оптимальном использовании

ресурсов рассмотрены составление моделей задачи о раскрое и транспортной
задачи в теории, а также распределительной задачи и задаче «о диете» в
практикуме. В тестировании по данной теме входит шесть задач, оценивае-
мых, в зависимости от сложности, в один или два балла. Для успешного про-
хождения теста необходимо набрать пять и более баллов из девяти.

Тема 2: Различные формы ЗЛП и переход от одной формы

к другой

Ключевые понятия: каноническая ЗЛП, стандартная и общая ЗЛП.

Формируемые умения и навыки (компетенции): способность к ана-
лизу формы ЗЛП и умения перехода от одной формы к другой:
а) переход от общей задачи к канонической и стандартной;
в) переход от стандартной задачи к канонической.

Теория

ЗЛП будем называть канонической, если

1) она является задачей минимизации min f = (c , x )
2) все ограничения имеют вид равенств А ⋅ x T = В
3) на все переменные наложено условие неотрицательности x ≥ 0
Стандартными или симметричными будем называть ЗЛП следующих
двух типов:
А) : 1) задача минимизации, min f = (c , x );
2) все ограничения имеют вид неравенств со знаком ≥, А ⋅ x T ≥ В;
3) на все переменные наложено требование неотрицательности, x ≥ 0;
или
В): 1) задача максимизации, max f =(c , x );
2) все ограничения имеют вид неравенств со знаком ≤, А ⋅ x T ≤ В;
3) на все переменные наложено требование неотрицательности, x ≥ 0.
12
Будем называть ЗЛП в общей форме, если:
1) она находит экстремум (минимум или максимум) целевой функции;
2) система ограничений включает как линейные уравнения, так и неравен-
ства;
3) не на все переменные может быть наложено условие неотрицательно-
сти.
Переход от одной формы к другой осуществляется с помощью следую-
щих преобразований:
1) Переход от задачи минимизации к задаче максимизации и наоборот осу-
ществляется сменой знака у целевой функции:
min f = (c , x ) ⇔ max( − f ) = ( −c , x )
2) Переход к соответствующему знаку в неравенстве осуществляется умно-
жением обеих частей неравенства на −1 , при этом знак неравенства меня-
ется на противоположный:
( a , x ) ≥ b ⇔ ( − a , x ) ≤ −b
3) Переход от одного ограничения в виде равенства к паре равносильных
ограничений в виде неравенств осуществляется следующим образом:
(a , x ) ≥ b
(a , x ) = b ⇔
(a , x ) ≤ b
4) Переход от неравенства к равносильному равенству осуществляется с по-
мощью неотрицательных балансовых переменных, которые называются
дополнительными.
Если неравенство имеет знак ≥ , то в левой части неравенства вычитают
неотрицательную дополнительную переменную, а если ≤ , то прибавляют:
( a , x ) ≥ b ⇔ (a , x ) − xn +1 = b, xn +1 ≥ 0
или
( a , x ) ≤ b ⇔ (a , x ) + xn+1 = b, xn+1 ≥ 0
5) Переход к неотрицательным переменным осуществляется следующим
образом.
Если на некоторую переменную xi не наложено условие неотрицательно-
сти, то xi заменяется разностью двух неотрицательных новых перемен-
ных.
xi = xi′ − xi′′ , xi′ ≥ 0, xi′′ ≥ 0
Замечание 1. На практике нумерацию новых переменных производят по-
следовательно, в порядке возрастания.
Замечание 2. Для удобства последний переход (5) производят в первую
очередь, затем осуществляют остальные преобразования.

Практика

Пример 1: Перейти к канонической и стандартной формам в ЗЛП

minf = x1 +x2 –2x3

13
 x1 + x2 − 2 x3 ≤ 2,

 x1 − x2 + x3 = 1,
 x + 4 x ≥ 6.
 1 2

x1 ≥ 0 ,
x3 ≥ 0.
Решение:
Данная ЗЛП дана в общей форме: среди ограничений есть уравнения и
неравенства и не на все переменные наложено условие неотрицательности, а
именно на x2 .
Перейдем к канонической форме:
Используя замечание 2, сделаем переход к неотрицательной переменной в
первую очередь: x2 =x'2 – x4, где x'2 ≥ 0, x4 ≥ 0. Исключим переменную x2 из
целевой функции и системы ограничений: minf = x1 + x'2 – x4 – 2x3
Все ограничения должны иметь вид равенств, используя переход от неравен-
ства к равенству, получим новую систему ограничений:
 x1 + x′2 − x4 + 2 x3 + x5 = 2,

 x1 − x2′ + x4 + x3 = 1,
 x + 4 x′ − 4 x − x = 6.
 1 2 4 6

Все переменные неотрицательные: xi ≥ 0, i=1,2,…,6

Итак, получили ЗЛП в канонической форме:
minf = x1 + x'2 –x4 –2x3
 x1 + x′2 − x4 + 2 x3 + x5 = 2,

 x1 − x2′ + x4 + x3 = 1,
 x + 4 x′ − 4 x − x = 6.
 1 2 4 6

xi ≥ 0, i=1,2,…,6
Перейдем к стандартной форме:
Так как в стандартной форме также на все переменные должно быть наложе-
но условие неотрицательности, то x2 =x'2 – x4, где x'2 ≥ 0, x4 ≥0, используя пе-
реход к неотрицательной переменной.
minf = x1 + x'2 –x4 –2x3,так как задача на минимизацию, то все ограничения
должны быть неравенствами со знаком ≥ . Используя переход к соответст-
вующему знаку неравенства и переход от уравнения к неравенствам, полу-
чим систему ограничений.
- x1 − x 2′ + x 4 − 2 x3 ≥ 2,

 x1 − x 2′ + x4 + x3 ≥ 1,

- x1 + x2′ − x 4 − x3 ≥ −1,
 x1 + 4 x′2 − 4 x 4 ≥ 6.
Итак, получили ЗЛП в стандартной форме:
minf = x1 + x'2 –x4 –2x3

14
 - x1 − x 2′ + x 4 − 2 x3 ≥ 2,

 x1 − x 2′ + x4 + x3 ≥ 1,

- x1 + x2′ − x 4 − x3 ≥ −1,
 x1 + 4 x′2 − 4 x 4 ≥ 6.
xi ≥ 0, i=1,2,3,4
Пример 2: Перейти от канонической к стандартной форме в ЗЛП
minf = 2x1 –x2 +2x3 –x4
2 x1 − x2 + x3 + x4 = 1,

 x1 + x2 + x3 − 2 x4 = 3.
xi ≥ 0, i=1,2,3,4
Решение:
Используем переход от задачи в канонической форме к ЗЛП в стандартной
форме.
Для этого жордановыми исключениями выделим в системе ограничений еди-
ничную матрицу.

xбп x1 x2 x3 x4 b
2 –1 1 1 1
1 1 1 –2 3
0 -3 –1 5 –5
x1 1 1 1 –2 3
x3 0 3 1 –5 5
x1 1 –2 0 3 –2

Запишем соответствующую систему уравнений и выразим базисные пере-

менные через свободные.
3 x2 + x3 − 5 x4 = 5,  x3 = 5 − 3 x2 + 5 x4 ,
 
 x1 − 2 x2 + 3 x4 = −2.  x1 = −2 + 2 x2 − 3 x4 .
Так как переменные x1 и x3 неотрицательные, получаем систему неравенств:
5 − 3 x2 + 5 x4 ≥ 0,

 −2 + 2 x2 − 3 x4 ≥ 0.
Из целевой функции выведем базисные переменные:
minf = 2(–2 + 2x2 – 3x4) – x2 + 2(5 – 3x2 + 5x4 ) – x4 =6 – 3x2 + 3x4
Итак, получили ЗЛП в стандартной форме:

minf = 6 – 3x2 + 3x4

−3 x2 + 5 x4 ≥ −5,

2 x2 − 3 x4 ≥ 2.
x2 ≥ 0,
x4 ≥ 0.

15
 Рекомендации по организации самостоятельной работы студентов
с помощью электронного учебно-методического пособия

В практикуме по темам «Различные формы ЗЛП» и «Переход от од-

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

Тема 3: Свойства решений ЗЛП. Метод перебора.

Геометрический метод решения ЗЛП

Ключевые понятия: допустимый план и ОДР, оптимальный план,

опорное решение, невырожденное и вырожденное решение, недопустимая и
неограниченная ЗЛП, метод перебора, геометрический метод решения.
Формируемые умения и навыки (компетенции): умение использо-
вать геометрический метод и метод перебора при решении ЗЛП.

Теория

Допустимым решением (планом) ЗЛП называется любой n-мерный век-

тор x = ( x1 , x2 ,..., xn ) , удовлетворяющий системе ограничений и условиям
неотрицательности. Множество допустимых решений ЗЛП образует область
допустимых решений (ОДР).
Допустимый план называется оптимальным решением (планом) ЗЛП,
если при этом целевая функция достигает экстремума. Опорным решением
ЗЛП называется неотрицательное базисное решение системы ограничений.
Если число отличных от нуля координат опорного решения равно числу ба-
зисных переменных, то решение называется невырожденным, в противном
случае – вырожденным.
Пусть дана произвольная ЗЛП. Можно доказать, что допустимое множе-
ство планов ЗЛП является выпуклым. Это выпуклое множество может быть
выпуклым многогранником (при n=2 выпуклым многоугольником), выпук-
лой неограниченной многогранной областью или пустым множеством. Если
система ограничений, определяющая допустимое множество является пус-
тым множеством ( т.е. несовместна), то в этом случае говорят о недопусти-
мости задачи. Если целевая функция на допустимом множестве неограни-
ченна снизу, то задачу называют неограниченной и записывают minf=-∞.
Теорема. Если ЗЛП имеет решение, то оптимальное значение целевой
функции достигается по крайней мере в одной из угловых точек допустимого
множества. Если целевая функция принимает наименьшее значение более,
чем в одной угловой точке, то она принимает такое же значение в любой точ-
ке, являющейся выпуклой линейной комбинацией этих вершин.
16
 ЗЛП можно решить методом перебора опорных планов (вершин много-
гранника планов), т.е. выбрать опорный план при котором f принимает наи-
меньшее значение, в предположении, что ЗЛП имеет решение.
Геометрический или графический метод применяется в случае n=2 (n-
число переменных). Пусть дана ЗЛП, система ограничений которой состоит
только из неравенств (ЗЛП в стандартной форме).
Этапы решения задачи геометрическим методом:
1) На координатной плоскости X1OX2 строим допустимое множество данной
задачи по системе ограничений (ОДР – область допустимых решений).
2) От начала координат откладывают вектор координаты, которого
c = (c1 , c2 ), находят по коэффициентам целевой функции f = c1x1 + c2x2. Этот
вектор является вектором градиента и указывает направление возрастания
функции, а противоположный вектор – убывания функции.
3) Строим семейство параллельных прямых (линий уровня), перпендикуляр-
ных к вектору. На практике строят одну прямую, а затем начинают ее мыс-
ленно двигать.
Определение. Прямая, которая проходит через вершину многоугольника и
весь многоугольник лежит по одну сторону от этой прямой, называется
опорной.
Пример:
(1) (1) опорная прямая
(3)
(2) опорная прямая

(3) не опорная прямая

(2)

Оптимальному плану соответствует вершина ОДР, через которую

проходит опорная прямая из семейства параллельных прямых. Если двигать-
ся в направлении вектора c , то угловая точка, через которую проходит пер-
вая опорная прямая соответствует оптимальному решению для минимума
функции, а последняя для максимума.

Практика

Пример 1: Решить ЗЛП геометрическим методом

maxf = 3x1 + 2x2
 x1 − x 2 ≥ −2,
 2 x − x ≤ 6,
 1 2

 2 x1 + x 2 ≥ 2,
 x 2 ≤ 4.
x1 ≥ 0, x2 ≥ 0.
17
Решение:
Используем алгоритм геометрического метода:
1) Строим ОДР, для этого в прямоугольной декартовой системе координат
строим прямые: x1 – x2 = –2 (1) 2x1 + x2 = 2 (3)
2x1 – x2 = 6 (2) x2 = 4 (4)
Для каждой из прямых составляем таблицу точек
x1 0 –2 x1 – x2 = –2 (1) x1 0 3 2x1 – x2 = 6 (2)
x2 2 0 x2 –6 0

x1 0 1
x2 2 0 2x1 + x2 = 2 (3)

Определим, какая часть плоскости задается неравенством методом проб-

ной точки. Для этого выбираем координаты любой точки, не лежащей на
прямой и подставляем их в неравенство. Если получается верное неравенст-
во, то выделяем часть той полуплоскости, где лежит точка. Выделение про-
изводим стрелкой (вектором нормали), направленной в выбранную полу-
плоскость.
x2

(1)
(2)

4 C (4)
D
B
2

-2 3
A 1 E
x1

-6 (3)

Например, для прямой (1) выберем точку (0,0) (прямая не проходит через
нее). Подставим координаты точки в неравенство: 1·0–1·0 ≥ –2, 0≥ –2 – вер-
но. Следовательно, мы выбираем ту полуплоскость, где лежит (0,0). Анало-
гично выделяем полуплоскости для каждой из прямых. Находим общую
часть всех полуплоскостей и учитываем условия неотрицательности. Полу-
чится пятиугольник ABCDE.
2) Строим вектор c = {3, 2} по целевой функции maxf = 3x1 + 2x2 . Начало
вектора в точке (0;0) конец в точке (3;2), вектор выделен красным цветом.
3) Строим семейство параллельных прямых, перпендикулярных вектору c .
Строим первую прямую, проходящую через начало координат и начинаем ее
двигать в направлении вектора c , так как решаем задачу на максимизацию
функции, до второй опорной прямой для ОДР. Выбираем угловую точку, че-
18
рез которую проходит опорная прямая – точку D. Найдем ее координаты как
точку пересечения прямых (2) и (4), т.е. решаем систему уравнений:
2 х1 − x2 = 6,  х1 = 5,
  , т.е. D(5,4). Вычислим значение целевой функции в
x
 2 = 4. x
 2 = 4.
точке D: f(D) = 3·5 + 2·4= 23.
Пример 2. Решить ЗЛП геометрическим методом
minf = − x1 + 7x2 + x3 + 3x4 − x5
− х −3 х + х + 2 х + х
1 2 3 4 5
= 4,
 х − 8х + 4х + х + х
 1 2 3 4 5 = 3,
−4 х + х + х =−4.
 2 3 5

xi ≥ 0, i=1,2,…,5
Решение:
Перейдем от задачи в канонической форме к задаче в стандартной форме.
xбп x1 x2 x3 x4 x5 b
–1 –3 1 2 1 4
1 –8 4 1 1 3
0 –4 1 0 1 –4
x1 1 3 –1 –2 –1 –4
0 –11 5 3 2 7
0 –4 1 0 1 –4
x1 1 –1 0 –2 0 –8
0 9 0 3 –3 27
x3 0 –4 1 0 1 –4
x1 1 –1 0 –2 0 –8
x5 0 –3 0 –1 1 –9
x3 0 –1 1 1 0 5
Используя последнюю часть таблицы, запишем систему ограничений в пре-
образованном виде
 х − х − 2 х =−8,
1 2 4

 −3 х − х + х = −9,
 2 4 5
выразим базисные переменные через свободные и вы-
 − х + х + х = 5.
 2 3 4

х 1
=−8 + х 2 + 2 х 4 ,


ведем их из целевой функции: х 5 = −9 + 3 х2 + х4 , (*)
х =5+ х2 − х4 .
 3

19
minf = − ( − 8 + x2 + 2x4) + x2 + (5 + x2 − x4) + 3x4 − ( − 9 + 3x2 + x4)=22 + 4x2 − x4
Используем условие неотрицательности переменных, получим ЗЛП с дву-
мя переменными в стандартной форме.
minf =22 + 4x2 − x4
 х + 2 х ≥8,
2 4

3 х + х ≥ 9,
 2 4

 х − х ≥−5
 2 4

x2 ≥ 0
x4 ≥ 0
Решаем ее геометрическим методом:
1) Строим ОДР, для этого в прямоугольной декартовой системе координат
строим прямые: x2 + 2x4 = 8 (1) 3x2 + x4 = 9 (2)
x2 – x4 = − 5 (3)
x4 (3)

A
(1) 5

4
B

С 8
-5 3
x2
(2)

Искомой ОДР является неограниченная область с угловыми точками A, В

и С.
2) Строим вектор c = {4; −1} по целевой функции minf =22 + 4x2 − x4 Начало
вектора, в точке (0;0) а конец в точке (4;-1).
3) Строим семейство параллельных прямых, перпендикулярных вектору c .
Строим первую прямую, проходящую через начало координат и начинаем ее
двигать в направлении вектора −c , так как решаем задачу на минимизацию
функции. Находим опорную прямую в этом направлении, она проходит через
точку А, точку пересечения прямых (2) и (3):
3 х + х = 9,
2 х 4 2
=1,
 ,
 , таким образом точка А(1,6).
х − х = −5. = 6.
 2
х
4 4

Вычисляем минимальное значение целевой функции minf =22 + 4·1 – 1·6=20.

20
Находим оптимальное решение исходной задачи. Для этого используем сис-
тему уравнений (*).
х 1
= 5,
х *
 3 = 0, Таким образом, оптимальное решение X (5; 1; 0; 6; 0).
х = 0.
 5

Рекомендации по организации самостоятельной работы студентов

с помощью электронного учебно-методического пособия

В разделе теория геометрического метода анимация позволяет нагляд-

но, а не мысленно увидеть движение прямой. После щелчка левой клавишей
мыши по ссылке minf=f(E) или maxF=f(C) прямая (красного цвета) начинает
двигаться, опорные прямые выделяются голубым цветом.

При нажатии на ссылку Исходное состояние прямая возвращается в

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

21
 Тема 4: Симплекс-метод

Ключевые понятия: симплексная таблица, индексная строка, оценки

переменных, симплексное отношение.
Формируемые умения и навыки (компетенции): умение использо-
вать симплекс-метод при решении ЗЛП.

Теория

Симплекс метод (Метод последовательного улучшения базисного плана)

Пусть дана каноническая ЗЛП с простейшей системой ограничений (в
системе линейных уравнений выделена единичная матрица) и все свободные
члены ≥ 0.
Алгоритм симплекс метода:
1) Составление первой симплексной таблицы:
cбп xбп x1 x2 ··· xn B
c1 c2 ··· cn
cб1 xб1 a11 a12 ··· a1n b1
··· ··· ··· ··· ··· ··· ···
cбr xбr ar1 ar2 ··· arn br
f Δ1 Δ2 ··· Δn Δ0
Последняя строка в таблице называется индексной строкой.
Где Δi называются оценками соответствующих переменных, а Δ0 – значе-
ние целевой функции f при подстановке в нее найденного начального опор-
ного плана и считаются по формуле: Δ i = (cбп , Аi ) − ci , Δ 0 = (cбп , B ) , т.е. Δi рав-
но скалярному произведению столбца cбп на столбец коэффициентов соот-
ветствующей переменной минус соответствующий коэффициент при целе-
вой функции, а Δ0 равно скалярному произведению столбца cбп на столбец
свободных членов.
Например: Δ1 = (cбп , А1 ) − c1 = cб1 ⋅ a11 + cб 2 ⋅ a21 + ... + cбr ⋅ ar1 − c1
2) Проверка исходного плана на оптимальность.
Если в индексной строке все оценки неположительные Δi ≤ 0, i=1,…,n ,
то исходный опорный план оптимален и Δ0 искомое наименьшее значение
целевой функции.
3) Проверка на неограниченность задачи.
Если в индексной строке содержится положительная оценка, над кото-
рой в таблице нет ни одного положительного элемента, то целевая функция
не ограничена снизу и задача не имеет решения.
4) Улучшение исходного опорного плана.
Если в индексной строке содержится положительная оценка, то перехо-
дим к новому опорному плану заполняя новую таблицу по правилам:

22
 а) Выбираем ведущий столбец по положительной оценке, если их не-
сколько то по наибольшей. Таким образом, мы выбрали переменную вводи-
мую в число базисных.
б) Выбираем ведущую строку исходя из наименьшего симплексного от-
b 
ношения θ = min  i  , a ik > 0.
i
 aik 
(отношение неотрицательных свободных членов к соответствующим по-
ложительным элементам ведущего столбца).
Таким образом, выбираем переменную, выводимую из базиса.
в) Выполняем жорданово исключение с выбранным ведущим элементом,
стоящим на пересечении ведущего столбца и строки. При этом все элементы
новой симплексной таблицы, в том числе и расположенные в индексной
строке, вычисляются по стандартным правилам жордановых исключений.
г) Проверяем пункт 2.
Практика

Пример: Решить ЗЛП симплексным методом

minf = − 4x1 + 6x2 − 2x3 + 3x4
2 х1
+ х 2 − х 3 = 5,

− 3 х3 + х4 = 7.
2 х1

xi ≥ 0, i=1,2,…,4
Решение:
Система имеет простейший вид (выделена единичная матрица) и все свобод-
ные члены неотрицательны, поэтому можем составить первую симплексную
таблицу
1)
сбп xбп x1 x2 x3 x4 b
–4 6 –2 3
6 x2 1 1 –1 0 5
3 x4 2 0 –3 1 7
f 16 0 5 0 51
2) Так как в индексной строке есть положительные оценки, то исходный
опорный план будет неоптимальным.
3) Так как в индексной строке содержится положительная оценка, над кото-
рой в таблице есть положительный элемент, то задача имеет решение 4)
Улучшаем начальный опорный план пошагово
а) Выбираем столбец с наибольшей оценкой Δ1 = 16.
б) Считаем симплексное отношение θ=min{5/1;7/2}=7/2, т.е. ведущий эле-
мент a21.
в) Заполняем новую таблицу с выбранным ведущим элементом по прави-
лам жордановых исключений:
23
xбп x1 x2 x3 x4 b
x1 0 1 1/2 –1/2 3/2
x4 1 0 –3/2 1/2 7/2
f 0 0 29 –8 –5
Возвращаемся к шагу 2)
2) Так как в индексной строке есть одна положительная оценка Δ3 =29, по-
этому выбираем третий столбец ведущим.
3) Так как в индексной строке в третьем столбце есть положительный эле-
мент, то задача имеет решение, этот элемент и будет ведущим a13.
4) Заполняем новую таблицу с выбранным ведущим элементом по правилам
жордановых исключений:
xбп x1 x2 x3 x4 b
x1 0 2 1 –1 3
x3 1 –3 0 –1 10
f 0 –58 0 21 –92
Возвращаемся к шагу 2)
2)-3) В новой таблице в индексной строке есть положительный элемент, но
в этом столбце нет положительных элементов, следовательно, данная ЗЛП не
имеет решений.

Рекомендации по организации самостоятельной работы студентов

с помощью электронного учебно-методического пособия

В разделе теория симплекс-метода для заполнения симплексных таблиц

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

24
 При нажатии на пустые клетки, при заполнении второй таблицы, вы-
даются подсказки, о том каким образом находятся элементы.

В практикуме приведены примеры, решение которых рекомендуется

разобрать. В тестирование по данной теме входит семь задач, оцениваемых, в
зависимости от сложности, в один, два или три балла. Для успешного прохо-
ждения теста необходимо набрать шесть и более баллов из двенадцати.

Тема 5: Метод искусственного базиса

Ключевые понятия: вспомогательная задача, искусственные пере-

менные.
Формируемые умения и навыки (компетенции): умение использо-
вать метод искусственного базиса (двухфазный симплекс-метод) при реше-
нии ЗЛП.
Теория

Рассмотрим двухфазный симплекс-метод. Пусть дана каноническая ЗЛП,

но в системе уравнений не выделена единичная матрица и все свободные
члены ≥ 0.
25
 Алгоритм решения состоит из этапов:
1) Построение вспомогательной задачи:
a) Прибавляем искусственные переменные в те ограничения, которые не со-
держат базисных переменных (переменная называется базисной, если стол-
бец, соответствующий этой переменной, является единичным). Получаем ис-
кусственную простейшую систему ограничений.
b) Составляем целевую функцию вспомогательной задачи S, равной сумме
всех искусственных переменных.
2) Решение вспомогательной задачи.
Решая вспомогательную задачу симплекс – методом найдем minS. При ре-
шении возможны случаи:
a) minS ≠0 , тогда исходная ЗЛП является недопустимой и не имеет ре-
шения;
b) minS =0 и среди базисных переменных в завершающей симплексной
таблице есть хотя бы одна искусственная. В этом случае выводят искусст-
венные переменные из числа базисных, выполняя жордановые исключения.
Произвольно выбирают по одному ведущему элементу в каждой из строк,
соответствующих искусственным базисным переменным, при этом индекс-
ная строка и столбец свободных членов не изменятся.
c) minS =0 и среди базисных переменных в завершающей симплексной
таблице нет ни одной искусственной, тогда переходим к третьему этапу.
3) Решение основной задачи.
Заменив систему ограничений исходной ЗЛП найденной простейшей систе-
мой (последняя симплексная таблица на втором этапе), решаем симплекс-
методом полученную задачу.
Замечание: Для уменьшения объемов вычислений при решении вспомога-
тельной задачи, при выводе искусственной переменной из числа базисных,
соответствующий столбец в следующих симплексных таблицах не заполня-
ется.

Практика
Пример. Решить ЗЛП методом искусственного базиса (двухфазный сим-
плекс-метод).
minf = 7x1 − 13x2 − 8x3 +10x4
 х − х −3х + 2 х
1 2 3 4
= 3,

 х − 2х − х + х
1 2 3 4 = 2.
xi ≥ 0, i=1,2,…,4
Решение:
Используем алгоритм двухфазного симплекс метода.
1) Составляем вспомогательную задачу:
minS = x5 + x6

26
 х − х −3х + 2 х
1 2 3 4
+ х5 = 3,

 х − 2х − х + х
1 2 3 4 + х6 = 2.
xi ≥ 0, i=1,2,…,6
Получили простейшую систему ограничений с неотрицательными свобод-
ными членами.
2) Решаем вспомогательную задачу симплексным методом.
xбп x1 x2 x3 x 4 x5 x 6 b
сбп 0 0 0 0 1 1
1 x5 1 –1 –3 2 1 0 3
1 x6 1 –2 –1 1 0 1 2
S 2 –3 –4 3 0 0 5
x4 1/2 –1/2 –3/2 1 0 3/2
x6 1/2 –3/2 1/2 0 1 1/2
S 1/2 –3/2 1/2 0 0 1/2
x4 2 –5 0 1 3
x3 1 –3 1 0 1
S 0 0 0 0 0
3) Решаем основную задачу симплексным методом, заменив систему ограни-
чений, полученной простейшей (последняя таблица)
сбп xбп x1 x2 x3 x4 b
7 –13 –8 10
10 x4 2 –5 0 1 3
-8 x3 1 –3 1 0 1
f 5 –13 0 0 22
x4 0 1 –2 1 1
x6 1 –3 1 0 1
f 0 2 –5 0 17
x2 0 1 –2 1 1
x1 1 0 –5 3 4
f 0 0 –1 –2 15
Итак, получили minf =15, оптимальное решение X*(4, 1, 0 ,0).

Рекомендации по организации самостоятельной работы студентов

с помощью электронного учебно-методического пособия:

В практикуме метода искусственного базиса приведены примеры, ко-

торые рекомендуется разобрать. В тестирование по данной теме входит 4 за-
дачи, оцениваемых, в зависимости от сложности, в один, два или три балла.
Для успешного прохождения теста необходимо набрать четыре балла или бо-
лее из семи.

27
 Тема 6: Теория двойственности

Ключевые понятия: симметричные двойственные задачи, несиммет-

ричные двойственные задачи, сопряженные условия, критерий Канторовича.
Формируемые умения и навыки (компетенции): умение составлять
симметричные и несимметричные двойственные задачи, по решению одной
из взаимно двойственных ЗЛП нахождение решения другой.

Теория

Любой задаче линейного программирования, называемой исходной или

прямой, можно поставить в соответствие другую задачу, которая называется
двойственной или сопряженной. Если понять взаимосвязь между этими за-
дачами, то можно решение одной из них получить непосредственно из реше-
ния другой.
Симметричные двойственные задачи (ДЗ)
Рассмотрим симметричные двойственные задачи, т.е. обе задачи ли-
нейного программирования имеют стандартную форму.
ИЗ ДЗ
min(c1x1+ c2x2 + …+cnxn) max(b1 y1+ b2y2 + …+bmym)
a11 x1+ a12x2 + …+a1nxn ≥ b1 y1 ≥ 0
a21 x1+ a22x2 + …+a2nxn ≥ b2 y2 ≥ 0
··· ···
am1 x1+ am2x2 + …+amnxn ≥ bm ym ≥ 0
x1 ≥ 0 a11 y1+ a21y2 + …+am1ym ≤ c1
x2 ≥ 0 a12 y1+ a22y2 + …+am2ym ≤ c2
··· ···
xn ≥ 0 a1n y1+ a2ny2 + …+amnym ≤ cn
Правила составления симметричных ДЗ:
1) Одна из задач является задачей нахождения минимума, другая – макси-
мума.
2) Число переменных одной задачи равно числу ограничений другой.
3) Коэффициенты целевой функции одной задачи являются свободными чле-
нами системы ограничений другой.
4) В задаче нахождения минимума все неравенства со знаком ≥ , в задаче на-
хождения максимума ≤ .
5) Матрицы систем ограничений обеих задач получаются друг из друга
транспонированием.
6) Каждому ограничению неравенством в одной из задач соответствует неот-
рицательная переменная в другой задаче.

неравенство ↔ yi ≥ 0

xi ≥ 0 ↔ неравенство

28
 Очевидно, что двойственной задачей к двойственной является исходная
задача. Поэтому рассмотренные задачи являются взаимно двойственными.
При составлении двойственной задачи каждому ограничению исходной
задачи сопоставляют очередную переменную двойственной задачи. Таким
образом, получаем взаимно однозначное соответствие между ограничениями
и переменными взаимно двойственных задач.
Несимметричные двойственные задачи
Пусть дана ЗЛП общего вида.
Правила составления несимметричных ДЗ
Правила 1-6 составления симметричных ДЗ остаются справедливыми.
7) Каждому ограничению равенством в одной задаче соответствует пере-
менная произвольного знака.
равенство ↔ ∀yi
∀ xi ↔ равенство
При составлении несимметричных взаимно-двойственных задач принято
располагать компоненты соответствия, находящиеся по правилам 6 и 7 в
одной строке, и называть их сопряженными условиями.
Принцип двойственности. Критерий Канторовича.
Теоремы двойственности позволяют установить взаимосвязь между оп-
тимальными решениями пары двойственных задач. Решив одну из пары
двойственных задач, можно или найти оптимальное решение другой задачи,
не решая ее, или установить его отсутствие.
Теорема 1. Если одна из пары двойственных задач имеет оптимальное реше-
ние, то и другая имеет оптимальное решение. При этом оптимальные значе-
ния целевых функций равны minf = maxF.
Если одна из пары двойственных задач не имеет решения ввиду неогра-
ниченности целевой функции, то другая не имеет решения ввиду несовмест-
ности системы ограничений.
Теорема 2. Если каждая из пары взаимно двойственных задач имеет хотя бы
по одному плану, то обе задачи имеют оптимальное решение.
Теорема 3. Для того чтобы некоторые планы x и y пары двойственных за-
дач были оптимальными, необходимо и достаточно, чтобы значения целевых
функций для этих планов были равны.

Теорема (Критерий Канторовича для одного плана). Для того чтобы план
x0 данной ЗЛП был оптимальным, необходимо и достаточно, чтобы суще-
ствовал план y0 двойственной задачи, такой что при подстановке этих пла-
нов в соответствующие системы ограничений всякому строгому неравенству
в исходной ЗЛП соответствовало бы равенство в сопряженном условии ДЗ.

Теорема (Критерий Канторовича для двух планов). Пусть задано по плану

x0 и y0 в каждой из взаимно двойственных задач. Для того чтобы эти планы
были оптимальными, необходимо и достаточно, чтобы при подстановке этих
29
планов в соответствующие системы ограничений в каждой паре сопряжен-
ных условий строгому неравенству в ограничениях одной задачи соответст-
вовало бы равенство в ограничениях другой.

Практика

Пример 1. Для исходной ЗЛП составить двойственную задачу.

minf = 2x1 +3x2 – 4x3

х 1
− 2 х 2 − 3 х 3 ≥ 3,

+ х2 − х3 ≥ −2.
х 1

xi ≥ 0, i=1,2,3.
Решение:
Дана ЗЛП в стандартной форме, поэтому используем правила для симмет-
ричных двойственных задач.
Исходная ЗЛП Двойственная ЗЛП
minf = 2x1 +3x2 – 4x3 maxF = 3y1 – 2y2
x 1 – 2x 2 – 3 x 3 ≥ 3 y1 ≥ 0
x1 + x2 – x3 ≥ –2 y2 ≥ 0
x1 ≥ 0 y1 + y2 ≤ 2
x2 ≥ 0 –2y1 + y2 ≤ 3
x3 ≥ 0 –3y1 – y2 ≤ –4
Пример 2. Для исходной ЗЛП составить двойственную задачу.
maxf = 3x1 + x2 – 3x3
2 х − х + 6 х ≥1,
1 2 3

3 х + х − 4 х = −6
 1 2 3

 х − х + 5 х ≤ 2.
 1 2 3

x1 ≥ 0
x3 ≥ 0.
Решение:
Исходная задача дана в общей форме, так как нет условия неотрицатель-
ности на переменную x2 и в системе ограничений есть как неравенства так и
равенство. Перед тем как составлять двойственную задачу умножим первое
неравенство на -1, используя правило соответствия знака неравенства.
Для составления двойственной задачи используем правила для несим-
метричных двойственных задач.
Сопряженным условием для второго равенства в системе ограничений
будет являться переменная произвольного знака ∀y2 и для переменной x2 в
системе ограничений двойственной задачи будет равенство, по правилу 7.
Исходная ЗЛП Двойственная ЗЛП
30
 maxf = 3x1 +x2 – 3x3 minF = –y1 – 6y2 + 2y3
–2x1 + x2 – 6x3 ≤ –1 y1 ≥ 0
3x1 + x2 – 4x3 = –6 ∀ y2
x 1 – x 2 + 5x 3 ≤ 2 y3 ≥ 0
x1 ≥ 0 –2y1 +3y2 +y3 ≥ 3
∀ x2 y1 + y2 – y3 = 1
x3 ≥ 0 –6y1 – 4y2 +5y3 ≥ –3
Пример 3. Применяя критерий Канторовича, исследовать на оптимальность
план X0(2, 3, 0).
minf = x1 + 3x2 + 3x3
 х + х + х = 5,
1 2 3

 х − х − 2 х ≥ −3,
 1 2 3

− х + х − х ≥ 1.
 1 2 3

x1 ≥ 0
x 3 ≥ 0.
Решение:
Составим двойственную задачу, используя правила для несимметричных
двойственных задач.
Исходная ЗЛП Двойственная ЗЛП
minf = x1 +3x2 +3x3 minF = 5y1 – 3y2 + y3
x1 + x 2 + x3 = 5 ∀y1
x1 – x2 – 2x3 ≥ –3 y2 ≥ 0
–x1 + x2 – x3 ≥ 1 y3 ≥ 0
x1 ≥ 0 y1 + y2 – y3 ≤ 1
∀x2 y1 – y2 + y3 = 3
x3 ≥ 0 y1 – 2y2 –y3 ≤ 3
0
Подставим данное решение X (2, 3, 0) во все ограничения исходной задачи и
там, где будет строгое неравенство, поставим соответствующий знак. Тогда в
сопряженном условии двойственной задачи будет равенство.
minf = x1 + 3x2 + 3x3 maxF = y1 + y2 – y3
x1 +x2 +x3 = 5 ∀y1
x1 –x2 –2x3 ≥ –3 > y2 ≥ 0 =
–x1 +x2 –x3 ≥ 1 y3 ≥ 0
x1 ≥ 0 > y1 + y2 – y3 ≤ 1 =

∀x 2 y1 –y2 + y3 = 3
x3 ≥ 0 y1 –2y2 – y3 ≤ 3
0
Если заданный план оптимален X , то по теореме (Критерий Канторовича для
одного плана) у двойственной ЗЛП должен существовать план
31
 0
y 2
= 0,
Y (y , y , y ), для которого
1 2 3

+ y2 − y3 = 1.
y 1

Кроме того, так как план двойственной задачи, его компоненты удовлетво-
ряют ограничению - равенству
y1 – y2 + y3 = 3. Решаем систему и находим Y0.
y 2
= 0, y 2
= 0, y 2
= 0,
y y y
 1 + y2 − y3 = 1,  1 − y3 = 1,  1 = 2,
y − y2 + y3 = 3. y + y3 = 3. y = 1.
 1
 1
 3

Так как найденный вектор Y0 (2, 0, 1) удовлетворяет всем ограничениям

двойственной задачи (убеждаемся подстановкой его компонент во все огра-
ничения двойственной задачи), то он является оптимальным решением и,
следовательно, данный вектор X0 (2, 3, 0) является оптимальным решением
исходной задачи.

Рекомендации по организации самостоятельной работы студентов

с помощью электронного учебно-методического пособия

В практикуме по теме «Двойственность в линейном программирова-

нии» представлено большое количество примеров, которые рекомендуется
разобрать. В тестирование по данной теме входит 8 задач, оцениваемых, в за-
висимости от сложности, в один, два или три балла. Для успешного прохож-
дения теста необходимо набрать шесть или более баллов из двенадцати.

Тема 7: Транспортная задача

Ключевые понятия: открытая и закрытая модель транспортной зада-

чи, распределительная таблица, цикл, потенциалы, оценки свободных клеток.
Формируемые умения и навыки (компетенции): умение использо-
вать метод потенциалов при решении транспортной и распределительной за-
дач. Научиться строить начальный опорный план по правилам «северо-
западного угла» и «наименьшего тарифа», делать пересчет по циклу и решать
открытую модель ТЗ.
Теория

Постановка транспортной задачи

Пусть в m пунктах A1 , A2 , … , Am находится однородный груз в коли-
честве соответственно a1 , a2 , … , am, который необходимо доставить n по-
требителям B1 , B2 , … , Bn в количестве b1 , b2 , … , bn. Известны транспорт-
ные издержки cij - стоимость перевозки единицы продукции из пункта Ai в
32
пункт Bj , т.е. дана матрица тарифов Cm×n = (cij) . Составить план перевозок,
при котором общая стоимость перевозок наименьшая.
Для наглядности транспортную задачу представим в таблице, которая
называется распределительной. Тарифы cij занесены в уголках соответст-
вующих клеток.
B1 B2 … Bn Запасы груза, ai

A1 c11 c12 … c1n a1

A2 c21 c22 … c2n a2

… … … … … …

Am cm1 cm2 … cmn am

Потребности m n

в грузе, bj b1 b2 … bn  a = b
i =1
i
j =1
j

Наша модель транспортной задачи является закрытой, так как суммарный

m n
запас груза равен суммарной потребности, т.е.  ai =  b j
i =1 j =1

Обозначим xij - количество единиц груза, которое надо доставить от по-

ставщика Ai потребителю Bj . План перевозок груза записывается в виде
матрицы Xm×n = (xij). Неизвестные xij занесены в соответствующие клетки.
B1 B2 … Bn Запасы груза, ai

c11 c12 … c1n a1

A1 x11 x12 x1n
c21 c22 … c2n a2
A2 x21 x22 x2n
… … … … … …

cm1 cm2 … cmn am

Am xm1 xm2 xmn
Потребности m n

в грузе, bj b1 b2 … bn  ai =  b j
i =1 j =1

Тогда общая стоимость перевозок груза равна

f = c11 x11 + c12 x12 +…+ c1n x1n +…+ cm1 xm1 +cm2 xm2 +…+ cmn xmn и требуется
найти min f .
Переменные xij должны удовлетворять ограничениям по запасам груза и по
потребностям. От поставщика A1 перевезено x11 + x12 +…+ x1n единиц гру-
за, что должно равняться запасу a1, т.е. x11 + x12 +…+ x1n = a1.
Аналогично для поставщика A2: x21 + x22 +…+ x2n = a2, … и для поставщика
Am: xn1 + xn2 +…+ xmn = am .
К потребителю B1 перевезено x11 + x21 +…+ xm1, что должно равняться
потребности b1, т.е. x11 + x21 +…+ xm1= b1. Аналогично для потребителя B2:
x12 + x22 +…+ xm2= b2, … и для потребителя Bn: x1n + x2n +…+ xmn= bn.
33
Все переменные должны удовлетворять условиям неотрицательности.
Итак, получили:
(1) minf = c11 x11 + c12 x12 +…+ c1n x1n +…+ cm1 xm1 +…+ cmn xmn
x + x
11 12
++ x1n = a1 ,


 x + x
m1 m2
++ x mn = a m ,
(2)

x + x
11 21
++ x m1 = b1 ,



 x + x
1n 2n
++ x mn = bn .
(3) xij ≥ 0, i = 1, m, j = 1, n.
Соотношения (1)-(3) образуют экономико-математическую модель транс-
портной задачи.
В системе ограничений ТЗ m+n уравнений с m·n переменными.
Теорема. Ранг системы ограничений для закрытой модели ТЗ на единицу
меньше, чем число уравнений, т.е. r=m+n-1.
Оптимальный план ТЗ находится также методом последовательного улучше-
ния опорного плана, но переход от одного опорного плана к другому выпол-
няется непосредственно в распределительной таблице.
Понятие цикла
Определение. Циклом называется последовательность клеток в таблице,
в которой две и только две соседние клетки расположены в одной строке или
в одном столбце и последняя клетка лежит в той же строке или столбце, что и
первая.
В цикле всегда четное число клеток, минимальное число клеток четыре
(прямоугольник). Графически цикл представляет замкнутую ломаную линию,
звено которой проходит только по строке или по столбцу, каждое звено со-
единяет две клетки цикла (возможно что ломаная самопересекающаяся).
Примеры возможных циклов:

1 3
2

5
4
34
 B1 B2 B3 B4 B5 B6 B7
A1 1-й цикл: (2,1)→(2,2) →(4,2)
* •
A2 * • →(4,1)
A3 • • 2-й цикл: (1,5) →(1,7) →(3,7)
A4 • • • • →(3,4) →(4,4) →(4,5)
Пронумеруем клетки цикла и
придадим знак + клеткам с нечетным номером и знак – с четным номером.
Весь цикл разобьется на два полуцикла: положительный полуцикл и отрица-
тельный полуцикл.
Определение. Любой набор клеток таблицы, в котором нет ни одного цикла
называется ациклическим набором. В противном случае циклическим.
Примеры ациклических наборов (в набор входят только клетки, в которых
стоит •):

B1 B2 B3 B4 B5 B1 B2 B3 B4 B5
• ° A1 • • °
A1 A2 • •
• A3 • • •
A2
• • • • • Если к каждому из наборов добавить еще одну
A3 клетку, то наборы станут циклическими (доба-
вили клетку с °).
Теорема. Любой набор из m+n клеток является циклическим, где m –
число строк в таблице, n – число столбцов.
Из теоремы следует, что наибольшее число клеток в ациклическом наборе
клеток таблице равно m+n–1 , что равно рангу системы ограничений ТЗ
(смотри теорему). Но так как r равно числу базисных переменных, то в опор-
ном решении ТЗ их будет m+n–1, остальные переменные - свободные. Если
xij является свободной переменной (xij = 0), то клетку (i, j) в распределитель-
ной таблице не заполняем и называем эту клетку свободной. Если в опорном
плане базисная переменная принимает значение ≠ 0, то в соответствующую
клетку записываем это значение и называем эту клетку занятой. Итак, в
опорном плане ТЗ должно быть m+n–1 занятых клеток. Допустимый план ТЗ
является опорным тогда и только тогда, когда занятые клетки плана образу-
ют ациклический набор клеток.
Построение начального опорного плана
Пусть дана закрытая модель ТЗ. Рассмотрим два правила построения
начального опорного плана: правило «северо-западного угла» и правило
«наименьшего тарифа».
По правилу «северо-западного угла» в первую очередь заполняется са-
мая левая верхняя клетка. Исходя из ограничений на запас и потребности,
суммы всех заполненных строк и столбцов должны быть соответственно
равны ai и bj .
Действия производим по шагам:
35
1) Заполняем клетку (1,1), принимая объем перевозки от А1 к В1 равным
x11= min(a1, b1).
2) а) Если a1 < b1, то запасы поставщика А1 полностью удовлетворены и
поэтому все остальные клетки 1-ой строки заполняем прочерками и рядом с
b1 в скобках указываем объем оставшейся потребности потребителя В1, рав-
ный a1- b1.
б) Если a1 > b1, то потребности потребителя B1 полностью удовлет-
ворены и поэтому все остальные клетки 1-го столбца заполняем прочерками
и рядом с а1 в скобках указываем объем оставшегося запаса поставщика А1,
равного b1- a1.
в) Если a1 = b1, то из рассмотрения одновременно исключается и строка
и столбец, поэтому число занятых клеток будет меньше, чем m+n–1. Такой
опорный план называется вырожденным. Чтобы устранить вырожденность
помещают «базисный» нуль в одной из клеток первой строки или первого
столбца, которые исключились из распределения, при этом лучше выбрать
клетку с меньшим тарифом.
3) Заполняем следующую самую левую верхнюю клетку, все рассуждения
аналогичны. Продолжая этот процесс получим ациклический
план, содержащий m+n–1 занятую клетку.
Отличие правила «наименьшего тарифа» только в том, что в первую
очередь заполняется клетка, содержащая наименьшую стоимость перевозки
единицы груза cij (наименьший тариф), если таких клеток несколько, то про-
извольно выбирают любую.
Замечание. План, построенный для ТЗ методом «наименьшего тарифа»,
как правило (но не всегда) дает лучшее приближение к оптимальному реше-
нию, чем план, построенный методом «северо-западного угла».
Метод потенциалов. Алгоритм решения
1 этап. Пусть найден начальный опорный план закрытой модели ТЗ, в ко-
тором m+n–1 занятых клеток образуют ациклический набор клеток.
2 этап. Каждому поставщику Аi поставим в соответствие некоторое число
ui и каждому потребителю Bj - число vj . Числа ui и vj называются потенциа-
лами, их значения выбираются так, чтобы тариф занятых клеток был равен
сумме соответствующих потенциалов
(1) ui + vj = сij (для занятых клеток), i=1,…,m и j=1,…,n.
Равенство (1) задает систему уравнений, имеющей бесконечное множество
решений (m+n переменных и m+n –1 уравнений). Поэтому одному из по-
тенциалов придают произвольное числовое значение (например, ui=0).Затем
вычисляют остальные потенциалы. Если известен потенциал ui,то потенциал
vj находится по занятой клетке, используя формулу vj= сij – ui. Если известен
потенциал vj,то потенциал ui находится по занятой клетке используя формулу
ui= сij – vj.
3 этап. Проверка опорного плана на оптимальность. Для этого вычисляют
оценки всех свободных клеток по формуле
(2) Δij =ui + vj – сij ( для свободных клеток).

36
Если все оценки свободных клеток неположительные ( ≤ 0 ), то найденный
опорный план является оптимальным. По заполненным клеткам считают
наименьшее значение целевой функции
f = c11 x11 + c12 x12 +…+ c1n x1n +…+ cm1 xm1 +cm2 xm2 +…+ cmn xmn и по запол-
ненной таблице составляют матрицу перевозок X.
4 этап. Если оценка свободной клетки положительна, то переходят к ново-
му опорному плану, делая пересчет по циклу.
Пересчет по циклу
Выбираем клетку, соответствующую наибольшей положительной оценке
и помечаем ее знаком +. Эта свободная клетка подлежит заполнению.
1 шаг: Чтобы не нарушать сбалансированности перевозки строят цикл, с на-
чалом в этой свободной клетке все остальные клетки цикла занятые. Так чис-
ло клеток (вместе со свободной) стало m+n, то цикл, по крайней мере один,
существует.
2 шаг: Последовательно обходим клетки цикла, поочередно проставляя “+”,
“-”, начиная со свободной клетки (т.е. свободной клетки всегда знак “+”). Из
всех объемов перевозок xij, записанных в клетках отрицательного полуцикла,
выбираем наименьшее количество и обозначаем его через λ.
λ=min {объем груза в клетках отрицательного полуцикла}
3 шаг: Затем в клетках + прибавляем λ , а в клетках - вычитаем λ. Все ос-
тальные клетки, не входящие в цикл оставляем без изменения. Получаем но-
вый ациклический набор клеток. И переходим к этапу 2.
Перераспределение плана перевозок по клеткам цикла называют пересчетом
по циклу, в результате пересчета общая стоимость перевозок уменьшится на
Δf=Δij ·λ , т.е fнов= fстар - Δf , поэтому можно каждый раз не пересчитывать
значение целевой функции.
Открытая модель транспортной задачи
В открытой модели ТЗ суммарный запас груза поставщиков не равен
m n
суммарной потребности потребителей:  ai ≠  b j .
i =1 j =1

Решение задачи с открытой моделью сводится к решению задачи с за-

крытой моделью.
m n
Если a > b ,
i =1
i
j =1
j
то в математическую модель задачи вводится фик-
m n
тивный потребитель Вn+1 с потребностью bn +1 =  ai −  b j , все тарифы на дос-
i =1 j =1

тавку груза потребителю Вn+1 принимаются равными 0.

m n
Если  ai <  b j , то в математическую модель задачи вводится фиктивный
i =1 j =1
n m
поставщик Am+1 с запасом am +1 =  b j −  ai , все тарифы на доставку груза от
j =1 i =1

Am+1 принимаются равными 0.

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

Практика

Пример 1: Построить цикл с началом в клетке (4,1).

B1 B2 B3 B4 B5 B6 B7
A1 • •
A2 •
A3 • • •
A4 •
A5 • • • •

Решение:
Начало цикла в клетке (4,1). Следующая клетка в цикле (3,1), затем (3,3),
(1,3), (1,4) и (4,4). Итак, получили цикл: (4,1) →(3,1) →(3,3) →(1,3) →(1,4)
→(4,4).
Пример 2: Построить начальный опорный план по правилу «северо-
западного» угла. Условия задачи заданы таблицей:

3 6 5 1 100
1 4 3 2 400
4 3 1 2 600
300 500 100 200
Решение:
m n
Проверим, что модель транспортной задачи закрытая, т.е. a = bi j = 1100 ,
i =1 j =1

заполним самую нижнюю правую клетку.

Заполним распределительную таблицу по шагам:
1) Заполняем клетку (1,1): x11= min(100,300) = 100

38
 Запасы груза, ai
B1 B2 В3 B4
3 6 5 1
A1 100 – – – 100
1 4 3 2
A2 200 200 – – 400 (200)
А3 4 3 1 2
– 300 100 200 600 (300) (200)
Потребности 300 500 100 200 1100
в грузе, bj (200) (300)

2) Запасы поставщика A1 удовлетворены полностью, поэтому ставим про-

черки в первой строке. В скобках указываем объем оставшейся потребности
(200) у потребителя В1
3) Заполняем клетку (2,1): x21= min(400,200) = 200
4) Потребности В1 удовлетворены полностью, поэтому ставим прочерки в не-
заполненных клетках первого столбца. В скобках указываем объем оставше-
гося запаса (200) у поставщика A2
5) Заполняем клетку (2,2): x22= min(200,500) = 200
6) Запасы поставщика А2 удовлетворены полностью, поэтому ставим прочер-
ки в незаполненных клетках второй строки. В скобках указываем объем ос-
тавшейся потребности (300) у потребителя В2
7) Заполняем клетку (3,2): x32= min(600,300) = 300
8) Потребности В2 удовлетворены полностью. В скобках указываем объем
оставшегося запаса (300) у поставщика А3
9) Заполняем клетку (3,3): x33= min(300,100) = 100
10) Потребности В3 удовлетворены полностью. В скобках указываем объем
оставшегося запаса (200) у поставщика А3
11) Заполняем клетку (3,4): x34= min(200,200) = 200
Таблица заполнена полностью. Получили m+n–1= 3+4 –1 = 6 занятых кле-
ток, которые образуют ациклический набор клеток.
Найдем значение целевой функции
f=3·100+ 1·200+4·200+3·300+1·100+2·200 = 2700 при найденном опорном
плане.
Пример 3: В условиях предыдущей задачи построим первоначальный опор-
ный план по правилу «наименьшего тарифа».
Решение:
Заполним распределительную таблицу по шагам:
1) Выбираем клетки с наименьшим тарифом с21=с14= с33=1 это клетки (2,1),
(1,4) и (3,3). Заполняем любую из них, например, заполняем клетку (2,1): x21=
min(400,300) = 300
2) Потребности В1 удовлетворены полностью, поэтому ставим прочерки в 1-
ом столбце. В скобках указываем объем оставшегося запаса (100) у постав-
щика А2

39
 B1 B2 В3 B4 Запасы груза, ai
3 6 5 1
A1 – – – 100 100
1 4 3 2
A2 300 – – 100 400 (100)
А3 4 3 1 2 600 (500)
– 500 100 0
Потребности 300 500 100 200 1100
в грузе, bj (100)

3) Заполняем клетку (3,3): x33= min(600,100) = 100

4) Потребности В3 удовлетворены полностью, поэтому ставим прочерки в не-
заполненных клетках третьего столбца. В скобках указываем объем остав-
шегося запаса (500) у поставщика A3
5) Заполняем клетку (1,4): x14= min(100,200) = 100
6) Запасы поставщика А1 удовлетворены полностью, поэтому ставим прочер-
ки в незаполненных клетках первой строки. В скобках указываем объем ос-
тавшейся потребности (100) у потребителя В4
7) Выбираем оставшиеся клетки с самым маленьким тарифом с24=с34= 2 это
клетки (2,4) и (3,4) Заполняем любую из них, например, заполняем клетку
(2,4): x24= min(100,100) = 100
8) Так как запасы в этой клетки равны потребностям a'2 = b'4, то получим вы-
рожденный план (занятых клеток будет меньше, чем 6). Поэтому ставим «ба-
зисный» нуль в одну из свободных клеток второй строки или четвертого
столбца, лучше выбрать клетку с наименьшим тарифом, т.е. в клетке (3,4)
ставим 0 и считаем ее занятой. В клетке (2,2) ставим прочерк.
9) Заполняем клетку (3,2): x32= min(500,500) = 500
Таблица заполнена полностью. Получили m+n–1= 3+4 –1 = 6 занятых кле-
ток, которые образуют ациклический набор клеток.
Найдем значение целевой функции f=1·100+ 1·300+2·100+3·500+1·100 = 2200
при найденном опорном плане. Из примера видно, что план построенный по
правилу «наименьшего тарифа» дает лучшее приближение к оптимальному
решению.
Пример 4: Проверить опорный план, построенный в примере 3 на оптималь-
ность.
Решение:
1 этап. Пусть построен первоначальный опорный план по правилу «наи-
меньшего тарифа», т.е. имеем 6 занятых клеток, образующих ациклический
набор (смотри пример 3).
а) В новой таблице убираем последнюю строку – потребности bj и последний
столбец – запасы аi, которые необходимы только для построения первона-
чального исходного плана.
б) Каждому поставщику Ai поставим в соответствие число ui и каждому по-
требителю Bj число vj.
40
Чтобы найти потенциалы по формуле (1), один из потенциалов в занятой
клетке должен быть определен, только тогда можно найти другой.
Каждая занятая клетка используется, причем только один раз.
2 этап. Нахождение потенциалов:
а) Пусть u1 = 0.
a`) В первой строке только одна занятая клетка (1,4) по ней мы можем найти
v4 = 1, т.к. u1 +v4= c14 , v4 = c14 – u1= 1 – 0=1

v1 = 0 v2 = 2 v3 = 0 v4 = 1
3 6 5 1
u1 = 0 – – – 100
1 4 3 2
u2 = 1 300 – – 100
4 3 1 2
u3 = 1 – 500 100 0

б) Можем использовать занятую клетку (2,4), так как в ней найден один из
потенциалов, а именно v4 = 1. Тогда u2 = 1, т.к. u2 = c24 – v4= 2 – 1=1
в) Можем использовать занятую клетку (2,1), так как в ней найден один из
потенциалов, а именно u2 = 1. Тогда v1 = 0, т.к. v1 = c21 – u2= 1 – 1= 0
г) Можем использовать занятую клетку (3,4), так как в ней найден один из
потенциалов, а именно v4 = 1. Тогда u3 = 1, т.к. u3 = c34 – v4= 2 – 1=1
д) Можем использовать занятую клетку (3,2), так как в ней найден один из
потенциалов, а именно u3 = 1. Тогда v2 = 2, т.к. v2 = c32 – u3= 3 – 1= 2
e) Можем использовать последнюю занятую клетку (3,3), так как в ней най-
ден один из потенциалов, а именно u3 = 1. Тогда v3 = 0, т.к. v3 = c33 – u3= 1 –
1= 0
3 этап. Вычисляем оценки свободных клеток по формуле (2)
Δ11 =u1 + v1 – с11 =0 + 0 – 3 = –3
Δ12 =u1 + v2 – с12 =0 + 2 – 6 = –4
Δ13 =u1 + v3 – с13 =0 + 0 – 5 = –5
Δ22 =u2 + v2 – с22 =1 + 2 – 4 = –1
Δ23 =u2 + v3 – с23 =1 + 0 – 3 = –2
Δ31 =u3 + v1 – с31 =1 + 0 – 4 = –3
Так как все оценки свободных клеток отрицательны, то найденный опорный
план оптимальный.
minf = 2200.
Пример 5: Проверить опорный план, построенный в примере 2 на оптималь-
ность.
Решение:
1 этап. Пусть построен первоначальный опорный план по правилу «северо-
западного угла», т.е. имеем 6 занятых клеток, образующих ациклический на-
бор (смотри пример 2).

41
а) В новой таблице убираем последнюю строку - потребности bj и последний
столбец - запасы аi, которые необходимы только для построения первона-
чального исходного плана.
б) Каждому поставщику Ai поставим в соответствие число ui и каждому по-
требителю Bj число vj
Чтобы найти потенциалы по формуле (1), придадим одному из потенциалов
произвольное значение, например u1 = 0.
2 этап. а) Пусть u1 = 0.
а`) В первой строке только одна занятая клетка (1,1) по ней мы можем найти
v1 = 3, т.к. u1 +v1= c11 , v1 = c11 - u1= 3 – 0

v1 = 3 v2 = 6 v3= 4 v4= 5
3 6 5 1
u1 = 0 100 – – –
1 4 3 2
u2 = –2 200 200 – –
4 3 1 2
u3 = –3 – 300 100 200

б) Можем использовать занятую клетку (2,1), так как в ней найден один из
потенциалов, а именно v1 = 3. Тогда u2 = –2, т.к. u2 = c21 – v1= 1 – 3= –2
в) Можем использовать занятую клетку (2,2), так как в ней найден один из
потенциалов, а именно u2 = –2. Тогда v2 = 6, т.к. v2 = c22 – u2= 4 – (–2)= 6
г) Можем использовать занятую клетку (3,2), так как в ней найден один из
потенциалов, а именно v2 = 6. Тогда u3 = –3, т.к. u3 = c32 – v2= 3 – 6= –3
д) Можем использовать занятую клетку (3,3), так как в ней найден один из
потенциалов, а именно u3 = –3. Тогда v3 = 4, т.к. v3 = c33 – u3= 1 – (–3)= 4
e) Можем использовать занятую клетку (3,4), так как в ней найден один из
потенциалов, а именно u3 = –3. Тогда v4 = 5, т.к. v4 = c34 – u3= 2 – (–3)= 5
3 этап. Вычисляем оценки свободных клеток по формуле (2)
Δ12 =u1 + v2 – с12 =0 + 6 – 6 = 0
Δ13 =u1 + v3 – с13 =0 + 4 – 5 = –1
Δ14 =u1 + v4 – с14 =0 + 5 – 1 = 4
Δ23 =u2 + v3 – с23 = –2 + 4 – 3 = –1
Δ24 =u2 + v4 – с24 = –2 + 5 – 2 = 1
Δ31 =u3 + v1 – с31 = –3 + 3 – 4 = –4
Так как имеется положительная оценка, то найденный опорный план не оп-
тимальный.

Пример 6: Сделать пересчет по циклу в примере 5.

Решение:
В клетке (1,4) положительная оценка Δ14 =u1 + v4 – с14 =0 + 5 – 1 = 4, поэтому
она подлежит заполнению.

42
 v1 = 3 v2 = 6 v3= 4 v4= 5
3 – 6 5 1 +
u1 = 0 100 – – –
1 + 4 – 3 2
u2 = –2 200 200 – –
4 3 + 1 2 –
u3 = –3 – 300 100 200

1 шаг: Строим цикл, с началом в клетке (1,4), все остальные клетки цикла за-
нятые.
2 шаг: Последовательно обходим клетки цикла проставляя “+ “ и “–“, начи-
ная со свободной клетки. Находим λ – наименьший объем груза в клетках от-
рицательного полуцикла: λ=min {100, 200, 200} = 100
3 шаг: В клетках со знаком “+ “ прибавляем λ, а в клетках со знаком “–“ вы-
читаем λ .
Все остальные клетки, не входящие в цикл оставляем без изменения.
Получаем новый ациклический набор клеток. Строим новую таблицу и про-
веряем найденный план на оптимальность:

v1 = –1 v2 = 2 v3= 0 v4= 1
3 6 5 1
u1 = 0 – – – 100
1 4 3 2
u2 = 2 300 100 – –
4 3 1 2
u3 = 1 – 400 100 100
2 этап: находим потенциалы u1 = 0, v4 = 1, u3 = 1, v2 = 2, v3 =0, u2 = 2
3 этап: находим оценки свободных клеток:
Δ11 =u1 + v1 – с11 =0 + (–1) – 3 = –4, Δ12 =u1 + v2 – с12 =0 + 2 – 6 = –4
Δ13 =u1 + v3 – с13 =0 + 0 – 5 = –5, Δ22 =u2 + v3 – с23 =2 + 0 – 3 = –1
Δ24 =u2 + v4 – с24 =2 + 1 – 2 = 1, Δ31 =u3 + v1 – с31 = 1 + (–1) – 4 = –4
Есть положительная оценка, следовательно, план не оптимальный
Δf=Δ14 ·λ=4·100=400, т.е. f= 2700 – 400 = 2300.
Пример 7: Найти оптимальное распределение трех видов механизмов,
имеющихся в количествах 45, 20 и 35 между четырьмя участками работ, по-
требности которых соответственно равны 10, 20, 30 и 40, при следующей
матрице производительности каждого из механизмов на соответствующем
участке:
5 4 1 5
3 5 3 1
1 6 7 6

43
Решение:
Составим первую распределительную таблицу:

Запасы меха-
v1 = 5 v2 = 9 v3 = 10 v4 = 5 низмов, ai
5 – 4 1 5 +
u1 = 0 10 – – 35 45 (35)
3 + 5 3 1 –
u2 = –4 – 15 – 5 20 (5)
1 6 7 6
u3 = –3 – 5 30 – 35
Потребности в
механизмах, bj 10 20 30 40 100
(15) (35)
1 этап: Cоставляем первоначальный опорный план по правилу «наибольшей
производительности», т.е. в первую очередь заполняем клетку с наибольшим
показателем производительности.
Найдем значение целевой функции f=5·10+ 5·35+5·15+1·5+6·5+7·30= 545 при
найденном опорном плане.
2 этап: Находим потенциалы:
u1 =0, v1 =5, v4 =5, u2 = –4, v2 =9, u3 = –3, v3 =10
3 этап: Находим оценки свободных клеток:
Δ12 =u1 + v2 – с12 =0 + 9 – 4 =5
Δ13 =u1 + v3 – с13 =0 + 10 – 1 =9
Δ21 =u2 + v1 – с21 = –4 + 5 – 3 = –2
Δ23 =u2 + v3 – с23 = –4 + 10 – 3 = 3
Δ31 =u3 + v1 – с31 = –3 + 5 – 1 =1
Δ34 =u3 + v4 – с34 = –3 + 5 – 6 = –4
Так как есть отрицательные оценки (ищем max), то найденный опорный план
не оптимальный. Выбираем любую из клеток (2,1) или (3,4).
4 этап: Выбираем клетку (2,1) и делаем пересчет по циклу.
1 шаг: строим цикл, с началом в клетке (2,1) все остальные клетки занятые.
2 шаг: последовательно обходим клетки цикла проставляя “+ “ и “–“, начи-
ная со свободной клетки. Находим λ – наименьший объем груза в клетках от-
рицательного полуцикла: λ=min {10, 5} = 5
3 шаг: В клетках со знаком “+ “ прибавляем λ, а в клетках со знаком “–“ вы-
читаем λ .
Все остальные клетки, не входящие в цикл оставляем без изменения. Получа-
ем новый ациклический набор клеток. Δf=Δ21 ·λ = –10 , т.е. f = 555
Строим новую таблицу (последний столбец и последнюю строку удаля-
ем) и возвращаемся ко второму этапу:

44
 v1 = 5 v2 = 7 v3 = 8 v4 = 5
5 + 4 1 5 –
u1 = 0 5 – – 40
3 – 5 + 3 1
u2 = –2 5 15 – –
1 6 – 7 6 +
u3 = –1 – 5 30 –

2 этап: Находим потенциалы: u1 = 0, v1 = 5, v4 = 5, u2 = –2, v2 = 7, u3 = –1,

v3 =8
3 этап: Находим оценки свободных клеток
Δ12 =u1 + v2 – с12 =0 + 7– 4 =3
Δ13 =u1 + v3 – с13 =0 + 8 – 1 =7
Δ23 =u2 + v3 – с23 = –2 + 8 – 3 = 3
Δ24 =u2 + v4 – с24 = –2 + 5 – 1 = 2
Δ31 =u3 + v1 – с31 = –1 + 5 – 1 = 3
Δ34 =u3 + v4 – с34 = –3 + 5 – 6 = –4
Так как есть отрицательная оценка (ищем max), то найденный опорный план
не оптимальный.
4 этап: Выбираем клетку (3,4) и делаем пересчет по циклу.
1 шаг: строим цикл, с началом в клетке (3,4) все остальные клетки занятые.
2 шаг: последовательно обходим клетки цикла проставляя “+ “ и “–“, начи-
ная со свободной клетки. Находим λ – наименьший объем груза в клетках от-
рицательного полуцикла: λ=min {40, 5, 5} = 5
3 шаг: В клетках со знаком “+ “ прибавляем λ, а в клетках со знаком “–“ вы-
читаем λ .
Все остальные клетки, не входящие в цикл оставляем без изменения. Получа-
ем новый ациклический набор клеток. Δf=Δ21 ·λ = –10 , т.е. f=555
Δ34 =u3 + v4 – с34 = –1 + 5 – 6 = –2
Так как есть отрицательные оценки (ищем max), то найденный опорный план
не оптимальный. Δf=Δ34 ·λ = –10 , т.е. f = 565
Строим новую таблицу и возвращаемся ко второму этапу.
2 этап: Находим потенциалы: u1 =0, v1 =5, v4 =5, u3 =1, v2 =5, v3 =6, u2 =0
3 этап: Находим оценки свободных клеток
Δ12 =u1 + v2 – с12 =0 + 5– 4 =1
Δ13 =u1 + v3 – с13 =0 + 6 – 1 =5
Δ21 =u2 + v1 – с21 =0+ 5 – 3 = 2
Δ23 =u2 + v3 – с23 =0 + 6 – 3 = 3
Δ24 =u2 + v4 – с24 =0 + 5 – 1 = 4
Δ31 =u3 + v1 – с31 =1 + 5 – 1 = 5

45
 v1 = 5 v2 = 5 v3 = 6 v4 = 5
5 4 1 5
u1 = 0 10 – – 35
3 5 3 1
u2 = 0 – 20 – –
1 6 7 6
u3 = 1 – 0 30 5

Так как все оценки свободных клеток положительны, то найденный опорный

план оптимальный.
Ответ: maxf=565 и оптимальное распределение механизмов на четыре уча-
стка работ имеет вид:
10 0 0 35 
 
X =  0 20 0 0  .
*

 0 0 30 5 
 

Рекомендации по организации самостоятельной работы студентов

с помощью электронного учебно-методического пособия

В разделе теория (в подразделе «Понятие цикла») анимация позволяет

наглядно увидеть построение цикла для каждой пустой клетки таблицы (при
нажатии левой клавиши мыши на пустую клетку). Также анимация позволяет
постепенно, пошагово заполнять распределительную таблицу, используя
правила «северо-западного угла» и «наименьшего тарифа» (в подразделе
«Построение начального опорного плана»), упрощает понимание метода по-
тенциалов, пересчета по циклу, решение распределительной задачи в соот-
ветствующих подразделах.

В практикуме кроме обычного режима демонстрации решения задач

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

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

В тестирование по данной теме входит десять задач, оцениваемых, в

зависимости от сложности, в один, два или три балла. Для успешного прохо-
ждения теста необходимо набрать девять или более баллов из семнадцати.

47
 БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Сборник задач по высшей математике для экономистов: учебное посо-

бие / под ред. В.И. Ермакова. – М.: ИНФРА-М, 2007. – 575 c.
2. Малиновский, Ю.Г. Элементы математического программирования /
Ю.Г. Малиновский. – Челябинск: Изд-во ЧГТУ, 1995. – 100 с.
3. Малиновский, Ю.Г. Высшая математика: Задания и методические
указания по выполнению контрольных работ по специальности «Экономика
и управление в строительстве»/ Ю.Г. Малиновский, Н.И. Шильникова, А.Г.
Лямин / под ред. Л.В.Матвеевой. – Челябинск: Изд-во ЧГТУ, 1996. – 62 с.
4. Исследование операций в экономике : учеб. пособие для вузов /
Н.Ш. Кремер, Б.А. Путко, И.М. Тришин и др; под ред. Н.Ш. Кремера. – М.:
ЮНИТИ, 2003. – 407 с.
5. Акулич, И.Л. Математическое программирование в примерах и зада-
чах: учеб. пособие для студентов эконом. спец. вузов. – М.: Высш. шк., 1986.
– 319 с.
6. Кузнецов, А.В. Руководство к решению задач по математическому
программированию / А.В. Кузнецов, Н.И. Холод, П.С. Костевич – Минск:
Вышэйш. школа, 1978. – 256 с.

48
 ОГЛАВЛЕНИЕ

Введение………………………………………………………………………... 3
Объем дисциплины и виды учебной работы………………………………… 10
Содержание курса
Тема 1: Построение математических моделей…………………………. 10
Теория………………………………………………………….......... 10
Практика……………………………………………………….......... 11
Рекомендации по организации самостоятельной работы студен-
тов с помощью электронного учебно-методического посо-
бия………………………………………………………………....... 12
Тема 2: Различные формы ЗЛП и переход от одной формы к другой 12
Теория……………………………………………………………….. 13
Практика…………………………………………………………..…. 14
Рекомендации по организации самостоятельной работы студен-
тов с помощью электронного учебно-методического посо-
бия…………………………………………………………………… 16
Тема 3: Свойства решений ЗЛП. Метод перебора. Геометрический
метод решения ЗЛП …………………………………………………… 16
Теория……………………………………………………………….. 16
Практика………………………………………………………….….. 17
Рекомендации по организации самостоятельной работы студен-
тов с помощью электронного учебно-методического посо-
бия………………………………………………………………….. 21
Тема 4: Симплекс-метод……………………………………………….. 22
Теория………………………………………………………………. 22
Практика…………………………………………………………….. 23
Рекомендации по организации самостоятельной работы студен-
тов с помощью электронного учебно-методического посо-
бия………………………………………………………………….. 24
Тема 5: Метод искусственного базиса…………….………………….. 25
Теория……………………………………………………………….. 25
Практика…………………………………………………………….. 26
Рекомендации по организации самостоятельной работы студен-
тов с помощью электронного учебно-методического посо-
бия…………………………………………………………………… 28
Тема 6: Теория двойственности……..…………….…………………… 28
Теория……………………………………………………………….. 28
Практика…………………………………………………………….. 30
Рекомендации по организации самостоятельной работы студен-
тов с помощью электронного учебно-методического посо-
бия…………………………………………………………………… 32
Тема 7: Транспортная задача………..…………….…………………… 32
Теория………………………………………………………………... 32
49
 Практика……………………………………………………………... 38
Рекомендации по организации самостоятельной работы студен-
тов с помощью электронного учебно-методического посо-
бия…………………………………………………………………… 46
Библиографический список…………………………………........................ 48

50
 Надежда Васильевна Муравьева

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Учебное пособие
для самостоятельной работы студентов

Техн. редактор А.В. Миних

Издательский центр Южно-Уральского государственного университета

Подписано в печать 03.10.2011. Формат 60×84 1/16. Печать цифровая.

Усл. печ. л. 3,02. Тираж 100 экз. Заказ 316/589. Цена С.

Отпечатано в типографии Издательского центра ЮУрГУ.

454080, г. Челябинск, пр. им. В.И. Ленина, 76.

51