Обоснование принятия оптимальных решений для хлебозавода

Размещено на http://www.allbest.ru/

Обоснование принятия оптимальных решений для хлебозавода



Введение

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

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

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

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

Задачи выполнения типового расчета:

- научиться строить экономико-математические модели;

- освоить симплекс-метод табличного решения задачи линейного программирования;

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

- освоить метод потенциалов решения транспортной задачи;

- освоить методику решения антагонистических игр;

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



1. Особенности обоснования принятия оптимальных решений для хлебозавода

Хлебозавод - одно из старейших предприятий хлебопекарной отрасли России. Он ведет свою историю с октября 1934 года, когда с конвейера сошла первая партия продукции.

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

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

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

Дальнейшее развитие и совершенствование производственной базы завода шло рука об руку с техническим прогрессом. На хлебозавод внедрялись новые технологии производства, и оставалось неизменным качество хлеба - эталонное, ГОСТовское.

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

Мука доставляется в цистернах муковозов, а дрожжи, соль, сахар, жир и т.д. - специализированными автомашинами. На заводе мука хранится в бункерах; её транспортирование осуществляется пневматическим способом. Остальное сырьё хранится в жидком виде в ёмкостях и транспортируется по трубопроводам. Дозирование муки производится дозаторами непрерывного действия, а жидких компонентов - автоматическими дозировочными станциями. Тесто приготовляется с помощью агрегатов, включающих месильные машины непрерывного действия и аппараты для брожения. Затем тесто разделяется на куски и формуется на поточных линиях, состоящих из тестоделительных, тестокруглительных, тестозакаточных машин, а также конвейерных установок для расстойки (выдержки) теста в кусках. Хлеб выпекается в автоматизированных конвейерных печах. Режим работы тестоприготовительных агрегатов, тесторазделочных линий и печей автоматически контролируется и регулируется в соответствии с качественными показателями поступающего сырья, изменением условий работы предприятия и т.д. Выпеченный хлеб подаётся на автоматизированный склад (включает хлебохранилище и экспедицию), где хранится в контейнерах до отправки в торговую сеть.

В состав хлебозавода входят 2 производства: хлебобулочное и кондитерское. ОАО " Пышка" - хлебозавод. Он находится в Туле и распространяет свою продукцию по территории, данной области.

Основная задача хлебозавода: обеспечение населения хлебобулочной и кондитерской продукцией.

Принципы и цели:

- постоянное обновление и совершенствование ассортимента продукции;

- использование только натурального и высококачественного сырья.

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

Хлебозавод выпускает следующие изделия:

П1 - Хлеб

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

П2 - Печенье

Это небольшое кондитерское изделие, выпеченное из теста. К тесту для печенья добавляют различные зёрна; печенье формуют в виде кружков, квадратов, звёздочек, трубочек; иногда печенье делают с начинкой (шоколадом, изюмом, сгущённым молоком, кремом) или помещают начинку между двумя печеньями.

П3 - Слойка

Это слоёный пирожок, изделие из слоёного теста.

Ресурсы, использованные для производства изделий:

Р1 - Соль

Р2 -Мука

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

Р3 - Вода или какая-либо другая жидкость используется для формирования из муки теста.



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

Организация имеет возможность выпускать три вида изделий П₁, П₂, П₃, При их изготовлении используется три вида ресурсов Р₁, Р₂, Р₃. Размеры допустимых затрат ресурсов ограничены соответственно величинами b₁, b₂, b₃. Расход ресурса i-го вида (i=1,2,…,m) на единицу изделия j-го вида (j=1,2,…,n) составляет a_ijден. ед. Цена единицы продукции j-го вида равна с_j. Требуется найти оптимальный план выпуска изделий, который обеспечивал бы организации максимальный доход.

Построим экономико-математическую модель задачи. С целью ее построения следует ввести переменные и представить исходные данные в табличном виде (Таблица 1).

Таблица 1- Переменные для решения задачи оптимального распределения ресурсов

Норма затрат Ресурсы	Виды изделий	Запас ресурсов	Скрытые цены ресурсов
					yi	yi*
	a11	a12	a13	b1
	a21	a22	a23	b2
	a31	a32	a33	b3
Цена единицы изделия	c1	c2	c3	fmax(х)	gmin(у)
План выпуска	xj
	xj*

Введем переменные: х₁ - объем производства продукции первого вида; х₂ - объем производства продукции второго вида; х₃ - объем производства продукции третьего вида.

Представим исходные данные варианта 44 в виде таблицы 2.



Таблица 2 - Исходные данные для решения задачи оптимального распределения ресурсов

Норма затрат Ресурсы	Виды изделий	Запас ресурсов	Скрытые цены ресурсов
					yi	yi*
	3	3	2	3
	2	4	1	10
	3	1	2	4
Цена единицы изделия	3	4	1	fmax(х)	gmin(у)
План выпуска	xj
	xj*

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

,

