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

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

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

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	100	1	1,4	2,0
У2	40	1	1	1
У3	20	0	1	0
У4	2	0	0	1 (КЭ)
L	0	-600	-850	-1700

 

Таблица 2

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

 

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

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

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

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

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

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

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

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

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

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

                                                                          (2.4.1)

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

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

Для

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

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

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

Вопросы для самопроверки

 

1. Отличие линейного программирования от линейной алгебры.

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

3. Как находить оптимальное решение задачи с минимумом или максимумом целевой функции.

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

5. Постановка задачи выбора оптимального промыслово-технологического режима работы добывающего судна.

6. Получение первой симплекс-матрицы задачи линейного программирования.

7. Правила преобразования симплекс-матриц при итеративном процессе.

8. Использование результатов преобразования симплекс-матриц.

9. Понятие о двойственной задаче линейного программирования.

 

⇐ Предыдущая10111213141516171819Следующая ⇒

Поделиться: