ВУЗ:
Составители:
Лабораторная работа 10
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Цель работы: освоение методов автоматизированного решения задач линейного программирования с использованием па-
кетов прикладных программ.
Методические указания
Для решения задачи методом линейного программирования необходимо, чтобы описанная в ней ситуация отвечала
пяти основным условиям.
Во-первых, она должна быть связана с ограниченными ресурсами (т.е. ограниченное число рабочих, оборудования,
финансов и т.д.), в противном случае этой задачи просто бы не существовало. Во-вторых, необходимо сформулировать
точную цель (максимальная прибыль или минимальные затраты). В-третьих, задача должна характеризоваться линейно-
стью (например, если на изготовление детали требуются три часа, то на изготовление двух будет затрачено шесть часов, на
выпуск трех – девять и т.д.) В-четвертых, задача должна характеризоваться однородностью (изделия, изготовленные на
станке, идентичны; все часы, в течение которых рабочий выполняет ту или иную операцию, используются им с одинаковой
продуктивностью). Пятое условие заключается в делимости: метод линейного программирования строится на допущении,
что результат и ресурсы можно разделить на доли. Если такое деление невозможно, например, полет половины самолета
или прием на работу одной четвертой служащего, аналитику лучше всего воспользоваться специальной модификацией ли-
нейного программирования – дискретным (целочисленным) программированием.
Методы линейного программирования могут применяться, если построена только одна цель: максимизировать (на-
пример, прибыль) или минимизировать (например, издержки). Когда целей несколько, используют целевое программиро-
вание. Если же задача эффективнее всего решается поэтапно или по временным интервалам, аналитику следует исполь-
зовать метод динамического программирования. В еще более сложных задачах при решении могут понадобиться другие
варианты данного метода, например нелинейное или квадратичное программирование.
Модель линейного программирования. Формально выражаясь, задача линейного программирования связана с оп-
тимизацией процесса, в ходе которого отбираются неотрицательные искомые переменные X
1
, Х
2
, ..., Х
у
, используемые
затем для максимизации (или минимизации) целевой функции в следующей форме.
Максимизировать (минимизировать) целевую функцию
nn
XCXCXCF +
+
+
=
...
2211
(1)
при условии ограничений на количество ресурсов, выраженных в таком виде:
≤+++
≤+++
≤+++
,...
...
;...
;...
2211
22222121
11212111
mnmnnn
nn
nn
BXAXAXA
BXAXAXA
BXAXAXA
(2)
где C
n
, A
mn
, B
m
– заданные постоянные величины.
В зависимости от типа задачи ограничения могут указываться также с использованием знака «равенство» (=) или
знака «больше или равно» (≥).
Допустимым решением или планом задачи линейного программирования называется вектор P = (X
1
, X
2
, …, X
n
), удовле-
творяющий условиям (2).
Множество планов в геометрической интерпретации представляет собой выпуклый многогранник.
План, который обращает в равенство хотя бы n независимых ограничений задачи, называется опорным планом.
Опорный план соответствует некоторой вершине многогранника планов.
Опорный план содержит не свыше m положительных компонент (m – число независимых ограничений задачи).
Опорный план, содержащий менее m положительных компонент, называют вырожденным.
Оптимальный план является опорным (если оптимум достигается на двух опорных планах, то оптимальны все пла-
ны, соответствующие отрезку, соединяющему соответствующие вершины).
Основным численным методом решения задач линейного программирования является симплексный метод.
Доказано, что оптимальное решение задачи линейного программирования связано с угловыми точками многоуголь-
ника решений, т.е. с опорными планами. Они определяются системой m линейно независимых векторов, содержащихся в
системе из n векторов A
1
, …, A
n
. Количество опорных планов меньше
m
n
C
, где n – число неизвестных, а m – число ограни-
чений. При больших n и m найти все их перебором очень трудно, поэтому необходим упорядоченный перебор, такой
схемой является симплексный метод, который позволяет исходя из известного опорного плана задачи за конечное число
шагов получить ее оптимальный план. Каждый из шагов (итераций) состоит в нахождении нового плана, которому соот-
ветствует меньшее для задачи на минимум (большее для задачи на максимум) значение линейной формы, чем ее значение
в предыдущем плане. Процесс продолжается до получения оптимального плана. Если задача не обладает планами или ее
линейная форма неограничена на многограннике решений, то симплексный метод позволяет установить это в процессе
решения.
При использовании симплексного метода пользуются симплексными таблицами следующего вида [2]:
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