где n - количество видов продукции.

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

,



где m - количество ресурсов.

Также должно выполняться условие неотрицательности переменных:

.

Таким образом, экономико-математическая модель прямой задачи линейного программирования (ПЗЛП) варианта 44 имеет вид:

при ограничениях:

Данная ПЗЛП имеет стандартную форму записи, поскольку в задаче на максимум все функциональные (ресурсные) ограничения имеют знаки «меньше или равно».

Для построения двойственной задачи линейного программирования (ДЗЛП) следует ввести двойственные переменные: у₁ - скрытая цена первого ресурса; у₂ - скрытая цена второго ресурса; у₃ - скрытая цена третьего ресурса.

Целевая функция ДЗЛП представляет собой совокупные затраты второго предприятия на приобретение всех ресурсов первого предприятия, при этом второе предприятие стремиться, чтобы его затраты на приобретение ресурсов у первого предприятия были минимальными:



.

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

.

Должно выполняться условие неотрицательности переменных:

.

Также для построения ДЗЛП можно руководствоваться следующими правилами.

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

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

3. Каждая из задач задана в стандартной форме, при этом в задаче максимизации все неравенства вида «меньше или равно», а в задаче минимизации все неравенства вида «больше или равно».

4. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу. Для варианта 0 матрица коэффициентов при переменных в системе ограничений ПЗЛП имеет вид:



Тогда транспонированная матрица, отражающая коэффициенты при переменных в системе ограничений ДЗЛП, имеет вид:

.

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

6. Условие неотрицательности переменных имеются в обеих задачах.

Таким образом, экономико-математическая модель ДЗЛП варианта 0 имеет вид:

при ограничениях

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

Для перехода к канонической форме записи ПЗЛП варианта 0 следует добавить дополнительные переменные х₄, х₅, х₆, в соответствующие неравенства со знаком «+», поскольку они отражают возможный остаток неиспользованных ресурсов:

Для ДЗЛП каноническая форма записи имеет вид:

Для перехода к канонической форме записи ДЗЛП варианта 0 следует добавить дополнительные переменные y₄, y₅, y₆, в соответствующие неравенства со знаком «», поскольку они отражают возможное превышение затрат на приобретение ресурсов над ценой реализации продукции (возможный убыток от производства продукции):

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

Установим соответствие переменных прямой и двойственной задачи для варианта 0:

Таблица

Решение задачи оптимального распределения ресурсов возможно двумя способами:

А. Одновременное решение ПЗЛП и ДЗЛП с помощью симплекс-таблиц.

Б. Двойственный симплекс-метод.

Рассмотрим оба метода.

Решаем ПЗЛП.

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

В первую строку с_jвносятся значения коэффициентов при переменных из целевой функции. В столбец базисных переменных вносим дополнительные переменные х_j.

В столбец с_i вносят значения коэффициентов при переменных из целевой функции, которые вошли в базис.

