Линейная производственная задача

1. Линейная производственная задача

Постановка задачи:

Сформулировать линейную производственную задачу и составить ее математическую модель.

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

В последней симплексной таблице указать обращенный базис Q-1,

соответствующий оптимальному набору базисных неизвестных.

Проверить выполнение соотношения  H = Q-1 * B.

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

Исходные данные:

Имеется фирма, на которой предполагается выпуск четырех видов изделий : в объемах 112 т,32 т,46 т, соответственно, где :

 

 

 

 

Фирма располагает тремя видами ресурсов:

фурнитура-112 т,

фанера-32 т,

доска-46 т,

 

 

Известна технологическая матрица А, в которой каждый элемент означает необходимое количество i-го  ресурса для i-го  продукции:

 

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

 

Также известен вектор удельной прибыли C, элементы которого cj означают прибыль от производства единицы продукции j-го вида:

 

Требуется :

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

Решение:

Математическая модель задачи: найти производственную программу

                                         

максимизирующую прибыль

Z =    → max                       (1)

           (критерий оптимальности)                   (целевая функция)

 

Система ограничений по ресурсам:

                                      (2)

 

Где по смыслу задачи

                                     (3)

 

Данная модель (1,2,3) является линейной, т.к. все неизвестные модели в степени не выше единицы и отсутствуют производные переменные , следовательно, для решения задачи будем использовать метод программирования ,в основе которого лежит симпликсный метод.

Введя дополнительные неотрицательные неизвестные, , заменяем неравенства (2) следующим видом:

                       (2)

 

Где дополнительные переменные имеют смысл остатков соответствующих ресурсов Среди всех решений системы уравнений (4), удовлетворяющий условию неотрицательности

 

Надо найти то решение, при котором функция (1) примет наибольшее значение.

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

,,,=32,46

Первые четыре компоненты которого определяют производственную программу

,

По которой мы пока ничего не производим.

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

 

 

 

Мы пока сохраняем в общем решении ,и увеличиваем только . При этом значение базисных переменных должны оставаться неотрицательными ,что  приводит к системе неравенств:

       или        т.е   .

 

Дадим наибольшее значение при нулевых значениях других свободных неизвестных, и подставим его в общее решение(4). Получаем для системы уравнений (4) частное неотрицательное решение:

,=0,,=0, ,(6)

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

)==

а разрешающим элементом будет =4.

 

Приравняв к нулю свободные переменные получаем базисное неотрицательное решение ,совпадающее с (6) ,причем первые четыре его компонента определяют новую производственную программу

 =0                                                  (7)

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

 

Из последнего уравнения системы (7) выражаем базисную переменную через свободные и подставляем в (1). Получаем:

(19) в методичке                                                   (8)

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

                                                         (9)

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

И припишем его к системе (4). Получается вспомогательная система уравнений.

                         (12)

 

 

 

 

Применим симплексный метод к решению этой задачи. Процесс решения приведен в (таблице1)

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

                                                                                                             

 

 

 

                             

                                                                                                                                                   (таблица1)

					28	14	11	20	0	0	0
Č	Базис
0			112		4	2	2	4	1	0	0
0			32		2	3	1	0	0	1	0
0			46		1	4	0	2	0	0	1
			F0 = 0		-28	-14	-11	-20	0	0	0
0			48		0	-4	0	4	1	-2		0
0			16		1	3/2	1/2	0	0	1/2		0
28				30	0	5/2	-1/2	2	0	-1/2		1
				448	0	28	-3	-20	0	-14		0
0				12	0	-1	0	1	1/4	-1/2		0
20				16	1	3/2	1/2	0	0	1/2		0
28		F		6   688	0   0	9/2   8	-1/2   3	0   0	-1/2   5	1/2   4		1   0

 

 

 

 

 

 

 

 

 

 

 

 

2.Задача оптимального  пополнения недостающих ресурсов.

Исходные данные:

	Б	H
14		12	0	-1	0	1	1/4	–1/2	0
28		16	1	3/2	½	0	0	½	0
0		6	0	9/2	-1/2	0	–1/2	1/2	1
		688	0	8	3	0	5	4	0

 

Формулировка задачи:

При выполнении оптимальной производственной программы первый и второй ресурсы используются полностью, тем самым они образуют "узкие места" производства. Будем их заказывать дополнительно, а третий ресурс будет в избытке, при этом матрицу (столбец) нужно представить так:.Так как мы будем использовать найденные двойственные оценки ресурсов должно выполняться условие H+×T≥0 .

Требуется:

Найти вектор T(, максимизирующий суммарный прирост прибыли при условии сохранения двойственных оценок ресурсов, и, следовательно, структуры производственной программы.

Математическая модель задачи:

W=4+3        → max                                                                                        (1)

+ × ≥                                                      (2)

,                                                                                                        (3)

                                                                                           (4)

Решение задачи:

Решение задачи имеет графический вид.

1)

 

2)

3)

t1 ≤ 112/3, t2 ≤ 32/3

t1≥0,  t2≥0

Решим эту задачу графически:

По графику видно, что решение данной задачи находится в точке А(68/3; 32/3) и имеет вид: t1=68/3, t2=32/3, t3=0 и прирост прибыли составит:

 

W= 5t1+4t2=5*68/3 + 4*32/3 = 156

 

 

3. Динамическое программирование. Распределение капитальных вложений.

 

Динамическое программирование - это вычислительный метод для решения задач управления определённой структуры. Данная задача с n переменными представляется как много шаговый процесс принятия решений. На каждом шаге определяется экстремум функции только от одной переменной.

 

Рассмотрим нелинейную задачу распределения ресурсов между предприятиями отрасли.

 

Имеются n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через fj(xj) прирост мощности  или прибыли на  j-том предприятии, если оно получит  xj рублей капвложений. Требуется найти такое распределение (х1, х2, ..., хn) капвложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли

 

Z=f1(x1)+f2(x2)+...+fn(xn)

 

при ограничении по общей сумме капвложений

 

х1 + х2 +...+хn = b

 

причём будем считать, что все переменные xj принимают только целые значения xj =1,2,...

 

Функции fj(xj) мы считаем заданными, заметив, что их определение - довольно трудоёмкая экономическая задача.

 

Воспользуемся методом динамического программирования для решения этой задачи.

 

Введём параметр состояния и определим функцию состояния. За параметр состояния x  примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния Fk(x) определим как максимальную прибыль на первых  k  предприятиях, если они вместе получат x рублей. Параметр x может меняться от 0 до b. Если из x рублей k-ое предприятие  получит Хк  рублей, то каково бы ни было это значение, остальные x-Хк  рублей естественно распределить между предприятиями от 10-го до (к-1)-го предприятия, чтобы была получен максимальная прибыль Fk-1(x-xk). Тогда прибыль k предприятий будет равна fk(xk) + Fk-1(x-xk). Надо выбрать такое значение xk между 0 и x, чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению: