В 1-ом неравенстве вводим базисную переменную x₄:

Введем искусственную переменную x₅ во 2-ое равенство:

Для постановки задачи на минимум целевую функцию запишем так:

Получений базис называется искусственным, а метод решения называется методом искусственного базиса.

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

Из уравнений выражаем искусственные переменные, которые подставляем в целевую функцию:

Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

Базисное решение называется допустимым, если оно неотрицательно.

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

Таблица 1 – Начальная симплекс-таблица

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

Проводим итерацию №0 для проверки критерия оптимальности.

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

Текущий опорный план не оптимален, так как в индексной строке находятся положительные коэффициенты.

Далее переходим определению новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент.

Далее переходим пределению новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3
и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (6) и находится на пересечении ведущего столбца и ведущей строки (Таблица 2).

Таблица 2 – Симплекс-таблица с выделенным разрешающим элементом

Далее проводим пересчет симплекс-таблицу по разрешающему элементу (Таблица 3).

Таблица 3 – Симплекс-таблица после совершения итерации №0

Проводим итерацию №1 для проверки критерия оптимальности.

Текущий опорный план не оптимален, так как в индексной строке находятся положительные коэффициенты.

Далее переходим к определению новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент.

Далее переходим к определению новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2
и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (¹/₃) и находится на пересечении ведущего столбца и ведущей строки (Таблица 4).

Таблица 4 – Симплекс-таблица с выделенным разрешающим элементом

Проводим пересчет симплекс-таблицу по разрешающему элементу (Таблица 5).

Таблица 5 – Симплекс-таблица после совершения итерации №0

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

---

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.

Оптимальный план можно записать так:

Как следствие, используя симплекс-метод, установлено, что для минимизации времени ремонта нам необходимо распределить устройства следующим образом: в мастерскую №1 будет направленно устройств в количестве 0 шт., в мастерскую №2 будет направленно устройств в количестве 3, в мастерскую №3 будет направленно устройств в количестве 3. При этом минимальное время для ремонта всех устройств будет равно 18.

---

4.2 Решение методом Гомори.

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

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

1. Решаем задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования.

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

- оно должно быть линейным;

- должно отсекать найденный оптимальный нецелочисленный план;

- не должно отсекать ни одного целочисленного плана.

Для удобного представление решения используется программа для работы с электронными таблицами MS Excel.

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

Определим минимальное значение целевой функции

при следующих условиях-ограничений:

Введем искусственные переменные x: в 1-м равенстве вводим переменную x₄; в 2-м равенстве вводим переменную x₅;

Для постановки задачи на минимум целевую функцию запишем так:

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

Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.

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

Из уравнений выражаем искусственные переменные:

которые подставим в целевую функцию:

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

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

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

Решим систему уравнений относительно базисных переменных: x₄, x₅

Полагая, что свободные переменные равны 0, получим первый опорный план:

X₁ = (0,0,0,30,6)

Базисное решение называется допустимым, если оно неотрицательно.

---

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

Проводим итерацию №0 для проверки критерия оптимальности.

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

Текущий опорный план не оптимален, так как в индексной строке находятся положительные коэффициенты.

Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент.

Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3

и из них выберем наименьшее:

min (30 : 6 , 6 : 1 ) = 5

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (6) и находится на пересечении ведущего столбца и ведущей строки (Таблица 6).

---

Таблица 6 – Симплекс-таблица с выделенным разрешающим элементом

Базис	B	x1	x2	x3	x4	x5
x4	30	5	4	6	1	0
x5	6	1	1	1	0	1
F(X1)	36M	-3+6M	-4+5M	-2+7M	0	0

Формируем следующую часть симплексной таблицы.

Вместо переменной x₄ в план 1 войдет переменная x₃.

Строка, соответствующая переменной x₃ в плане 1, получена в результате деления всех элементов строки x₄ плана 0 на разрешающий элемент 6

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x₃ плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x₃ и столбец x₃.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

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

Проводим пересчет симплекс-таблицу по разрешающему элементу (Таблица 7).

Таблица 7 – Симплекс-таблица после совершения итерации №0

Базис	B	x1	x2	x3	x4	x5
x3	5	5/6	2/3	1	1/6	0
x5	1	1/6	1/3	0	-1/6	1
F(X1)	10+M	-11/3+M	-22/3+M	0	1/3-11/6M	0

Проводим итерацию №1 для проверки критерия оптимальности.

Текущий опорный план не оптимален, так как в индексной строке находятся положительные коэффициенты.

Определение новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент.

Определение новой свободной переменной.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее:

min (5 : ²/₃ , 1 : ¹/₃ ) = 3

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (¹/₃) и находится на пересечении ведущего столбца и ведущей строки. (Таблица 8)

Таблица 8 – Симплекс-таблица с выделенным разрешающим элементом

Базис	B	x1	x2	x3	x4	x5
x3	5	5/6	2/3	1	1/6	0
x5	1	1/6	1/3	0	-1/6	1
Базис	B	x1	x2	x3	x4	x5
F(X2)	10+M	-11/3+M	-22/3+M	0	1/3-11/6M	0

Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x₅ в план 2 войдет переменная x₂.

Строка, соответствующая переменной x₂ в плане 2, получена в результате деления всех элементов строки x₅ плана 1 на разрешающий элемент ¹/₃

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₂ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₂ и столбец x₂.

---

Смотрите также файлы

• Методы оптимизации Зыкина.docx

• РЕФЕРАТ_ФИЗКУЛЬТУРА.docx

• физра реферат.doc

• конкуренты.docx

• Отчёт о патентном исследовании Ермакова.doc