Рабочее поле таблицы (столбцы под переменными х_jзаполняют коэффициентами при соответствующих переменных из системы равенств канонической формы записи ПЗЛП. Отсутствие той или иной переменной в равенстве означает, что ей соответствует коэффициент, равный нулю.

В столбец b_i вносят свободные члены системы равенств.

Индексная строка (_j) для переменных находится по формуле:

,

где h_ij - соответствующий элемент, стоящий на пересечении i-й строки и j-го столбца рабочего поля симплекс таблицы.

Индексная строка (_j) для свободного члена находится по формуле

,

где l_i - соответствующий элемент, из столбца b_i.

В рассматриваемом варианте в первую строку с_jвносим значения коэффициентов при переменных из целевой функции 3, 4 и 1, остальные значения равны нулю. В столбец базисных переменных вносим дополнительные переменные х₄, х₅, х₆. В рассматриваемом случае базисные переменные не входят в целевую функцию, поэтому им соответствуют нулевые значения в столбце с_i.

Рабочее поле таблицы (столбцы под переменными х₁, х₂, х₃, х₄, х₅, х₆) заполняем коэффициентами при соответствующих переменных из системы равенств канонической формы записи ПЗЛП.

Поскольку, в первом равенстве отсутствуют переменные х₅ и х₆, поэтому в первой рабочей строке симплекс-таблицы этим переменным соответствует коэффициент «0».

Таблица 3 - Шаг симплекс-метода

сi	сj	3	4	1	0	0	0
	Базисные пер. (БП)	х1	х2	х3	х4	х5	х6	bi
0	x4	3	3	2	1	0	0	3
0	x5	2	4	1	0	1	0	10
0	х6	3	1	2	0	0	1	4
j	-3	-4	-1	0	0	0	0

Заполняем индексную строку:

₁ = 03 + 02 + 03 - 3 = -3;

₂ = 01 + 04 + 03 - 4 = -4;

₃ = 02 + 01 + 02 - 1 = -1;

₄ = 0; ₅ = 0; ₆ = 0;

₇= 04 + 010 + 03 = 0.

Первое опорное решение имеет вид: = (0, 0, 0, 3, 10, 4), = 0. (компоненты опорного решения выписывают для базисных переменных из столбца свободных членов b_i; переменные, не входящие в базис, имеют значение 0). В рассматриваемом случае переменные х₁, х₂, х₃. не входят в базис, поэтому их компоненты в опорном решении равны нулю, базисные переменные имеют значения х₄= 3, х₅ = 10, х₆ = 4. Значение целевой функции берут из последней строки столбца. На данном шаге симплекс-метода = 0.

Следует проверить первое опорное решение на оптимальность.

Возможны следующие случаи решения задачи на максимум:

- если все оценки _j 0, то найденное решение оптимальное;

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

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

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

В рассматриваемом случае первое опорное решение не оптимальное, поскольку имеются три отрицательные оценки ₁ = - 3, ₂ = - 4, ₃ = - 1.

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

Пусть одна оценка _k 0 или наибольшая по абсолютной величине _k 0, тогда k-й столбец принимают за ключевой (разрешающий).

Такой переменной является переменная из столбца с наибольшей по абсолютной величине оценкой ₂ = 4, т.е. переменная х₂.



Таблица 4 - Шаг симплекс-метода

сi	сj	3	4	1	0	0	0		min
	Базисные пер. (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
0	x4	3	3	2	1	0	0	3
0	x5	2	4	1	0	1	0	10
0	х6	3	1	2	0	0	1	4
j	-3	-4	-1	0	0	0	0

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

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

В столбце оценочных отношений min{b_i/h_ij} отражены отношения свободных членов к элементам из разрешающего столбца, минимальным является отношение 1, соответствующее строке переменной х₄, следовательно, эта строка - разрешающая, а переменная х₄ выводится из базисных переменных:

Таблица 5 - Шаг симплекс-метода

сi	сj	3	4	1	0	0	0		min
	Базисные пер. (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
0	x4	3	3	2	1	0	0	3	3/3
0	x5	2	4	1	0	1	0	10	10/4
0	х6	3	1	2	0	0	1	4	4/1
j	-3	-4	-1	0	0	0	0	-

На пересечении ключевой строки и ключевого столбца находится ключевой элемент «3».

Переход ко второму шагу симплекс-метода.

В столбец базисных переменных на место выведенной из базисных вносится новая базисная переменная. При этом в столбец с_i вносится соответствующее значение коэффициента при переменной из целевой функции.

Ключевая строка переписывается, при этом все ее элементы делят на ключевой элемент. Заполняют столбцы для базисных переменных: на пересечении строки и столбца, в которых находится одна и та же переменная, ставят «1», в остальных клетках столбца нули.

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

.

Оценки _j можно считать по приведенным ранее формулам или по правилу «прямоугольника».

Заполним симплекс-таблицу второго шага для варианта 44. Вместо переменной х₄ вводим в базис переменную х₂, в целевой функции ей соответствует коэффициент 4, который вносится в соответствующую клетку столбца с_i. В строке, соответствующей переменной х₂ переписываем элементы из ключевой строки предыдущей таблицы, предварительно разделив их на ключевой элемент «3»:



Таблица 6 - Шаг симплекс-метода

сi	сj	3	4	1	0	0	0		min
	Базисные пер. (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
4	x 2	1	1	2/3	1/3	0	0	1
0	x 5		0
0	х6		0
j		0						-

Таблица 7 - Шаг симплекс-метода

сi	сj	3	4	1	0	0	0		min
	Базисные пер. (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
4	x 2	1	1	2/3	1/3	0	0	1
0	x 5		0			1	0
0	х6		0			0	1
j		0			0	0		-

Остальные клетки заполняем по правилу прямоугольника, отмечая, что ключевой элемент «3» находится в третьей строке и втором столбце предыдущей таблицы:

= ;

= ;

= ;

= ;

= ;

= ;

= ;

= .

Таблица 8 - Шаг симплекс-метода

сi	сj	3	4	1	0	0	0		min
	Базисные пер. (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
4	x 2	1	1	2/3	1/3	0	0	1
0	x 5	-2	0	-5/3	-4/3	1	0	6
0	х6	2	0	4/3	-1/3	0	1	3
j		0			0	0		-

Находим оценки переменных:

₁ = 0(2) + 0(-2) + 4(1) - 3 = 1;

₃ = 0(4/3) + 0(-5/3) + 4(2/3) - 1 = 5/3;

₄ = 0(-1/3) + 0(-4/3) + 4(1/3) - 0 =4/3;

₇= 0(3) + 0(6) + 4(1) = 4.

Таблица 9 - Шаг симплекс-метода

сi	сj	3	4	1	0	0	0		min
	Базисные пер. (БП)	х1	х2	х3	х4	х5	х6	bi	bi/hij
4	x 2	1	1	2/3	1/3	0	0	1
0	x 5	-2	0	-5/3	-4/3	1	0	6
0	х6	2	0	4/3	-1/3	0	1	3
j	1	0	5/3	4/3	0	0	4	-

Поскольку все оценки положительные _j, то полученное опорное решение является оптимальным: = (0, 1, 0, 0, 6, 3), а максимальное значение целевой функции равно = 4.

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

Таблица 10 - Шаг симплекс-метода

сi	сj	3	4	1	0	0	0
	Базисные пер. (БП)	х1	х2	х3	х4	х5	х6	bi
4	x 2	1	1	2/3	1/3	0	0	1
0	x 5	-2	0	-5/3	-4/3	1	0	6
0	x 6	2	0	4/3	-1/3	0	1	3
j	1	0	5/3	4/3	0	0	4
yi	y4	y5	y6	y1	y2	y3

Таким образом, = (4/3, 0, 0, 1, 0, 5/3), поскольку y₁x₄, y₂x₅, y₃x₆, y₄x₁, y₅x₂, y₆x₃. Значение целевой функции = 4.

Экономический смысл переменных, участвующих в решении отражен в таблице 11.

Таблица 11 - Экономический смысл переменных

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

Экономический смысл переменных:

x₁^*, x₂^*, x₃^*-основные переменные - оптимальный план производства;

x₄^*,x₅, x₆^*- дополнительные переменные - остатки ресурсов;

y₁,y₂,y₃-основные переменные - скрытые цены;

y₄,y₅,y₆-дополнительные переменны - превышение затрат на ресурсы над ценой реализации (возможный убыток от производства продукции).

Анализ решения ПЗЛП

Подставим оптимальные значения переменных x^*в исходную систему ограничений ПЗЛП:

1) 3х₁ + 3х₂ + 2х₃ 3

30+ 31 + 20 = 3

3=3, следовательно, х₄ = 0, ресурс Р₁ используется полностью;

2) 2х₁ + 4х₂ + х₃ 10

20+ 41 + 10 = 4

4 < 10, следовательно, х₅ = 6, ресурс Р₂ используется не полностью;

3) 3х₁ + х₂ + 2х₃ 4

30 + 11 + 20 = 1

1 < 4, следовательно, х₄ = 3, ресурс Р₃ используется не полностью.

Анализ решения ДЗЛП

Подставим оптимальные значения переменных у^*в исходную систему ограничений ПЗЛП:

1) 3у₁ + 2у₂ + 3у₃ 3

3(4/3) + 20 + 30 = 4

4 3, на 1, следовательно, у₄ = 1, убытки от производства первого вида продукции П₁, которая не вошла в оптимальный план производства, в случае ее производства будут составлять 1 ден. ед. с каждого изделия первого вида;

2) 3у₁ + 4у₂ + у₃ 4

3(4/3) + 40 + 10 = 4

4 = 4, следовательно, у₅ = 0, убытки от производства второго вида продукции П₂, которая вошла в оптимальный план производства отсутствуют;

3) 2у₁ + у₂ + 2у₃ 1

