Менеджмент как процесс принятия управленческих решений. Виды управленческих решений.

Менеджмент как процесс принятия управленческих решений. Виды управленческих решений.

Технология менеджмента рассматривает управленческое решение как процесс, состоящий из трех стадий: подготовка решения: принятие решения; реализация решения.

 

 

Факторы, влияющие на процесс принятия решений: личностные, ситуационные. Классификация неопределенных факторов по источнику неопределенности и по природе неопределенности.

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

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

По источнику неопределенности различают факторы неопределенности среды и факторы личностной неопределенности:

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

По природе неопределенности. По этому основанию выделяют вероятностную неопределенность и неопределенность уверенности.

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

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

 

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

Проблема →Цель→Задача→Решение

Под проблемой понимается: 1)несоответствие фактического состояния объект управления желаемому заданному запланированному. 2)вопрос который не имеет готового решения на момент его постановки.

Решение проблемы означает: 1)найден вариант действий, но еще не осуществлен. 2)устранены некоторые препятствия или трудности. 3)итог деятельности.

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

Описание проблемной ситуации содержит в себе 2части:: 1)характеристика самой проблемы:2)описание причин или факторов приведенных к появлению проблемы.

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

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

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

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

Этап 1. Предварительный анализ проблемы. На этом этапе определяются:

* главные цели;

* уровни рассмотрения, элементы и структура системы (процесса), типы связей;

* подсистемы, используемые ими основные ресурсы и критерии качества функционирования подсистем;

* основные противоречия, узкие места и ограничения.

Этап 2. Постановка задачи. Постановка конкретной ЗПР включает:

* формулирование задачи;

* определение типа задачи;

* определение множества альтернативных вариантов и основных критериев для выбора из них наилучших;

* выбор метода решения ЗПР.

Этап 3. Получение исходных данных

Этап 4. Решение ЗПР с привлечением математических методов и вычислительной техники, экспертов и лица, принимающего решение.

Этап 5. Анализ и интерпретация полученных результатов. Полученные результаты могут оказаться неудовлетворительными и потребовать изменений в постановке ЗПР.

Таблица 2.3

У поставщика А₂ осталось 150 ед. груза. Удовлетворяем потребителя B₂ за счет оставшегося у поставщика А₂ груза. Для этого сравниваем этот остаток с потребностями потребителя B₂: 150<200, записываем 150 ед. в клетку А₂B₂ и, так как запасы А₂ полностью израсходованы, прочеркиваем остальные клетки второй строки. Потребности B₂ остались неудовлетворенными на 50 ед. Удовлетворяем их за счет поставщика А₃ и переходим к удовлетворению B₃ за счет остатка, имеющегося у поставщика А₃, и т. д. Процесс продолжаем до тех пор, пока не удовлетворим всех потребителей за счет запасов поставщиков. На этом построение первоначального опорного плана заканчивается.
Таким образом, в табл. в правых верхних углах клеток стоят числа, определяющие стоимость перевозки единицы грузов, а в левых нижних углах — числа, определяющие план перевозок, так как их сумма по строкам равна запасам соответствующего поставщика, а сумма по столбцам — потребности соответствующего потребителя.
Проверим, является ли план, построенный в табл. 2.2, опорным. Видим, что, начиная движение от занятой клетки A1B1, вернуться не только в нее, но и в любую другую занятую клетку, двигаясь только по занятым ячейкам, невозможно. Следовательно, план является опорным. В то же время план невырожденный, так как содержит точно m + n -1 = 4 + 5 - 1 = 8 занятых клеток.
При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы груза не учитывалась, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Поэтому рассмотренный метод используется при вычислениях-с помощью ЭВМ.

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

Z = 100 *10 + 100*2 + 150 *7+ 50 *5 + 100*3 + 50*2 + 50*16+ 250*13 = 6950 (eд. стоимости)
Если при составлении опорного плана учитывать стоимость перевозки единицы груза, то, очевидно, план будет значительно ближе к оптимальному.

2) Метод наименьшей стоимости.

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

