Решение линейной программы симплексным методом в обычном, целочисленном и частично целочисленном вариантах в среде MatLAB

Федеральное агентство по образованию Российской Федерации

Государственное образовательное  учреждение  
высшего профессионального образования

Кузбасский государственный технический  университет

Кафедра вычислительной техники и  информационных технологий

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

К КУРСОВОЙ РАБОТЕ

по дисциплине «Исследование операций в экономике»

на тему:

«Решение линейной программы симплексным методом в обычном, целочисленном и частично целочисленном вариантах в среде MatLAB» 

 

 

 

Выполнил:

студент гр. ПИ-031

Трофимов Иван Евгеньевич

Научный руководитель:

Тынкевич Моисей Аронович, кандидат физико-математических наук, профессор

Кемерово - 2006 г.

 

СОДЕРЖАНИЕ

 

СОДЕРЖАНИЕ 2

ВВЕДЕНИЕ 3

ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 4

1. Формы   задачи   линейного   программирования. 4

2. Переход  к   канонической   форме. 7

СИМПЛЕКС-МЕТОД 8

1. Теоретические   основы   симплекс-метода. 8

2. Прямой   алгоритм   симплексного   метода 12

МЕТОД ГОМОРИ 14

ЗАКЛЮЧЕНИЕ 17

СПИСОК ЛИТЕРАТУРЫ 18

 

                                ВВЕДЕНИЕ

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

Из практики рассмотрения задач математического программирования следует, что в общем виде решить их практически невозможно. Целесообразно рассматривать отдельные классы (виды) задач. Для каждого такого класса удается сформулировать алгоритм решения, приемлемый только для данного класса задач. Наиболее разработанными в математическом программировании являются задачи линейного программирования(ЛП).  
ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1. Формы   задачи   линейного   программирования.

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

                                   (1.1)

на некотором  множестве D Ì Rⁿ ,где x Î D удовлетворяют системе ограничений

…

…

                  (1.2)

и, возможно, ограничениям

                             (1.3)

He умаляя общности, можно считать, что в системе (1.2) первые т ограничений являются неравенствами, а последующие — l-уравнениями. Очевидно, этого всегда можно добиться за счет простого переупорядочения ограничений. Относительно направления знака неравенства будем предполагать, что левая часть меньше или равна правой. Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеют противоположный знак. Ограничения (1.3), вообще говоря, могут быть рассмотрены как частный случай ограничений в форме неравенств, но в силу особой структуры их обычно выделяют отдельно и называют условиями неотрицательности (или тривиальными ограничениями).

Дополнительно следует заметить, что выбор типа искомого экстремума (максимума или  минимума) также носит относительный характер. Так, задача поиска максимума функции

                    (1.4)

эквивалентна  задаче поиска минимума функции

             (1.5)

Часто условия  задачи (1.1) - (1.3), содержащей ограничения  только типа неравенств, бывает удобно записывать в сокращенной матричной форме

                  (1.6)

где с и x — векторы из пространства Rⁿ, b — вектор из пространства R^m, a А — матрица размерности m ´ п.

Задачу  линейного программирования, записанную в форме (1.1) - (1.3), называют общей задачей  линейного программирования (ОЗЛП).

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

                   (1.7)

Поскольку любая оптимизационная задача однозначно определяется целевой функцией f и областью D, на которой отыскивается оптимум (максимум), будем обозначать эту задачу парой (D, f).

Условимся относительно терминологии, которая  используется в дальнейшем и является общепринятой в теории линейного программирования.

Планом  ЗЛП называется всякий вектор х из пространства Rⁿ.

Допустимым планом называется такой план ЗЛП, который удовлетворяет ограничениям (1.2)-(1.3), т. е. содержится в области D. Сама область D называется при этом областью допустимых планов. Оптимальным планом х^* называется такой допустимый план, при котором целевая функция достигает оптимального (в нашем случае — максимального) значения, т. е. план, удовлетворяющий условию

max f(x) = f(x^*).

Величина f^* = f(x^*) называется оптимальным значением целевой функции.

Решением  задачи называется пара (х^*, f^*), состоящая из оптимального плана и оптимального значения целевой функции, а процесс решения заключается в отыскании множества всех решений ЗЛП.

 

2. Переход  к   канонической   форме.

Подавляющее большинство известных методов решения задач линейного программирования предназначены для канонических задач. Поэтому начальный этап решения всякой общей задачи линейного программирования обычно связан с приведением ее к некоторой эквивалентной канонической задаче.

Общая идея перехода от ОЗЛП к КЗЛП достаточно проста:

• ограничения в виде неравенств преобразуются в уравнения за счет добавления фиктивных неотрицательных переменных , которые одновременно входят в целевую функцию с коэффициентом 0, т. е. не оказывают влияния на ее значение;
• переменные, на которые не наложено условие неотрицательности, представляются в виде разности двух новых неотрицательных переменных:

• переменные, на которые наложено условие неположительности, представляются в виде новой неотрицательной переменной помноженной на -1:

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

 

СИМПЛЕКС-МЕТОД

1. Теоретические   основы   симплекс-метода.

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

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

