Задача и назначение.

Задача линейного программирования..

Условие: Предприятие производит изделия двух видов: изделие А и изделие В. При изготовлении изделий используются два вида сырья: М1 и М2. Максимально возможный запас этих материалов составляет 250 и 320 кг. Норма расхода сырья (кг) на одно изделие приведен в табл. 1.

Таблица 1

На основании изучения рынка сбыта установлено, что спрос на изделие А никогда не превышает спроса на изделие В более чем на 10едениц. Кроме того известно, что спрос на изделие А никогда не превышает15 едениц. Прибыль от реализации одного изделия вида А равен а₁ = 35 грн., Прибыль от реализации одного изделия вида В равна а₂ = 40 грн.

Необходимо составить такой план производства, при котором прибыль предприятия от реализации всех изделий является максимальным.

Построим математическую модель.

Необходимо ответить на 3 основных вопроса:

- Какие величины использовать в качестве переменных?

- В чем состоит конечная цель?

- Какие ограничения накладываются на переменные?

Для построения математической модели выбираем переменные, строим целевую функцию и ограничения.

Переменные.

Переменные выбираем на основании вопросы, содержится в условии задачи.

Пусть x₁ - объем производства изделий вида А , x₂ - объем производства изделий вида В.

Целевая функция.

Поскольку предприятие делает А по цене а₁ за 1 изделие x₂ и зделий вида В по цене а₂ за 1 изделие, то общая прибыль от производства изделий обоих видов будет:

Ограничения.

По условию задачи расход материалов М₁ і М₂ на одно изделие соответствующего вида составляет:

; ; ; .

Максимально возможный запас сырья составляет:

; .

Расход исходного материала для производства изделий обоих видов не должна превышать максимально возможного запаса соответствующего материала:

для сырья вида М₁;

для сырья вида М₂.

Превышение спроса на изделие вида А по спросу на изделие вида В:

Спрос на изделие вида В не превышает 15 едениц:

Количество изготовленных изделий не может быть отрицательным числом:

Таким образом рассмотрим следующее математическую задачу: среди всех неотрицательных решений данной системы линейных неравенств необходимо найти такое, при котором функция f принимает максимальное значение: max (целевая функция).

при

(ограничения)

Эта модель является линейной, так как целевая функция и ограничения представляют собой линейные функции относительно переменных х₁ и х₂.

Определим область допустимых решений. Для этого в неровностях системы ограничений и условиях неотрицательности переменные знаки неровностей заменяем на знаки точных равенств и найдем соответствующие прямые:

Каждая прямая, представляющий ограничения в виде равенства, делит плоскость на две полуплоскости. В одной полуплоскости удовлетворяются выходные неравенства, в другой - не удовлетворяются. Определяем искомую полуплоскость, берем какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверяем, удовлетворяют ее координаты данной неравенства. Если координаты этой точки удовлетворяют данной неровности, значит эта точка принадлежит области допустимых решений.

Условия и означают, что область допустимых решений располагается справа от оси ординат и над осью абсцисс.

Таким образом, ограничения создают область допустимых решений.

Максимального значения функция f достигнет (при условии, что точки прямой будут принадлежать пространства решений) в точке пересечения прямых и .

Координаты этой точки можно найти путем решения системы уравнений:

Отсюда x₁ = 20; x₂ = 10.

Это и есть оптимальное решение. В этой точке функция достигает максимального значения, при этом удовлетворяются все ограничения задачи.

Также проводим расчет с помощью программного продуктаMathCAD.

Задача и назначение.

Постановка задачи: на пяти токарных станках различных типов выполняются пять различных технологических операций. Та же операция может выполняться только на одном станке. За каждым станком может быть закреплена только одна операция. Время выполнения каждой из операций на каждом из станков задано матрицей с_ij:

Нужно так распределить операции между станками, чтобы суммарное время на обработку деталей был минимальным.

Решение:

Пусть

1, если i-м станке выполняется j-я операция;

x_ij =

0, если i-м станке выполняется j-я операция.

По условию задачи по каждому станком закреплена только одна операция. Это выражается следующими равенствами:

Каждая операция может выполняться только на одном станке:

Сформулируем задачу о назначении в следующем виде:

найти значения неизвестных x_ij (i = 1...5…5; j=1…5), удовлетворяющей системе уравнений і равные 0 или 1, при которых функция

принимает минимальное значение.

Решение задачи проводим с помощью пакета программ MathCAD. Суммарные затраты времени будут минимальными, если на первом станке выполнять четвертую операцию, на втором станке - первую, на третьем - вторую, на четвертом - третью, на пятом - пятую.
Список использованной литературы:

1. Вентцель Е.С. Исследование операций: задачи, принципы, методология.- М .: Наука, Главная редакция физико-математической литературы, 1975.

2. Акулич И. Л. Математическое программирование в примерах и задачах. Учеб. пособие для студ. экономич. специальн. вузов. М .: Высшая школа, 1986.

3. Конспект лекций ДонИЖТ 2007.

4. Математические методы в планировании на железнодорожном транспорте. А.Б. Каплан, И.В. Белов. Транспорт 1972 г., 248с.

5. Сборник задач по математическому моделированию на железнодорожном транспорте. Учебное пособие для ВУЗов ж-д транспорта М., «Транспорт», 1978. 200 с. Авт .: А.Б. Каплан, А.Д. Майданов, Р.М. Царев.