Курсовая работа: Задача линейного программирования

Система ограничений – это совокупность уравнений и неравенств, которым удовлетворяют переменные задачи и которая следует из ограниченности экономических условий задачи.

В общем виде система записывается в виде

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 Составление математической модели задачи

Записываем условие задачи в виде таблицы.

Таблица

Вид ресурса

Расход рес. на производство ед. продукции

К-во Просмотров: 494
Бесплатно скачать Курсовая работа: Задача линейного программирования