Математические модели задачи фирмы 2 страница

Как видно из таблицы 3, абсолютное значение в правой части таблицы возрастало после каждой итерации. Так же максимальное значение по столбцам тоже уменьшалось, пока все значения по строке не стали нулевыми или отрицательными. Из базиса видно, что при и прибыль будет максимальной и составит 385 ден.ед. Учитывая условия целостности, примем , тогда прибыль составит, так же как и при графическом методе, ден.ед.

1.3.3. Специальные задачи линейного программирования.

Перевозки товаров различными транспортными средствами в ряде случаев приводят к таким нежелательным явлениям, как порожние пробеги, простои, встречные и нерациональные перевозки. Для их исключения используются методы оптимального планирования перевозок, в частности, такая экономико-математическая модель, как «транспортная задача».

Под транспортной задачей в настоящее время понимают комплекс задач, имеющих специфические постановку и алгоритм решения.

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

Постановку и методику решения подобных задач рассмотрим с использованием следующего примера. Три завода некоторого объёдинения, территориально удалённые друг от друга, выпускают однотипную продукцию. Ежедневные объёмы производства на заводах составляют соответственно 120, 100 и 80 единиц некоторого товара. В конце рабочего дня товар должен быть развезён по оптово-розничным складам. Складов всего три. Причём они, так же как и заводы располагаются в разных районах региона. Ежедневный спрос на продукцию объединения у менеджеров складов соответственно 90, 90, 120 единиц продукции заводов. Известны также показатели затрат на перевозку 1 ед. товара от каждого из заводов до каждого из складов.

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

в которой - количество единиц товара планируемого к перевозке от i-го завода на j-ый склад, а под затратами понимается матрица

в которой - стоимость перевозки единицы груза от i-го завода на j-ый склад.

Для решения задачи исходные данные удобно свести в таблицу (табл.4), где числа 7, 6, 4 и т.д. обозначают стоимость перевозок, т.е. . Каждая клетка таблицы индексирована индексами i и j.

Таблица 4

Заводы	Объём производства	Потребители и их спрос
j=1	j=2	j=3
i=1
i=2
i=3

Математическая постановка данной задачи имеет вид: найти оптимальный план перевозок, доставляющий минимум целевой функции. Целевая функция описывается следующим образом:

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

Опорный план может быть получен различными методами. Рассмотрим метод «наименьших затрат». Суть метода заключается в том, что в таблице затрат выбирается клетка с наименьшем значением, т.е. клетка [3;1]=2. Третий завод может поставить в эту клетку не более 80 ед. груза, а первый склад может принять не более 90 е.д. Следовательно, максимальный грузопоток в этой клетке будет 80 ед. Однако, на первый склад нужно поставить ещё 10 ед. груза. Мы можем их поставить как из первого завода, так и со второго. Т.к. затраты на перевозку на склад №1 меньше у второго завода, то запланируем перевозку десяти ед. груза с него на первый склад.

Далее, аналогичным образом, распределяем остальной грузопоток. Со второго завода вывезено 10 ед., а 90 ед. ещё осталось. Остаток можно вывести как на второй склад так и на третий, но минимальные затраты на перевозку будут в случае транспортировки груза на склад №3. Полный опорный план представлен в таблице 5.

Проверим полученный опорный план. Сумма перевозок по строкам должна совпадать с соответствующими объёмами производства каждого из заводов. Сумма перевозок по столбцам должна совпадать с потребностью складов. По текущему плану перевозок целевая функция равна 1300 ден.ед.

Таблица 5

Заводы	Объём производства	Потребители и их спрос
j=1	j=2	j=3
i=1
		30
i=2
i=3

Следующим этапом решения задачи, является последовательное улучшение плана перевозок до оптимального. Для чего введём систему потенциалов и . При расчёте потенциалов нужно руководствоваться следующим:

1) всегда равно нулю;

2)

При расчёте нужно использовать только клетки, содержащие план перевозок. Например, зная, что и что по строке 1 в плане перевозок учувствуют ячейки [i = 1; j =2] и [i = 1; j =3], можем найти значения и . Для чего решим уравнения и . Зная значение можно найти значение , после найти значения и . Полный расчёт приведён в таблице 6.

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

Таблица 6

Заводы	Объём производства	Потребители и их спрос	u
j=1	j=2	j=3
i=1											u1 = 0
i=2											u2 = 1
i=3											u3 = 0
					-3
	v	v1 = 2	v2 = 6	v3 = 4

В таблице 6 ячейкой с отрицательным коэффициентом напряжённости является ячейка [i = 3; j = 1]. В эту ячейку нужно направить грузопоток, т.е. пересчитать план перевозок. Для изменения грузопотока составляется цепь пересчёта. Цепь представляет собой прямоугольную фигуру, одна из вершин которой находится в ячейке с отрицательным коэффициентом напряжённости, а остальные в ячейках, участвующих в грузоперевозке. Поочерёдно каждой из вершин цепи (начиная с ячейки с отрицательным коэффициентом) присваиваются знаки «+» и «-». Долее выбирается объём изменения грузопотока по минимальному значению плана перевозок выпадающих на вершины со знаком «-» (табл. 7). Таблица 7

Заводы

Объём производства

Потребители и их спрос

u

j=1

j=2

j=3

90

90

120

i=1

120

u1 = 0

90(-80)

30(+80)

i=2

100

u2 = 1

(+80)

(-80)

i=3

80

u3 = 0

80(-80)

(+80)

-3

v

v1 = 2

v2 = 6

v3 = 4

Измененный план грузоперевозок, обрабатывается по уже описанному алгоритму и приведён в таблице 8.

Таблица 8

Заводы	Объём производства	Потребители и их спрос	u
j=1	j=2	j=3
i=1											u1 = 0
i=2											u2 = 1
i=3											u3 =-3
					-3
	v	v1 = 2	v2 = 6	v3 = 4

После первой итерации в таблице 8 нет отрицательных коэффициентов, следовательно, полученный план грузоперевозок является оптимальным. Затраты на перевозку (W) составят 1 060 ден. ед.

В рассмотренном примере объёмы производства заводов были равны объёмам спроса. В случаях, когда это условие не выполняется, в задачу вводят фиктивного поставщика или потребителя доставляющих или потребляющих недостающие для равенства объёмы товаров.

Контрольные вопросы.

1. Допустимое решение задачи линейного программирования…

а. должно одновременно удовлетворять всем ограничениям задачи

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

в. должно быть вершиной множества допустимых решений

г. должно обеспечивать наилучшее значение целевой функции

2. План перевозок вырожденный, если число клеток транспортной таблицы:

а. равно m+n-1;

б. больше m+n-1;

в. меньше m+n-1.

3. Почему план перевозок, полученный по методу «северо-западного» угла, обычно бывает достаточно далек от оптимального?

4. Что называется планом задачи линейного программирования?

5. Дайте определение уровня целевой функции задачи линейного программирования.

6. К чему приведет включение в план выпуска изделия, для которого >c_j ?

7. Частным случаем какой задачи является задача о назначениях?

1.4 Варианты заданий по теме

Задача 1.

Предприятие, располагающее ресурсами сырья четырех видов А, В, С и D, может производить продукцию двух видов Р₁, Р₂. В таблице указаны затраты ресурсов на изготовление 1т продукции, объем ресурсов и выручка, получаемая от продажи 1т соответствующей продукции. Требуется определить план выпуска продукции каждого вида с целью получения максимальной прибыли.

1. Составьте математическую модель и решите задачу графическим методом.

2. Найдите решение задачи используя симплекс метод.

3. Решите задачу в пакете EXCEL и сравните результаты.

Вариант № 1

Вид сырья	Вид продукции	Объем ресурсов, т
Р1	Р2
А
В
С
D
Прибыль, руб.

Вариант № 2

Вид сырья	Вид продукции	Объем ресурсов, т
Р1	Р2
А
В
С
D
Прибыль, руб.

Вариант № 3

Вид сырья	Вид продукции	Объем ресурсов, т
Р1	Р2
А
В
С
D
Прибыль, руб.

Задача 2

Фирма производит два продукта А и В, рынок сбыта которых не ограничен. Каждый продукт должен быть обработан машинами 1, 2, 3, 4. Время обработки для каждого из изделий А и В, также допустимое время использования машин приведено ниже. Требуется определить план выпуска продукции каждого вида с целью получения максимальной прибыли.

1. Составьте математическую модель и решите задачу графическим методом.

2. Найдите решение задачи используя симплекс метод.

3. Решите задачу в пакете EXCEL и сравните результаты.

Вариант № 1

Станки	Допустимое время использования	Продукция
А	В
1
2
3
4
Прибыль, руб.

Вариант № 2

Станки	Допустимое время использования	Продукция
А	В
1
2
3
4
Прибыль, руб.

Вариант № 3

Станки	Допустимое время использования	Продукция
А	В
1
2
3
4
Прибыль, руб.

Задача 3

Продукция определенного типа производится в городах А₁, А₂, А₃ и потребляется в городах В₁, В₂ В₃ и В₄. В таблицах по вариантам указаны: объем производства, спрос, стоимость перевозки единицы продукции.

Составить оптимальный план перевозки продукции, при котором стоимость всех перевозок будет минимальна. Если задача не сбалансирована, тогда ввести фиктивных потребителей или производителей, добавить к исходной таблице.

Вариант № 1

Производители	Объем производства	Потребители
В1	B2	В3	В4
А1
А2
Аз
Спрос

Вариант № 2

Производители	Объем производства	Потребители
В1	B2	В3	В4
А1
А2
Аз
Спрос

2. Теоретические модели

2.1. Теория предельной полезности

Теория предельной полезности исследует поведение потребителя на потребительском рынке. Основным понятием этой теории является функция полезности, отражающей зависимость полезности набора благ от количеств этих благ, входящих в набор. Полезностью называют удовлетворение, которое получают от потребления определенного набора единиц товара или услуги. Различают и предельную . Общая полезность – это удовлетворение, которое получают от потребления определенного набора единиц товара или услуг.

Введем обозначения:

i = 1, …, m – номер блага;

х_i – количество i-го блага в наборе;

Х = (х₁, …, х_i, …, х_m) – набор благ;

U = U (X) = U (х₁, …, х_i, …, х_m) – функция полезности набора благ;

P_i – цена i-го блага;

В – бюджет потребителя, т.е. количество денег, которым располагает потребитель для покупок.

Выделим i-е благо. Количество его в наборе будем считать переменной величиной, а количества всех остальных – постоянными. На рис. 6 показан вид функции U = U (x_i).

Рисунок 6 Функция предельной полезности

Линия, соединяющая потребительские наборы (х₁, …, х_i, …, х_m), имеющие один и тот же уровень удовлетворения потребностей индивидуума, называется линией безразличия – линия уровня функции полезности

Количество блага измеряется в физических единицах (килограммах, метрах и т.д.). Полезность блага измеряется в специально введенных единицах – ютилях. Это единица условная, она различна для разных людей. Предполагается, что любой человек в состоянии признать полезность какого-то количества блага за единицу (ютиль) и в этих единицах измерять полезность всех других благ.

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

Обозначим:

х_i – количество i-го блага;

U_i – полезность данного количества i-го блага;

Δх_i – приращение количества блага;

ΔU_i – приращение полезности;

МU_i – предельная полезность блага.

Тогда:

Определение: предельная полезность блага есть частная производная от функции полезности блага по его количеству.

Свойства функции полезности (Рисунок 6):

- функция существует;

- проходит через ноль, т.е. U_i = 0 при х_i = 0;

- непрерывна;

- дифференцируема;

- возрастает на всей области определения, т.е. ;

- выпукла, т.е. предельная полезность убывает, .

Каждый человек легко может признать его, наблюдая за своими предпочтениями: предельная полезность блага убывает с ростом его количества.

Благосостояние человека определяется набором благ, которым он обладает. Разумность экономического человека состоит в том, что он стремится получить в свое распоряжение набор благ наибольшей полезности, действуя в рамках закона и нравственности.

Для потребителя возникает оптимизационная задача – найти набор благ наибольшей полезности при ограничении по бюджету.

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

U = U (х₁, …, х_i, …, х_m) .

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

Смысл ограничений: первое – покупки ограничены бюджетом, второе – блага потребителем либо покупаются, либо нет, но не продаются. Сформулированная задача является задачей на условный экстремум. Составим функцию Лагранжа:

В этой функции к полезности добавлено ограничение по бюджету, умноженное на дополнительную переменную Лагранжа l. Величина есть оставшаяся (неизрасходованная) сумма денег. Экономический смысл переменной l – предельная полезность оставшихся денег.