Аналитическое решение задачи

Аналитическое решение задачи с «ручными» расчетами рассмотрим на примере выбора оптимального промыслово-технического режима работы траулера. При этом используется симплекс-метод решения задач линейного программирования, который реализует аналитический перебор вершин ОДР в порядке ускоряющем получение оптимума. Реализация этого метода на ЭВМ или ПК выполняется методами прикладных программ линейного программирования.

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

1) максимально-возможный вылов рыбы за сутки А=100 т

2) Возможная заморозка рыбы в этот период В=40 т

3) Условия работы: Расход сырья:

Х₁ – заморозка колодки 1 т

Х₂ – заморозка без головы 1,4 т

Х₃ – филе 2 т

4) Стоимость 1 т готовой продукции Возможная заморозка и выпуск готовой продукции

Х₁ ® 600 40 т

Х₂ ® 850 20 т

Х₃ ® 1700 2 т

Таким образом математическая модель задачи имеет вид:

Х₁+1,4Х₂+2Х₃£100 – ограничение по вылову,

Х₁+Х₂+Х₃£40 – ограничения по выпуску продукции,

Х₂£20 - ограничения по выпуску обезглавленной рыбы,

Х₃£2 - ограничения по выпуску филе,

Х₁³0 Х₂³0 Х₃³0 – положительные значения показателей работы судна.

Для расчетов составляем симплекс матрицу в которую записывается исходные ограничения в виде уравнений за счет введения в неравенства фиктивных переменных: У₁, У₂, У₃, У₄.

У₁+Х₁+1,4Х₂+2Х₃=100

У₂+Х₁+Х₂+Х₃=40

У₃+ Х₂=20

У₄+ Х₃=2

Показатели целевой функции записываются в симплекс матрицу со знаками (-) при условии .

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

Таблица 1

I	Проб. реш.	Х1	Х2	Х3
У1			1,4	2,0
У2
У3
У4				1 (КЭ)
L		-600	-850	-1700

Таблица 2

II	Проб. реш.	Х1	Х2	Х4
У1			1,4	-2
У2				-1
У3			1 (КЭ)
Х3
L		-600	-850	+1700

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

В старой матрице (таблица 1):

1. выбирается ключевой столбец с наибольшим отрицательным элементом целевой строки;

2. ключевая строка выбирается по min частному положительному числу величин пробного решения деленных на коэффициент ключевого столбца. Коэффициент пересечения ключевых столбца и строки, выделенные в таблицах, называется ключевым элементом Кэ;

В новой матрице (таблица 2):

3. заменяем фиктивную переменную на реальную в ключевых строке и столбце;

4. ключевой элемент заменяется обратной величиной (1);

5. элементы ключевой строки заменяются частичными их деления на ключевой элемент;

6. элементы ключевого столбца заменяют частичными от их деления на ключевой элемент с обратным знаком;

7. все остальные элементы рассчитываются по формуле:

(2.4.1)

M и N – элементы, находящиеся в противоположных углах прямоугольника, опирающегося на старый элемент (Сэ) и ключевой элемент (Кэ), т.е. M и N – это концы диагонали прямоугольника противоположного Сэ и Кэ.

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

Для

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

А) величины Х₀₁, Х₀₂, Х₀₃ – равны значениям колонки пробного решения при действительных переменных;

Б) значения пробного решения в строке L дает оптимальную величину целевой функции.