Применение методов линейного программирования для решения экономических задач

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

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

1. если  прямая задача является задачей  максимизации, то двойственная будет  задачей минимизации, и наоборот;

2. коэффициенты  целевой функции прямой задачи  становятся свободными членами  ограничений двойственной задачи;

3. свободные  члены ограничений прямой задачи  становятся коэффициентами целевой  функции двойственной задачи;

4. матрица  ограничений двойственной задачи  получается путем транспортирования  матрицы ограничений прямой задачи;

5. знаки  неравенств в ограничениях изменяются  на противоположные;

6. число  ограничений прямой задачи равно  числу переменных двойственной задачи, и наоборот.

Виды  математических моделей двойственных задач могут быть представлены в  таблице (табл. 1.1).

 

Таблица 1.1

Виды  математических моделей двойственных задач

Исходная задача	Двойственная задача
Несимметричные задачи
Симметричные задачи

 

Таким образом, прежде чем записать двойственную задачу для данной исходной, систему ограничений  исходной задачи необходимо привести к соответствующему виду. [3, с.114-115]

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

 

 (1.10)

 

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

Двойственную  задачу выгоднее решать, чем прямую, если в прямой задаче при малом  количестве переменных имеется большое  количество ограничений. [2, c 70-71]

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

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

1. Находят  псевдоплан задачи.

2. Проверяют  этот псевдоплан на оптимальность.  Если псевдоплан оптимален, то  найдено решение задачи. В противном  случае либо устанавливают неразрешимость  задачи, либо переходят к новому  псевдоплану.

3. Выбирают  разрешающую строку с помощью  определения наибольшего по абсолютной  величине отрицательного числа  столбца вектора Р₀ и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+1)–и строки к соответствующим отрицательным элементам разрешающей строки.

4. Находят  новый псевдоплан и повторяют  все действия начиная со второго  этапа.

Двойственный  симплексный метод называют также  методом последовательного уточнения оценок, поскольку угловые точки задачи, возникающие при итерациях, можно рассматривать как приближенные значения точной оценки у*, т. е. как приближенные оценки влияния условий задачи на величину минимума целевой функции. [2, c.87-92]

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

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

Метод решения  таких задач, предложенный Гомори, основан  на симплексном методе и состоит  в следующем. Симплексным методом  находится оптимальный план задачи без учета условия целочисленности. Если оптимальный план целочисленный, то вычисления заканчивают; если же оптимальный план содержит хотя бы одну дробную компоненту X_i, то накладывают дополнительное ограничение, учитывающее целочисленность компонент плана, и вычисления симплексным методом продолжают до тех пор, пока либо будет найден целочисленный оптимальный план, либо доказано, что задача не имеет целочисленных оптимальных планов. [3 c.122-123]

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

2. ПРактическая чаСть проекта

 

2.1 Решение транспортной задачи методом потенциалов

 
Задача:

Таблица 1

 

Поставщики	Потребители						Запасы  поставщика
	1		2	3	4	5
1	14		10	2	5	10	50
2	11		5	4	11	3	20
3	9		8	12	1	18	30
4	1		4	9	17	18	40
Потребность потребителей		15	30	65	20	10

Имеется 4 склада содержащие некоторое количество единиц однотипной продукции, имеется  также 5 потребителей нуждающихся в  определенном количестве данной продукции. При перевозке одной единицы  продукции со склада i потребителю j возникают издержки C_ij.. При перевозке K единиц продукции со склада i потребителю j суммарные затраты на перевозку составляют K*C_ij. 
 
Требуется найти такой план перевозок при котором общие затраты на перевозку всей продукции, по всем потребителям, будут минимальны.

Шаг1: 
Проверка на сбалансированность

Сумма общих  потребностей потребителей равна: 15+30+65+20+10=140

Сумма общих  запасов поставщиков равна: 50+20+30+40=140

Сумма общих потребностей и общих  запасов - равны: 140

=140

 

Вывод: задача является сбалансированной, т.е. закрытой. 
 

 
Шаг:2 
Отыскание начального решения. Метод северо-западного угла

Запишем настоящую задачу в виде транспортной таблицы. В верхней строке перечислим потребности потребителей по порядку  номеров. В левом столбце перечислим имеющиеся запасы на складах. На пересечении j-го столбца и i-й строки будем  записывать количество продукции, поставляемое с i-го склада j-му потребителю. Пока начальное  решение не найдено, оставим эти  клетки пустыми.

	b1= 15	b2= 30	b3= 65	b4= 20	b5= 10
a1= 50
a2= 20
a3= 30
a4= 40

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

	b1= 15	b2= 30	b3= 65	b4= 20	b5= 10
a1= 50	X					50
a2= 20						20
a3= 30						30
a4= 40						40
	15	30	65	20	10

 

Итерация: 1 
Заполним клетку a₁,b₁. 
Сравним значения остатков для производителя a₁ и потребителя b₁.

Нераспределенных  остатков по потребностям для b₁ меньше, запишем меньшее число в клетку a₁,b₁ одновременно вычитая его из обеих клеток остатков. При этом клетка остатков по потребностям обнулится, указывая, что все потребности для b₁ удовлетворены. Поэтому исключим столбец b₁ из дальнейшего рассмотрения (серый фон).  
Ненулевое значение остатка по запасам для a₁ показывает, сколько единиц продукции у него осталось не потребленной.

	b1= 15	b2= 30	b3= 65	b4= 20	b5= 10
a1= 50	15	X				35
a2= 20						20
a3= 30						30
a4= 40						40
	0	30	65	20	10