Пусть стоит  задача максимизации

                                                 (2.1)

при условиях

    ,                                            (2.2)

X_j³ 0, j=1,…,n .                                            (2.3)

Предположим, что нам удалось найти опорный  план X⁰, в котором, например, первые m компонент отличны от нуля:

X⁰=(X₁⁰,X₂⁰,…,X_m⁰, 0, …, 0) ,                                       (2.4)

и соответствующий  базис Б=(A₁,A₂,…,A_m).

Попытаемся  выбрать другую систему базисных векторов с целью построения нового опорного плана, в котором k-я переменная (k>m) принимает значение Q >0:

X(Q) = (X₁(Q), X₂(Q),…,X_m(Q),  0, …,Q, … 0) .                   (2.5)

Подставляя (2.4) в (2.2), имеем

    .                                                (2.6)

Подставив  (2.5)  в (2.2),  получаем

    .                                      (2.7)

Разложим  вектор A_k по векторам исходного базиса

    .                                           ( 8 )

В общем  случае для получения коэффициентов  такого разложения придется решать систему m уравнений с m неизвестными, которая имеет единственное решение, поскольку базисные векторы линейно независимы и соответствующая матрица имеет ненулевой определитель. Заметим, что в ситуации, когда базисные векторы являются единичными (образуют единичную матрицу), искомые коэффициенты совпадают с компонентами исходного вектора; поэтому в дальнейшем мы предпочтем работать с единичным базисом.

Подставляя (2.6) и (2.8) в (2.7), получаем

,                       (2.9)

откуда имеем

                 (2.10)

Так как система  уравнений (2.10) имеет единственное решение, то получаем представление первых m компонент нового плана

                   (2.11)

Естественно потребовать неотрицательность  компонент нового плана. Так как  нарушение неотрицательности в (2.11) может возникнуть лишь при Z_jk>0, то значение Q нужно взять не превышающим наименьшего из отношений к положительным Z_jk.

Если  к тому же учесть, что число положительных (базисных) компонент опорного плана  должно оставаться равным m, то одну из первых m (ненулевых) компонент исходного плана обращаем в нуль выбором

.                                                   (2.12)

Подставляя (2.11) в (2.1), имеем

.     (2.13)

Если  обозначить

,                                                   (2.14)

,                                                    (2.15)

то (2.13) примет вид

.                             ( 16 )

 

Из полученных соотношений напрашиваются следующие  выводы.

Критерий 1 (критерий оптимальности). Если все D_k ³ 0, то выбранный план для задачи максимизации является оптимальным.

Критерий 2. Если обнаруживается некоторое D_k < 0 и хотя бы одно из значений Z_jk >0, то переход к новому плану увеличит значение целевой функции.

Этот  вывод с очевидностью следует  из (2.16); в такой ситуации согласно (2.12) полагаем k-ю переменную равной Q и преобразуем значения остальных (базисных) переменных в соответствии с (2.11).

Критерий 3. Если обнаруживается некоторое D_k < 0, но все Z_jk£0, то линейная форма задачи не ограничена по максимуму.

Этот  вывод следует из того, что согласно (2.11) компоненты нового плана сохраняют неотрицательность при любом Q>0 (в том числе и при сколь угодно большом) и согласно (2.16) появляется возможность неограниченного изменения значения целевой функции.

Предположение о том, что базисными являются первые m компонент плана, не является принципиальным, и указание диапазона по j от 1 до m в (2.11)-(2.15) можно заменить на указание о принадлежности к базису “jÎБ“.

Если  все опорные планы задачи являются невырожденными (число положительных  компонент равно m), то Q отлично от нуля и переход к новому плану согласно (2.16) изменяет значение целевой функции, что гарантирует достижение экстремума за конечное число шагов. При наличии вырожденных планов возможно т. н. зацикливание (возврат к ранее рассмотренным планам), но на практике зацикливание никогда не возникало.

 

2. Прямой   алгоритм   симплексного   метода

Пусть исходная задача приведена к канонической форме и начальный базис образует единичную матрицу. Тогда базисные компоненты опорного плана совпадают  с правыми частями ограничений  и коэффициенты Z_jk разложения вектора X_k по такому базису совпадают с компонентами этого вектора.

Для единообразия описания вычислительной процедуры  в дальнейшем  будем пользоваться т.н. симплексной таблицей вида:

C	Базис	План	C1	C2	. . .	Cm	Cm+1	. . .	Ck	. . .	Cn
баз	плана	X	X1	X2	. . .	Xm	Xm+1	. . .	Xk	. . .	Xn
С1	X1	B1	1	0	. . .	0	Z1m+1	. . .	Z1k	. . .	Z1n
С2	X2	B2	0	1	. . .	0	Z2m+1	. . .	Z2k	. . .	Z2n
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
Cm	Xm	Bm	0	0	. . .	1	Zmm+1	. . .	Zmk	. . .	Zmn
Zk		L(X)	Z1	Z2	. . .	Zm	Zm+1	. . .	Zk	. . .	Zn
Dk			D1	D2	. . .	D m	D m+1	. . .	Dk	. . .	Dn