Составим с помощью этого метода опорный план уже рассмотренной задачи. Запишем ее условие в таблицу (табл. 2.5). Выбираем в таблице наименьшую стоимость (это стоимость, помещенная в клетке A₁, B₄) так как A₁ = b₄, 100 ед. груза помещаем в этой клетке и исключаем из рассмотрения первую строку и четвертый столбец. В оставшейся таблице стоимостей наименьшей является стоимость, расположенная в клетке A₂ , B₁ и в клетке A₃ , B₅. Заполняем любую из них, например A₂ , B₁. Имеем 200 < 250, следовательно, записываем в нее 200 и исключаем из рассмотрения столбец B₁. В клетку A₃ , B₅ записываем 200 ед. и исключаем из рассмотрения строку A₃ . В оставшейся таблице стоимостей снова выбираем наименьшую стоимость и продолжаем процесс до тех пор, пока все запасы не будут распределены, а потребности удовлетворены. В результате получен план
X = (X₁₄ = 100; X₂₁ = 200; X₂₂ = 50; X₃₅= 200, X₄₂ = 150; X₄₃ = 100; X₄₅ = 50),
остальные значения переменных равны нулю.

Таблица 2.5

План не содержит циклов и состоит из семи положительных перевозок, следовательно, является вырожденным опорным планом. Определим его стоимость:
Z = 100*1+200*2+50*7+200*2+150*8+100*12+50*13= 4300 (ед)
Стоимость плана перевозок значительно меньше, следовательно, он ближе к оптимальному.

3).Метод аппроксимации Фогеля

Данный метод состоит в следующем:

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

находят max Δc_ij и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.

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

На первом шаге заполняем клетку A₃ B₁ (max Δc = 5 и min c_ij = 6), исключаем 1-ый столбец, отметив в дополнительной строке буквой «В» факт выполнения заказа пункта B₁ . Находим новые разности минимальных тарифов по строкам (в столбцах они не изменились) и max Δc = 2 в 1-ой строке и в 4-ом столбце. Заполняем клетку A₁B₄ и исключаем 4-й столбец и т.д. В конце остается последовательно заполнить клетки 3-го столбца остатками запасов в A₁ , A₃ , A₂ . Составленный опорный план дает значение Z₃ = 909 < Z₂.

Распределительный метод

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

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

Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l,m), приращение целевой функции Δ_lm равно разности двух сумм:

где - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком “+”; - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком “-”.
В клетках, отмеченных знаком “+”, величины груза прибавляются, что приводит к увеличению значения целевой функции F(X), а в клетках, отмеченных знаком “-”, величины груза уменьшаются, что приводит к уменьшению значения целевой функции.

Если разность сумм для свободной клетки (l, m) меньше нуля, т.е. Δ _lm< 0, то перераспределение величины θ по соответствующему циклу приведет к уменьшению значения F(X) на величину θ • Δ_lm, т.е. опорное решение можно улучшить. Если же величины Δ_lm, называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие

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

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

ПРИМЕР. Решить распределительным методом транспортную задачу, исходные данные которой приведены в таблице:

		b1	b2	b3
		20	40	40
a1	20		1		3		2
a2	30		4		5		7
a3	50		6		8		15

Решение. Строим начальное опорное решение методом минимальной стоимости:

Затем вычисляем значение целевой функции на нем: F(X₁) = 20∙1 + 30∙5 + 10∙8 + 40∙15 = 850.
Таблица

Находим цикл для свободной клетки (1, 2) таблицы, он включает клетки (1, 2), (1, 3), (3, 3), (3, 2). Вычисляем оценку Δ₁₂ = (3 + 15) - (2 + 8) = 8. Так как Δ₁₂ = 8 > 0, переходим к следующей свободной клетке (2, 1). Для нее цикл таков: (2, 1), (1, 1), (1,3), (3, 3), (3, 2), (2, 2) (см. табл.). Оценка Δ₂₁ = (4 + 2 + 8) - (1 + 15 + 5) =14 - 21 = -7. Так как Δ₂₁| = -7 < 0, определяем величину груза, перераспределяемого по циклу, Приращение целевой функции ΔF=-7∙20=-140. Получим новое опорное решение X₂. Значение целевой функции на нем F(X₂)=20∙2+20∙4+10∙5+30∙8+20∙15=710.

Вычисляем Δ₁₁ = (1 + 15 + 5) - (2 + 8 + 4) =7>0, Δ₁₂= (3 + 15) - (2 + 8) =8>0, Δ ₂₃ = (7 + 8) - (5 + 15)=-5<0, Δ₃₁= (6 + 5) - (8 + 4) =-1<0. Оценки можно вычислять до первой отрицательной. Так как Δ₂₃ =-5<0, осуществляем сдвиг по циклу (2,3), (3,3), (3,2), (2,2) на величину . Приращение целевой функции ΔF=-5∙10=-50. Получаем третье опорное решение X₃. Значение целевой функции на нем F(X₃)=20∙2+20∙4+10∙7+40∙8+10∙15=660.

Вычисляем оценки для свободных клеток Δ₁₁ = (1 + 7) - (2 + 4) =2>0, Δ₁₂ = (3 + 15) - (2 + 8) =8>0, Δ₂₂ =(5 + 15) - (7 + 8) =5>0, Δ₃₁ = (6 + 7) - (4 + 15) =-6<0. Так как Δ₃₁=-6<0, осуществляем сдвиг по циклу (3,1), (2,1), (2,3), (3,3), на величину Приращение целевой функции ΔFm=-6∙10=-60. Получаем четвертое опорное решение X₄ Значение целевой функции на нем F(X₄)=20 ∙2+10∙4+20∙7+10∙6+40∙8=600.

Вычисляем оценки для свободных клеток Δ₁₁ = (1 + 7) - (2 + 4) =2>0, Δ₁₂ = (3 + 7+ 6) - (2 +4+ 8) =2>0, Δ₂₂ =(5 + 6) - (4 + 8) =-1<0. Так как Δ₂₂ =-1<0, осуществляем сдвиг по циклу (2,2), (3,2), (3,1), (2,1), на величину Приращение целевой функции ΔF=-1∙10=-10. Получаем пятое опорное решение X₅.

Значение целевой функции на нем F(X₅)=20 ∙2+10∙5+20∙7+20∙6+30∙8=590. Вычисляем оценки для свободных клеток Δ₁₁ = (1 + 7) - (2 + 4) =2>0, Δ₁₂ = (3 + 7) - (2 +5) =3>0, Δ₃₃ =(15 + 5) - (7 + 8) =5>0. Все оценки для свободных клеток положительные, следовательно, последнее опорное решение оптимально.

Таблица 3.6.1

В левой колонке записаны номера кандидатов, в верхней строке – номера работ. В -й строке -мстолбце стоят затраты на выполнение -м кандидатом -й работы.

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

Алгоритм метода содержит следующие шаги.

Шаг 1. Получение нулей в каждой сроке. Для этого в каждой строке определяют наименьший элемент, и его значение отнимают от всех элементов этой строки. Переход к шагу 2.

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

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

Шаг 4. Поиск минимального набора строк и столбцов, содержащих все нули.

Для этого необходимо отметить:

1) все строки, в которых не имеется ни одного отмеченного нуля;

2) все столбцы, содержащие перечеркнутый нуль хотя бы в одной из отмеченных строк;

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

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

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

Шаг 5. Перестановка некоторых нулей.

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

Задача о рюкзаке.

Задача о загрузке (задача о рюкзаке) и различные её модификации широко применяются на практике в прикладной математике, криптографии, экономике, логистике, для нахождения решения оптимальной загрузки различных транспортных средств: самолетов, кораблей, железнодорожных вагонов и т.д. Задача о ранце – одна из задач комбинаторной оптимизации. Классическая задача о ранце известна очень давно. Вот её постановка: Имеется набор из N предметов, каждый предмет имеет массу Wi и полезность Vi, i=(1,2..N), требуется собрать набор с максимальной полезностью таким образом, чтобы он имел вес не больше W, где W – вместимость ранца.

Пример: Задание. В рюкзак объема V = 7 кладут N = 5 предметов.Объемы, веса и количество предметов в каждой группе приведены в таблице.

Объем
Вес
Кол-во

 

Максимизировать общий вес рюкзака.

Решение.

I этап. Условная оптимизация.
f₁(L) = max(2x₁); 0 < x₁ < 1; x₁ = 0,1.
f₁(0) = max[0*2] = 0
f₁(1) = max[0*2, 1*2] = 2
f₁(2) = max[0*2, 1*2] = 2
f₁(3) = max[0*2, 1*2] = 2
f₁(4) = max[0*2, 1*2] = 2
f₁(5) = max[0*2, 1*2] = 2
f₁(6) = max[0*2, 1*2] = 2
f₁(7) = max[0*2, 1*2] = 2

Таблица 1 – Расчет значения функции f₁(L)

L
f1(L)
x1

f₂(L) = max[3x₂ + f₁(L - 2x₂)]; 0 < x₂ < 3; x₂ = 0,1,2,3.
f₂(0) = max[0*3+0] = 0
f₂(1) = max[0*3+2] = 2
f₂(2) = max[0*3+2, 1*3+0] = 3
f₂(3) = max[0*3+2, 1*3+2] = 5
f₂(4) = max[0*3+2, 1*3+2, 2*3+0] = 6
f₂(5) = max[0*3+2, 1*3+2, 2*3+2] = 8
f₂(6) = max[0*3+2, 1*3+2, 2*3+2, 3*3+0] = 9
f₂(7) = max[0*3+2, 1*3+2, 2*3+2, 3*3+2] = 11
Таблица 2 – Расчет значения функции f₂(L)

 

L
f2(L)
x2

 

f₃(L) = max[2x₃ + f₂(L - 3x₃)]; 0 < x₃ < 3; x₃ = 0,1,2,3.
f₃(0) = max[0*2+0] = 0
f₃(1) = max[0*2+2] = 2
f₃(2) = max[0*2+3] = 3
f₃(3) = max[0*2+5, 1*2+0] = 5
f₃(4) = max[0*2+6, 1*2+2] = 6
f₃(5) = max[0*2+8, 1*2+3] = 8
f₃(6) = max[0*2+9, 1*2+5, 2*2+0] = 9
f₃(7) = max[0*2+11, 1*2+6, 2*2+2] = 11
Таблица 3 – Расчет значения функции f₃(L)

L
f3(L)
x3

f₄(L) = max[4x₄ + f₃(L - 1x₄)]; 0 < x₄ < 1; x₄ = 0,1.
f₄(0) = max[0*4+0] = 0
f₄(1) = max[0*4+2, 1*4+0] = 4
f₄(2) = max[0*4+3, 1*4+2] = 6
f₄(3) = max[0*4+5, 1*4+3] = 7
f₄(4) = max[0*4+6, 1*4+5] = 9
f₄(5) = max[0*4+8, 1*4+6] = 10
f₄(6) = max[0*4+9, 1*4+8] = 12
f₄(7) = max[0*4+11, 1*4+9] = 13
Таблица 4 – Расчет значения функции f₄(L)

L
f4(L)
x4

f₅(L) = max[1x₅ + f₄(L - 1x₅)]; 0 < x₅ < 2; x₅ = 0,1,2.
f₅(0) = max[0*1+0] = 0
f₅(1) = max[0*1+4, 1*1+0] = 4
f₅(2) = max[0*1+6, 1*1+4, 2*1+0] = 6
f₅(3) = max[0*1+7, 1*1+6, 2*1+4] = 7
f₅(4) = max[0*1+9, 1*1+7, 2*1+6] = 9
f₅(5) = max[0*1+10, 1*1+9, 2*1+7] = 10
f₅(6) = max[0*1+12, 1*1+10, 2*1+9] = 12
f₅(7) = max[0*1+13, 1*1+12, 2*1+10] = 13
Таблица 5 – Расчет значения функции f₅(L)

L
f5(L)
x5

II этап. Безусловная оптимизация.
Таким образом, максимальный вес рюкзака f₅(7) равна 13 кг.
При этом x₅ = 0, так как f₅(7) = 13 достигается при х₅=0 (см. таблицу 5).
Предметы остальных типов распределяются следующим образом:
L = 7 - 1 * 0 = 7
f₄(7) = 13 достигается при х₄ = 1 (см. таблицу 4).
L = 7 - 1 * 1 = 6
f₃(6) = 9 достигается при х₃ = 0 (см. таблицу 3).
L = 6 - 3 * 0 = 6
f₂(6) = 9 достигается при х₂ = 3 (см. таблицу 2).
L = 6 - 2 * 3 = 0
f₁(0) = 0 достигается при х₁ = 0 (см. таблицу 1).
L = 0 - 1 * 0 = 0
В итоге наилучший вариант загрузки рюкзака достигается при значениях: x₁ = 0, x₂ = 3, x₃ = 0, x₄ = 1, x₅ = 0

Задача оптимального раскроя

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

Есть достаточно большое число одномерных заготовок одинаковой длины D = 2,6 м. Заготовки следует разрезать на детали 3 типов длиной L = (1,5; 0,9; 1,2). По данным числам D и L_i составить матрицу всех возможных способов раскроя A = a_ij, где каждое a_ij указывает количество деталей i типа, что выходит из одной заготовки при раскрое по j способому, если заданы также потребности B = (45, 74, 66), в деталях i типа.
Составить математическую модель и решить задачу линейного программирования для выполнения планового задания, раскроив минимальное число заготовок.

Решение

Составим таблицу исходных данных:

i	Li	Bi
	1,5
	0,9
	1,2

Заполним матрицу всех возможных способов раскроя, учтя длину заготовок D = 2,6 м:

Длина раскроев	Способы раскроя
1	2	3	4
1,5
0,9
1,2

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

Получим задачу целочисленного линейного программирования:

z = x ₁ + x ₂ + x ₃ + x ₄ → min

x ₁, x ₂, x ₃, x ₄ > 0

1) Первый этап

Найдем решение, отбросив условие целочисленности. Изменим знаки целевой функции на противоположные и будем рассматривать задачу на максимум:
z = - x ₁ - x ₂ - x ₃ - x ₄ → max

Сведем задачу к каноническому виду, для чего прибавим дополнительные или базисные векторы [АКУ, с. 12]:

Для увеличения количества базисных векторов отнимаем от строки, которая содержит отрицательную вспомогательную переменную и максимальный B ₂ = 74 все строки с отрицательными вспомогательными переменными (1, 3) [ГЕТ, с. 177].

Поскольку начальный план нельзя построить обычным образом, используем метод искусственного базиса [АКУ, с. 47].
Вектор z ₁ является искусственным.

Тогда целевая функция запишется так:

z = - x ₁ - x ₂ - x ₃ - x ₄ – Mz ₁ → max,

где M - большое число.

Построим начальную симплекс-таблицу, где
Q - неотрицательное отношение столбца плана к ключевому столбцу.

№

Базис

Cб

План

-1

-1

-1

-1

- M

Q

x 1

x 2

x 3

x 4

x 5

x 6

x 7

z 1

x 5

-1

29/2

z 1

- M

-1

x 7

-2

-1

Δ j

–

-74

-1

-2

-1

–

Cтолбик 2 есть ключевым, поскольку он содержит минимальный отрицательный элемент

Δ₂ = -2 M + 1.

Строка 3 есть ключевой, поскольку в ней минимальное Q ₃ = 4.
Ключевой элемент находится на их пересечении и равный числу 2.
Вместо вектора x ₇, который удаляем из базиса, вводим вектор x ₂.
Делим ключевую строку на ключевой элемент 2.
Умножаем его на -1 и добавляем к 4 строке.
Умножаем его на -2 и добавляем к 1 строке.
Умножаем его на -2 и добавляем к 2 строке.
Получим следующую симплекс-таблицу.

№

Базис

Cб

План

-1

-1

-1

-1

- M

Q

x 1

x 2

x 3

x 4

x 5

x 6

x 7

z 1

x 5

-1

-1

21/2

z 1

- M

-1

x 2

-1

1/2

-1

-1/2

1/2

–

Δ j

-4

1/2

1/2

-1/2

–

-66

-1

-2

–

Cтолбик 4 есть ключевым, поскольку он содержит минимальный отрицательный элемент Δ₄ = -2 M + 2.

Строка 1 есть ключевой, поскольку в ней минимальное Q ₁ = 21/2.
Ключевой элемент находится на их пересечении и равный числу 2.
Вместо вектора x ₅, который удаляем из базиса, вводим вектор x ₄.
Делим ключевую строку на ключевой элемент 2.
Умножаем его на -2 и добавляем к 4 строке.
Умножаем его на -2 и добавляем к 2 строке.
Умножаем его на 1 и добавляем к 3 строке.
Получим следующую симплекс-таблицу.

№

Базис

Cб

План

-1

-1

-1

-1

- M

Q

x 1

x 2

x 3

x 4

x 5

x 6

x 7

z 1

x 4

-1

21/2

-1/2

1/2

1/2

-1/2

–

z 1

- M

-1

x 2

-1

29/2

1/2

1/2

-1/2

–

Δ j

-25

3/2

-1

1/2

1/2

–

-45

-1

–

Cтолбик 1 есть ключевым, поскольку он содержит минимальный отрицательный элемент Δ₁ = - M + 3/2.
Строка 2 есть ключевой, поскольку в ней минимальное Q ₂ = 45.
Ключевой элемент находится на их пересечении и равный числу 1.
Вместо вектора z ₁, который удаляем из базиса, вводим вектор x ₁. Дальше из расчетов данную искусственную переменную исключаем.
Делим ключевую строку на ключевой элемент 1.
Умножаем его на -3/2 и добавляем к 4 строке.
Умножаем его на 1/2 и добавляем к 1 строке.
Получим следующую симплекс-таблицу.

№	Базис	Cб	План	-1	-1	-1	-1				Q
x 1	x 2	x 3	x 4	x 5	x 6	x 7
	x 4	-1				1/2				-1/2
	x 1	-1						-1			–
	x 2	-1	29/2			1/2		1/2	-1/2
	Δ j	-185/2					1/2	1/2	1/2	–

Поскольку содержится нуль в небазисном векторе x ₃, то существует еще одно оптимальное решение, которое также найдем. Строка 3 есть ключевой, поскольку в ней минимальное Q ₃ = 29.
Ключевой элемент находится на их пересечении и равный числу 1/2.
Вместо вектора x ₂, который удаляем из базиса, вводим вектор x ₃.
Делим ключевую строку на ключевой элемент 1/2.
Умножаем его на -1/2 и добавляем к 1 строке.
Получим окончательную симплекс-таблицу.

№	Базис	Cб	План	-1	-1	-1	-1
x 1	x 2	x 3	x 4	x 5	x 6	x 7
	x 4	-1	37/2		-1			-1/2	1/2	-1/2
	x 1	-1						-1
	x 3	-1							-1
	Δ j	-185/2					1/2	1/2	1/2

Последняя строка таблицы не содержит отрицательных элементов, следовательно найденное решение является оптимальным: X = (45, 0, 29, 37/2), z_max = -185/2.
Вернувшись к замене знака функции, получим: z_min = 185/2.

Решение имеет дробные значения, поэтому переходим ко 2 этапу.

2) Второй этап

Применим метод Гомори для поиска целочисленного решения [АКУ, с. 180].
Дополнительные ограничения строятся по формуле на основании строки,
переменная плана которого имеет наибольшую дробную часть.
Вычислим дробные части основных переменных плана: f ₁(x ₄) = 0,5000.
Неравенство строим на основании 1 строки




Добавляем уравнение к системе уравнений и строим симплекс-таблицу с новым ограничением.
Новую задачу решаем двойственным симплекс-методом [АКУ, с. 107].

№	Базис	Cб	План	-1	-1	-1	-1
x 1	x 2	x 3	x 4	x 5	x 6	x 7	x 8
	x 4	-1	37/2		-1			-1/2	1/2	-1/2
	x 1	-1						-1
	x 3