2(4/3) + 10 + 20 = 8/3

8/3 1 на 5/3, следовательно, у₆ = 5/3, убытки от производства третьего вида продукции П₃, которая не вошла в оптимальный план производства, в случае ее производства будут составлять 5/3 ден. ед. с каждого изделия третьего вида.

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

В рассматриваемом случае дефицитным является ресурс Р₁.

Для исследования границ изменения первого вида ресурса Р₁ из последней симплекс-таблицы составляют систему неравенств для базисных переменных ПЗЛП, используя элементы из столбца свободных членов b_i и столбца, соответствующего переменной у₁. Коэффициенты из столбца «у₁» умножают на искомое изменение b₁запаса ресурса Р₁:

.

Учитывая, что b₁ = 3, допустимый интервал изменения границ первого вида ресурса составит или .

Проверим границы с помощью вычислительного эксперимента:

Зададим b₁ = 7,48:



Рисунок 1 - Прямая задача линейного программирования

Структура ПЗЛП не изменилась

Рисунок 2 - Двойственная задача линейного программирования



Структура ДЗЛП не изменилась.

Зададим b₁ = 0,02:

Рисунок 3 - Прямая задача линейного программирования

Структура решения ПЗЛП не изменилась

Рисунок 4 - Двойственная задача линейного программирования



Структура ДЗЛП не изменилась.

Зададим b₁ = 7,51:

Рисунок 5 - Прямая задача линейного программирования

Получили новую структуру оптимального плана прямой задачи: (х₁=0,01; х₂=2,5; x₃=0)

Рисунок 6 - Двойственная задача линейного программирования



Получили новую структуру оптимального плана ДЗЛП.

Можно сделать вывод о правильности установленных границ изменения ресурса Р₁: 0? b₂ ? 15/2.

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

В рассматриваемом случае не дефицитными являются ресурсы Р₂ и Р₃. Оптимальный план производства не изменится при .

Проверим границы с помощью вычислительного эксперимента:

Зададим b₂ = 3,98:

Рисунок 7 - Двойственная задача линейного программирования

Получили новый оптимальный план решения ДЗЛП.

Зададим b₂ = 4,02:



Рисунок 8 - Прямая задача линейного программирования

Оптимальный план решения ПЗЛП не изменился

Рисунок 9 - Двойственная задача линейного программирования



Оптимальный план решения ДЗЛП не изменился.

Можно сделать вывод о правильности установления границы изменения ресурса Р₂: b₂ ? 4.

Оптимальный план производства для не дефицитного ресурса Р₃ не изменится при .

Проверим границы с помощью вычислительного эксперимента:

Зададим b₃ = 0,98:

Рисунок 10 - Двойственная задача линейного программирования

Получили новый оптимальный план решения ДЗЛП.

Зададим b₂ = 1,02:



Рисунок 11 - Прямая задача линейного программирования

Оптимальный план решения ПЗЛП не изменился.

Рисунок 12 - Двойственная задача линейного программирования



Оптимальный план решения ДЗЛП не изменился.

Можно сделать вывод о правильности установления границы изменения ресурса Р₃: b₃ ? 1.

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

В план производства вошел второй вид продукции П₂.

Для второго вида продукции П₂, которая попала в план производства, из последней симплекс-таблицы составляют систему неравенств для базисных переменных ДЗЛП (они соответствуют свободным переменным ПЗЛП), используя элементы из строки _j и строки, соответствующей переменной х₂. Коэффициенты из строки «х₂» умножают на искомое изменение с₁цены продукции П₂

.

Учитывая цену второго вида продукции с₂ = 4, интервал устойчивости изменения цен составит или .

Проверим границы с помощью вычислительного эксперимента:

Зададим c₂ = 2,98:



Рисунок 13 - Прямая задача линейного программирования

Получили новый оптимальный план решения ПЗЛП.

Зададим c₂ = 3,02:

Рисунок 14 - Прямая задача линейного программирования



Структура оптимального плана решения ПЗЛП не изменилась.

Рисунок 15 - Двойственная задача линейного программирования

Структура решения ДЗЛП не изменилась.

Можно сделать вывод о правильности определения границы изменения цены с₂: с₂ 3.

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

Определим величины ?b_s ресурса Р_s, введением которого в производство можно компенсировать убыток и сохранить максимальный доход на прежнем уровне (ресурсы предполагаются взаимно заменяемыми), получаемый при исключении из производства ?b_r единиц ресурса Р_r.

В рассматриваемом случае: r = 1; ?b_r = 0,2; s = 2.

Для взаимозаменяемых ресурсов (коэффициент взаимозаменяемости >0, но отличен от бесконечности) количество ресурса ?b_iвида i, необходимое для замены выбывающего количества ?b_kресурса k, определяется по формуле:



.

Таким образом, . Следовательно, замена первого ресурса невозможна.

Оценим целесообразность приобретения ?b_k единиц ресурса Р_k по цене с_k за единицу. Для оценки целесообразности приобретения дополнительного количества ресурса ?b_iвида i по цене с_k необходимо сравнить предлагаемую цену с рассчитанной ранее теневой ценой этого ресурса . Приобретение дополнительного количества ресурса целесообразно, если выполняется условие непревышения новой цены над теневой ценой

с_k.

В противном случае приобретение дополнительного количества ресурса нецелесообразно.

В рассматриваемом случае: ?b_k = 0,2; k = 3, c_k = 15.

Поскольку < 15, то приобретение дополнительного количества ресурса не целесообразно.

Оценим целесообразность выпуска нового изделия П₄, на единицу которого ресурсы Р₁, Р₂, Р₃ расходуются в количествах a₁₄, a₂₄, a₃₄ единиц, а цена единицы изделия составляет с₄ денежных единиц. Включение дополнительного вида продукции n+1 в план производства целесообразно, если соотношение дополнительных затрат и цены реализации дополнительного вида продукции удовлетворяет следующему условию



.

Расчет затрат осуществим по формуле

ден. ед.

Учитывая, что затраты на ресурсы для производства продукции третьего вида меньше цены реализации с₄ = 35 ден. ед., то включение ее в план производства целесообразно.

Решим прямую и двойственную задачу линейного программирования в среде MicrosoftExсel. Решение задач линейного программирования с помощью программы MicrosoftExcel осуществляется через меню Сервис и вкладку Поиск решения. Если данная вкладка не установлена, то ее установка осуществляется следующими действиями:

1. Войти в меню Сервис.

2. Выбрать команду Надстройки.

3. В появившемся диалоговом окне Надстройки установить флажок напротив строки Поиск решения и нажать кнопку ОК.

После произведенных действий в меню Сервис появится команда Поиск решения.

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

