1. На основании полученных в первом этапе исходных данных и описания заданного производственного процесса составляется следующая таблица:
Продукты ресурсы | ||||
I | ||||
II |
Через Х1 обозначим ресурсы I вида.
Через Х2 обозначим ресурсы II вида.
2. Обращаясь к условиям задачи, определяем все возможные ограничения, объединяя их в систему ограничений.
8Х1 + 4Х2 + 6Х3 ≤ 1000
240Х1+ 200Х2 + 160Х3 ≤ 280000
Таким образом, получили задачу нелинейного программирования. Такие задачи называются задачами нелинейного программирования.
Решение задач нелинейного программирования осуществляется приведением их к задачам линейного программирования.
Для решения задачи линейного программирования применяется симплекс – метод.
Третий этап – выбор метода решения полученной математической задачи
Решение
1. Для решения задач линейного программирования симплекс – методом задача приводиться к каноническому виду:
8Х1 + 4Х2 + 6Х3 + Х4= 1000
240Х1+ 200Х2 + 160Х3 + Х5= 280000
2. Составляем таблицу и определяем все неотрицательные базисные решения системы.
Базисные переменные | Х1 | Х2 | Х3 | Х4 | Х5 | Свободный член |
Х4 | ||||||
Х5 |
А) Нашли некоторое неотрицательное базисное решение: Х4 =1300, Х5 = 190000. По заданию продолжаем искать базисные решения. Разрешающим элементом выбираем в 1 строке – Х2. Соответственно вся строка делится на 8, а все остальные элементы находятся по правилу прямоугольника.
Базисные переменные | Х1 | Х2 | Х3 | Х4 | Х5 | Свободный член |
Х4 | ||||||
Х5 | ||||||
Базисные переменные | Х1 | Х2 | Х3 | Х4 | Х5 | Свободный член |
Х2 | ¾ | ½ | 1/8 | 325/2 | ||
Х5 | -25 |
Б) Нашли некоторое неотрицательное базисное решение: Х2 =325/2, Х5 =157500. По заданию продолжаем искать базисные решения. Разрешающим элементом выбираем в 1 строке – Х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 |
В) Нашли некоторое неотрицательное базисное решение: Х1 =650/3, Х5 =138000. По заданию продолжаем искать базисные решения. Разрешающим элементом выбираем в 1 строке – Х3. Соответственно вся строка делится на 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 |
Г) Нашли некоторое неотрицательное базисное решение: Х5 =138000, Х3 =325. Найдены все неотрицательные базисные решения.
2. Находим получаемый продукт.
Х1= 6*0+8*0+4*0=0
Х2=240*0+200*0+160*0=0
У1=3*00,4*00,6=0
У2=5*00,5*00,5=0
У3=8*00,6*00,4=0
F1=0+0+0=0
Х1= 6*0+8*325/2+4*0=1300
Х2=240*0+200*325/2+160*0=32500
У1=3*13000,4*325000,6=26904,728
У2=5*13000,5*325000,5=32500
У3=8*13000,6*325000,4=37688,542
F2=26904,728 +32500 +37688,542 = 97093,27
Х1= 6*650/3+8*0+4*0=1300
Х2=240*650/3+200*0+160*0=52000
У1=3*13000,4*520000,6=35699,794
У2=5*13000,5*520000,5=41109,610
У3=8*13000,6*520000,4=45483,862
F3= 35699,794+ 41109,610+ 45483,862= 122263,266
Х1= 6*0+8*0+4*325=1300
Х2=240*0+200*0+160*325=52000
У1=3*13000,4*520000,6=35699,794
У2=5*13000,5*520000,5=41109,610
У3=8*13000,6*520000,4=45483,862
F3= 35699,794+ 41109,610+ 45483,862= 122263,266
F1 < F2
F2 < F3
F3 = F4
Ответ: Fmax= 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. Выбираем наибольшую из них, которая будет являться оптимальным планом выпуска продукции.