Навигация
Составляют систему ограничения задачи
15809
знаков
4
таблицы
17
изображений
2. Составляют систему ограничения задачи.
Система ограничений – это совокупность уравнений и неравенств, которым удовлетворяют переменные задачи и которая следует из ограниченности экономических условий задачи.
В общем виде система записывается в виде
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 Составление математической модели задачи
Записываем условие задачи в виде таблицы.
Таблица
| Вид ресурса | Расход рес. на производство ед. продукции | Запас ресурса | ||
| Ι | ІΙ | ІΙІ | ||
| сырьё | 4 | 2 | 10 | 420 |
| трудовые ресурсы | 6 | 2 | 8 | 120 |
| накладные расходы | 4 | 2 | 18 | 250 |
| Прибыль | 28 | 24 | 20 | max |
1. Выбирают переменные задачи.
Пусть 
количество производимых станков 1-ого, 2-ого и 3-его вида, 
Похожие работы
... лучей, исходящих из одной точки, называется многогранным выпуклым конусом с вершиной в данной точке. 1.4 Математические основы решения задачи линейного программирования графическим способом 1.4.1 Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n = 2 и n = ...
... . При этом значения cij соответствуют коэффициентам целевой функции исходной замкнутой транспортной задачи (1) и в последующем не изменяются. Элементы xij соответствуют значениям переменных промежуточных решений транспортной задачи линейного программирования и изменяются на каждой итерации алгоритма. Если в некоторой ячейке xij=0, то такая ячейка называется свободной, если же xij>0, то такая ...
... решения останется неизменным, т.е. будет состоять из переменных (Х3,Х6,Х4,Х5). СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 1. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного программирования. Ч.1. – Мн.: БГУИР, 1995. 2. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного ...
... . 1.3. Построение ограничений и градиента целевой функции : 1.4. Область допустимых решений – отрезок AB. 1.5. Точка А – оптимальная. Координаты т. А: ; ; . 2. Решение задачи линейного программирования симплекс-методом. Прямая задача. Задачу линейного программирования для любой вершины в компактной форме можно представить в виде: Для получения используем алгоритм, приведённый в ...
0 комментариев