Второй этап – составление математической модели задачи

1. На основании полученных в первом этапе исходных данных и описания заданного производственного процесса составляется следующая таблица:

 

Продукты ресурсы
I
II

 

Через Х₁ обозначим ресурсы I вида.

Через Х₂ обозначим ресурсы II вида.

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

 

8Х₁ + 4Х₂ + 6Х₃ ≤ 1000

240Х₁+ 200Х₂ + 160Х₃ ≤ 280000

 

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

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

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

 

Третий этап – выбор метода решения полученной математической задачи

Решение

1. Для решения задач линейного программирования симплекс – методом задача приводиться к каноническому виду:

8Х₁ + 4Х₂ + 6Х₃ + Х₄= 1000

240Х₁+ 200Х₂ + 160Х₃ + Х₅= 280000

 

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

 

Базисные переменные	Х1	Х2	Х3	Х4	Х5	Свободный член
Х4
Х5

 

А) Нашли некоторое неотрицательное базисное решение: Х₄ =1300, Х₅ = 190000. По заданию продолжаем искать базисные решения. Разрешающим элементом выбираем в 1 строке – Х₂. Соответственно вся строка делится на 8, а все остальные элементы находятся по правилу прямоугольника.

 

Базисные переменные	Х1	Х2	Х3	Х4	Х5	Свободный член
Х4
Х5
Базисные переменные	Х1	Х2	Х3	Х4	Х5	Свободный член
Х2	¾		½	1/8		325/2
Х5				-25

 

Б) Нашли некоторое неотрицательное базисное решение: Х₂ =325/2, Х₅ =157500. По заданию продолжаем искать базисные решения. Разрешающим элементом выбираем в 1 строке – Х₁. Соответственно вся строка делится на 3/4, а все остальные элементы находятся по правилу прямоугольника.

 

Базисные переменные	Х1	Х2	Х3	Х4	Х5	Свободный член
Х2	¾		½	1/8		325/2
Х5				-25
Базисные переменные	Х1	Х2	Х3	Х4	Х5	Свободный член
Х1		4/3	2/3	1/6		650/3
Х5		-120		-40

 

В) Нашли некоторое неотрицательное базисное решение: Х₁ =650/3, Х₅ =138000. По заданию продолжаем искать базисные решения. Разрешающим элементом выбираем в 1 строке – Х₃. Соответственно вся строка делится на 2/3, а все остальные элементы находятся по правилу прямоугольника.

 

Базисные переменные	Х1	Х2	Х3	Х4	Х5	Свободный член
Х1		4/3	2/3	1/6		650/3
Х5		-120		-40
Базисные переменные	Х1	Х2	Х3	Х4	Х5	Свободный член
Х3	3/2			1/4
Х5		-120		-40

 

Г) Нашли некоторое неотрицательное базисное решение: Х₅ =138000, Х₃ =325. Найдены все неотрицательные базисные решения.

2. Находим получаемый продукт.

Х₁= 6*0+8*0+4*0=0

Х₂=240*0+200*0+160*0=0

У₁=3*0^0,4*0^0,6=0

У₂=5*0^0,5*0^0,5=0

У₃=8*0^0,6*0^0,4=0

F₁=0+0+0=0

Х₁= 6*0+8*325/2+4*0=1300

Х₂=240*0+200*325/2+160*0=32500

У₁=3*1300^0,4*32500^0,6=26904,728

У₂=5*1300^0,5*32500^0,5=32500

У₃=8*1300^0,6*32500^0,4=37688,542

F₂=26904,728 +32500 +37688,542 = 97093,27

Х₁= 6*650/3+8*0+4*0=1300

Х₂=240*650/3+200*0+160*0=52000

У₁=3*1300^0,4*52000^0,6=35699,794

У₂=5*1300^0,5*52000^0,5=41109,610

У₃=8*1300^0,6*52000^0,4=45483,862

F₃= 35699,794+ 41109,610+ 45483,862= 122263,266

Х₁= 6*0+8*0+4*325=1300

Х₂=240*0+200*0+160*325=52000

У₁=3*1300^0,4*52000^0,6=35699,794

У₂=5*1300^0,5*52000^0,5=41109,610

У₃=8*1300^0,6*52000^0,4=45483,862

F₃= 35699,794+ 41109,610+ 45483,862= 122263,266

F₁ < F₂

F₂ < F₃

F₃ = F₄

Ответ: F_max= 122263,266

Четвертый этап – подготовка словесного алгоритма решения задачи

 

1. Вводим данные в таблицу

2. Выбираем разрешающий элемент:

2.1. Берем каждый неотрицательный элемент первой строки и делим на свободный член первой строки.

2.2. Находим среди всех деленных элементов минимальный.

2.3. Берем каждый неотрицательный элемент второй строки и делим на свободный член второй строки.

2.4. Находим среди всех деленных элементов минимальный.

2.5. Берем каждый неотрицательный элемент n-ой строки и делим на свободный член n-ой строки.

2.6. Находим среди всех деленных элементов минимальный.

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

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

3.1. Умножаем разрешающий элемент на элемент решаемой строки.

3.2. Отнимаем произведение соответствующего элемента решаемой строки на элемент разрешающего столбца решаемой строки

3.3. И делим ответ на разрешающий элемент.

3.4. Делим разрешающую строку на разрешающий элемент.

3.5. Берем каждый элемент разрешающей строки и делим на разрешающий элемент.

3.6. Всем элементам, кроме разрешающего элемента, разрешающего столбца присвоим (0)

3.7. Разрешающему элементу присвоим (1).

В индексе разрешающей строки присвоить индекс

4. Повторяем процедуру вычисления с 2 пункта.

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

6. Находим все F.

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