Задача линейного программирования (стр. 2 из 3)
Известно, что для изготовления станка Ι – ого вида требуется 4 ед. сырья, 2 ед. трудовых ресурсов и 10 ед. накладных расходов; станка ΙІ – ого вида 6 ед. сырья, 2 ед. трудовых ресурсов и 8 ед. накладных расходов; для станка ΙΙІ – ого вида требуется 4 ед. сырья, 2 ед. трудовых ресурсов и 18 ед. накладных расходов; Предприятие имеет в наличии 420 ед. сырья, 120 ед. трудовых ресурсов и 250 ед. накладных ресурсов.
Прибыль от реализации станка І вида - 28 тыс. руб., ІΙ вида - 24 тыс. руб., ΙІΙ вида - 20 тыс. руб. Условия производства требует, чтобы трудовые ресурсы были использованы полностью, а накладные расходы были бы не менее имеющихся в наличии.
Составить план производства станков, обеспечивающих максимальную прибыль.
§ 2 Составление математической модели задачи
Записываем условие задачи в виде таблицы.
Таблица
| Вид ресурса | Расход рес. на производство ед. продукции | Запас ресурса | ||
| Ι | ІΙ | ІΙІ | ||
| сырьё | 4 | 2 | 10 | 420 |
| трудовые ресурсы | 6 | 2 | 8 | 120 |
| накладные расходы | 4 | 2 | 18 | 250 |
| Прибыль | 28 | 24 | 20 | max |
1. Выбирают переменные задачи.
Пусть
количество производимых станков 1-ого, 2-ого и 3-его вида, 
2. Составляем систему ограничения задачи
по условию задачи требуется, чтобы
трудовые ресурсы были использованы полностью значит, ставим знак (=), а накладные расходы были бы не менее имеющихся в наличии значит, ставим знак (
).3. Задаём целевую функцию
Z(X) =
Математическая модель имеет вид: найти план выпуска станков
X = (
),удовлетворяющий системе ограничений задачи
и условию неотрицательности
), при котором прибыль будет максимальнойZ(X) =
§ 3 Алгоритмы решения задачи симплексным методом
Общая идея симплексного метода (метода последовательного улучшения плана) для решения задачи линейного программирования состоит
1) умение находить начальный опорный план;
2) наличие признака оптимальности опорного плана;
3) умение переходит к нехудшему опорному плану.
Алгоритм:
1) Математическая модель задачи должна иметь каноническую форму. В противном случаи её приводят к каноническому виду.
2) Находят начальное опорное решение задачи. Им является вектор, состоящий из тех переменных, которые входят только в одно уравнение в системе ограничений. Если начальное решение сразу не найти то используют метод Гаусса.
Количество переменных решения равно количеству уравнений системы. Заполняют симплексную таблицу по системе ограничений и целевой функции.
Макет симплексной таблицы:
| Б |  |  |  |  |  |  | … |  |  |
 |  |  |  |  | … |  | |||
| … | |||||||||
| … | |||||||||
| … | … | … | … | … | … | … | … | … | … |
 | |||||||||
Первый столбец – коэффициенты в целевой функции при базисных переменных.
Второй столбец – базисные переменные.
Третий столбец – свободные члены.
Самая верхняя строка – коэффициенты при целевой функции.
Вторая верхняя строка – сами переменные, входящие в целевую функцию и в систему ограничений.
Основное поле симплекс метода – система коэффициентов из уравнения.
Последняя строка – служит для того, чтобы ответить на вопрос: “оптимален план или нет ”.
Индексная строка позволяет нам судить об оптимальности плана.
3) Проверяют опорное решение, на оптимальность, вычисляя коэффициенты индексной строки по форме:
При решении задачи возможны два случая:
- При решении задачи на максимум:
а) все оценки
следует, что решение оптимальноеб) хотя бы одна оценка
и при соответствующей переменной нет положительных коэффициентов, то задача не имеет оптимального решения m, k, целевая функция неограниченна в О.Д.Р.в) хотя бы одна оценка
и при соответствующей переменной есть положительный коэффициент то данное решение можно улучшить, построив новое опорное решение на котором целевая функция будет больше.- При решении задачи на минимум:
а) все оценки
следует, что решение оптимальноеб) хотя бы одна оценка
и при соответствующей переменной нет положительных коэффициентов, то задача не имеет оптимального решения m, k, целевая функция неограниченна в О.Д.Р.в) хотя бы одна оценка
и при соответствующей переменной есть положительный коэффициент то данное решение можно улучшить, построив новое опорное решение.4) Новое опорное решение находится с помощью ключевого столбца, ключевой строки и ключевого элемента.
Ключевой столбец указывает на переменную, которую надо вывести из числа базисных для улучшения решения.
Ключевая строка указывает на переменную, которую надо вывести из числа базисных для улучшения решения.
Ключевой элемент нужен для элементов нового опорного решения (для новой симплексной таблицы).
Их нахождения зависит от цели задачи.
- При решении задачи на максимум:
а) ключевой столбец – это столбец с отрицательной наименьшей оценкой
в индексной строке.б) ключевая строка – это строка с наименьшим отношением свободных членов к положительным коэффициентам ключевого столбца:
min
= 
в) ключевой элемент – это число расположенное на пересечении ключевых столбца и строки(не может быть равен нулю).
- При решении задач на минимум:
а) ключевой столбец – это столбец с положительной наименьшей оценкой
в индексной строке.б) ключевая строка – это строка с наибольшим отношением свободных членов к положительным коэффициентам ключевого столбца:
mах
= в) ключевой элемент – это число расположено на пересечении ключевых столбца и строки.
5) Заполняют первую симплексную таблицу следующим образом:
а) ключевую строку делят на ключевой элемент и записывают на том же месте в новой таблице.
б) заполняют базисные столбцы.
в) остальные элементы пересчитывают по правилу “прямоугольника”:
НЭ = СТЭ –
где НЭ – новый элемент
СТЭ – элемент старого плана
РЭ – разрешающей элемент
А и Б – элементы старого плана
6) Возвращаются ко второму этапу алгоритма – проверка плана на оптимальность.
§ 4 Построение начального опорного решения методом Гаусса
Приводим задачу к каноническому виду.
Z(X) =
)