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