Выбираем ячейку для введения целевой функции (например, ячейку А1). При записи целевой функции в ячейку А1 вместо значений переменной х_i подставляют названия пустых ячеек, в которых хотим получить искомые значения х₁, х₂, х₃, например, С1, С2, С3. Тогда запись целевой функции в ячейке А1 будет иметь вид = 3*С1+4*С2+С3. После введения целевой функции в ячейку А1 нажимаем клавишу «Enter», в ячейке А1 отобразится 0.

Условия ограничений вписываем в ячейки столбца В. В выбранные ячейки записываются только левые части неравенств в следующем виде:

Ячейка В1: =3*С1+3*С2+2*С3 «Enter»

Ячейка В2: =2*С1+4*С2+С3 «Enter»

Ячейка В3: =3*С1+С2+2*С3 «Enter»

Ячейка В4: =С1 «Enter»

Ячейка В5: =С2 «Enter»

Ячейка В6: =С3 «Enter»

Через меню Сервис/Поиск решения открыть окно поиска решения:

Рисунок 16 - Решение задачи в среде MicrosoftExсel

В поле ввода Установить целевую ячейку вводим ссылку на ячейку А1.

В поле ввода Изменяя ячейки укажем ссылки на ячейки С1:С3.

Данная операция осуществляется следующими действиями:

1.Щелкнуть левой кнопкой мыши в поле ввода Изменяя ячейки.

2. Выделить при помощи левой кнопки мыши ячейки, начиная с С1 и до ячейки С3(поле ввода изменения ячейки должно автоматически заполниться).

В поле ввода Ограничения введем ограничения, соответствующие ячейкам В1, В2, В3. Ввод значений осуществляется в следующем порядке:

1.Нажать кнопку Добавить. Появится диалоговое окно Добавление ограничения.

2. Для каждого логического выражения, находящихся в ячейках В1, В2, В3 вводим свое условие и свое ограничение, последовательно нажимая кнопку Добавить. По окончании нажать кнопку ОК.

Рисунок 17 - Решение задачи в среде MicrosoftExсel

3. Должен появиться следующий результат:



Рисунок 18 - Результат решения задачи в среде MicrosoftExсel

Для поиска максимального значения устанавливаем флажок.

Для осуществления вычислений нажмем кнопку Выполнить. Откроется окно диалога Результаты поиска решения. В окне Тип отчета выберем строку Результаты и нажмем кнопку ОК. Получим следующие результаты:

В ячейке А1отражено максимально возможное значение функции при заданных условиях 4.

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

3х₁ + 3х₂ +2х₃ = 3

2х₁ + 4х₂ + х₃ = 4

3х₁ + х₂ + 2х₃ = 1

В столбце С отражены значения переменных, при которых значение функции принимает максимальную величину:

х₁ = 0; х₂ = 1; х₃ = 0.

На листе «Отчет по результатам» появится следующая информация, отражающая результаты расчета:



Рисунок 19 - Результат решения задачи в среде MicrosoftExсel

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

Рисунок 20 - Результат решения задачи в среде MicrosoftExсel



симплекс-метод

1. Выражение базисных переменных ПЗЛП и ДЗЛП через свободные.

Выразим базисные переменные ПЗЛП и ДЗЛП через свободные:

2.Определение исходного решения прямой и двойственной задач и проверка его на оптимальность.

Для этого заполняют симплекс-таблицу двойственного симплекс-метода. Таблица имеет два входа: по переменным прямой задачи x_jи по переменным двойственной задачи y_i. Базисные переменные ПЗЛП записывают в столбце x_баз, а свободные переменные в строке x_св со знаком «». Базисные переменные ДЗЛП записывают в строке у_баз, а свободные переменные в столбце у_св.

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

Решение является оптимальным, если в строке и столбце b_i нет отрицательных элементов. В противном случае следует провести изменения в базисных переменных.

Симплексная таблица двойственного симплекс-метода для варианта 40 имеет следующий вид:



Таблица 12 - Шаг двойственного симплекс-метода

Решение ПЗЛП выписывается по строкам, значения базисных переменных берутся из столбца b_i, если переменная с соответствующим индексом не входит в базис, то ее значение равно нулю: = (0, 0, 0, 3, 10, 4), = 0.

Решение ДЗЛП выписывается по столбцам, значения базисных переменных берутся из строки c_j, если переменная с соответствующим индексом не входит в базис, то ее значение равно нулю: = (0, 0, 0, -3, -4, -1), = 0.

Данное решение не является оптимальным, поскольку решение не допустимое (не выполнено условие неотрицательности переменных), ему соответствуют отрицательные элементы в строке . Поэтому следует провести замену переменных в базисе.

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

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

В рассматриваемом примере в строке три отрицательных элемента.



Таблица 13 - Шаг двойственного симплекс-метода

Можно выбрать любой из них, поэтому выбираем «1», а над ним выбираем элемент из второй строки «2». Следовательно, первая строка - разрешающая (выделена жирным шрифтом).

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

Если среди полученных отношений нет отрицательных, то ПЗЛП не имеет решения, ДЗЛП не имеет смысла или решения.

На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

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



Таблица 14 - Шаг двойственного симплекс-метода

Разрешающим элементом является элемент «2», который стоит на пересечении первой строки и третьего столбца.

Под разрешающим элементом всегда ставят «1». Остальные элементы разрешающей строки переписываются без изменений, а остальные элементы разрешающего столбца переписываются с противоположным знаком.

Заполнение нижних частей клеток для разрешающей строки и разрешающего столбца варианта 44:

Таблица 15 - Шаг двойственного симплекс-метода

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

Заполнение нижних частей для остальных клеток варианта 44:

на пересечении второй строки и первого столбца:

Рис. 22 31 = 1;

клетка на пересечении третьей строки и первого столбца:

Рис. 23 23 = 0;

клетка на пересечении четвертой строки и первого столбца:

Рис. 32 3(1) = 3;



клетка на пересечении второй строки и второго столбца:

Рис. 42 31 = 5;

клетка на пересечении третьей строки и второго столбца:

Рис. 21 32 = -4;

клетка на пересечении четвертой строки и второго столбца:

42 (1)3 = -5;

клетка на пересечении второй строки и четвертого столбца:

Рис.10 13 = 17;



клетка на пересечении третьей строки и четвертого столбца:

Рис.4 23 = 2;

клетка на пересечении четвертой строки и четвертого столбца:

Рис. 02 (1)3= 3.

Таким образом, получаем следующую таблицу:

Таблица 16 - Шаг двойственного симплекс-метода

Изменяют базисные переменные: меняют местами переменные из разрешающей строки и разрешающего столбца. Элементы из нижних клеток предыдущей симплекс-таблицы делят на верхний разрешающий элемент и записывают на соответствующие места в верхние клетки новой симплекс-таблицы.

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

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

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

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

Переходим к следующей симплекс-таблице. При этом в первую строку включается пара переменных х₃, у₆, соответствующих разрешающему столбцу, а в третий столбец вводится пара переменных х₄, у₁, соответствующая разрешающей строке. Верхние части клеток заполняются элементами, полученными в результате деления соответствующих (стоящих на аналогичном месте) элементов из предыдущей таблицы в нижних частях клеток на разрешающий элемент «2»:

Таблица 17 - Шаг двойственного симплекс-метода

Решение ПЗЛП на втором шаге двойственного симплекс-метода также выписывается по строкам: = (0, 0, 3/2, 0, 17/2, 1), = 3/2, решение ДЗЛП выписывается по столбцам: = (1/2, 0, 0, 3/2, -5/2, 0), = 3/2. Данное решение также не оптимальное, поскольку в строке еще остались отрицательные элементы. Необходимо продолжить поиск оптимального решения.

В строке выбираем отрицательный элемент «3/2». Над ним выбираем положительный, предпочтительнее «3/2», следовательно, первая строка - разрешающая (выделена жирным шрифтом):



Таблица 18 - Шаг двойственного симплекс-метода

Находим максимальное отношение среди отношений элементов в строке целевой функции к соответствующим элементам разрешающей строки

. Разрешающий столбец - первый, поскольку максимальное отношение соответствует ему.

Разрешающий элемент «3/2» находится на пересечении разрешающей строки и разрешающего столбца.

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

Таблица 19 - Шаг двойственного симплекс-метода



Переходим к следующей симплекс-таблице. При этом в первую строку включается пара переменных х₁, у₄, соответствующих разрешающему столбцу, а в первый столбец вводится пара переменных х₃, у₆, соответствующая разрешающей строке. Верхние части клеток заполняются элементами, полученными в результате деления соответствующих (стоящих на аналогичном месте) элементов из предыдущей таблицы в нижних частях клеток на разрешающий элемент «3/2»:

Таблица 20 - Шаг двойственного симплекс-метода

Решение ПЗЛП на третьем шаге двойственного симплекс-метода также выписывается по строкам: = (1, 0, 0, 0, 8, 1), = 3, решение ДЗЛП выписывается по столбцам: = (1, 0, 0, 0, -1, 1), = 3. Данное решение также не оптимальное, поскольку в строке еще остался отрицательный элемент. Необходимо продолжить поиск оптимального решения.

В строке выбираем отрицательный элемент «1». Над ним выбираем положительный, предпочтительнее «1», следовательно, первая строка - разрешающая (выделена жирным шрифтом):



Таблица 21 - Шаг двойственного симплекс-метода

Находим максимальное отношение среди отношений элементов в строке целевой функции к соответствующим элементам разрешающей строки. Разрешающий столбец - второй, поскольку максимальное отношение соответствует ему.

Разрешающий элемент «1» находится на пересечении разрешающей строки и разрешающего столбца.

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

Таблица 22 - Шаг двойственного симплекс-метода

Перейдем к следующей симплекс-таблице. При этом в первую строку включается пара переменных х₂, у₅, соответствующих разрешающему столбцу, а во второй столбец вводится пара переменных х₁, у₄, соответствующая разрешающей строке. Клетки следующей таблицы заполняются элементами, полученными в результате деления соответствующих элементов из предыдущей таблицы в нижних частях клеток на разрешающий элемент «1». Поскольку в нижних частях клеток таблицы все элементы положительные и разрешающий элемент также положительный, то в следующей таблице будет получено оптимальное решение и нет необходимости делить на две части клетки в последней таблице.

Таблица 23 - Шаг двойственного симплекс-метода

Оптимальное решение ПЗЛП: = (0, 1, 0, 0, 6, 3), = 4, оптимальное решение ДЗЛП: = (4/3, 0, 0, 1, 0,5/3), = 4.

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

3. Метод потенциалов решения транспортной задачи

Начальное решение транспортной задачи

Имеется 4 оптовых склада и 4 магазина.

A₁, A₂, A₃, A₄ - склады.

a₁ = 19, a₂ = 19, a₃ = 19, a₄ = 19 - соответственно, запасы на складах.

B₁, B₂, B₃, B₄ - магазины.

b₁ = 15, b₂ = 15, b₃ = 23, b₄ = 23 - соответственно, потребности магазинов.

Найдем исходное опорное решение по методу минимальной стоимости. Для этого заполним распределительную таблицу:

Таблица 24 - Транспортная задача

Таблица 25 - Транспортная задача

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

Рис.



f_o(x^o) = 12·19 + 16·15 + 15·4 + 16·19 + 10·15 + 10·4 = 1022

Количество ненулевых элементов 6 < 7 , решение вырожденное. Введем значимый ноль (O).

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

Таблица 26 - Транспортная задача

Вычисляем оценки свободных клеток:

₁₁ = c₁₁ - u₁ -v₁ = 21- 0 - 13= 8 > 0,

₁₂ = c₁₂- u₁ - v₂ = 17 - 0 -11 = 6 >0,

₁₄ = c₁₄ - u₁ - v₄ = 24 - 0 - 11= 13 >0,

₂₂ = c₂₂ - u₂ - v₂ = 19 - 3 - 11 = 5 > 0,

₂₄ = c₂₄ - u₂ - v₄ = 19 - 3 -11 = 5 > 0,

₃₁ = c₃₁ - u₃ - v₁ = 17 - 5 - 13= - 1< 0,

₃₂ = c₃₂ - u₃ - v₂ = 15 - 5 - 11= -1< 0,

₃₃ = c₃₃ - u₃ - v₃ = 24 - 5- 12 = 7 >0,

₄₁ = c₄₁ - u₄ - v₁ = 13+1-13 = 1 >0.

В распределительной таблице оценки клеток проставлены в нижнем левом углу в скобках:

Таблица 27 - Транспортная задача

Переход к следующему опорному решению.

Выбираем клетку, от которой начнем построение цикла перераспределения поставок, по правилу . У вершин цикла с соответствующими значениями поставок по правилу чередования знаков ставим знаки (+) и (-).У вершин со знаком (-) выбираем минимальный груз = min[15,19] = 15.

Рис.

Проверка решения Х₁ на оптимальность выполняется аналогично предыдущему шагу.



Таблица 28 - Транспортная задача

У вершин со знаком (-) выбираем минимальный груз = min[15,4,0] = 0.

Рис.

Проверка решения Х₂ на оптимальность.

Результаты расчета представлены в распределительной таблице:

Таблица 29 - Транспортная задача



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

F^*(x₂) = 12·19 + 16·15 + 15·4 + 15·15 + 16·4 + 10·19 = 1007

Таким образом, решение транспортной задачи:

Рис.

Решение транспортной задачи в среде Microsoft Exсel

Ввод исходных данных (в области C3:F6 - тарифы на перевозку продукции; в столбце G3:G6 - запасы; в ячейках С7, D7, E7, F7 - потребности).

В области решения в ячейке G10 введите формулу стоимости перевозок:

=СУММПРОИЗВ(C12:F15;C3:F6). Для этого необходимо нажать на значок f(x) на панели инструментов, выбрать математическую функцию СУММПРОИЗВ и ввести два массива C12:F15 и C3:F6. Далее в области C12:F15 проставьте любое первоначальное решение (например, единицы)/

В ячейке С16 записывается формула: =СУММ(C12:C14), т.е. сумма значений по столбцу (можно выделить значения столбца и нажать на знак автосуммы У на панели инструментов). Аналогично в D16, E16, F16. Автоматически суммируются значения по столбцам.

В ячейке G12 записывается формула: =СУММ(C12:F12), т.е. сумма значений по строке (можно выделить значения строки и нажать на знак автосуммы У на панели инструментов). Аналогично в G13, G14, G15. Автоматически суммируются значения по строкам:



Рисунок 21 - Поиск оптимального решения

Далее выполняют команду Поиск решения (вкладка Сервис или Данные).