Математические методы оптимизации (стр. 1 из 4)

Задание 1. Графическое решение задачи распределения ресурсов

· Записать стандартную и каноническую формы.

· Найти все базисные и допустимые базисные решения. Определить оптимальное базисное решение.

· Найти графически оптимальное базисное решение.

Фирма выпускает два вида изделий А и В. Каждое изделие проходит обработку на двух технологических линиях.

Известна таблица технологических коэффициентов

- времени обработки (в минутах) каждого изделия на каждой технологической линии. Кроме этого, известны рыночная цена каждого изделия и и общее время каждой линии и .

Изделия А	Изделия В	Общее время работы линии
Линия 1	60	32	1920
Линия 2	36	60	2160
Цена одного изделия	30	25

РЕШЕНИЕ

Запишем стандартную и каноническую формы

Обозначим:

план выпуска изделия А;

план выпуска изделия В.

Тогда затраты линии 1 и линии 2, необходимые для производства плана

будут равны соответственно:

План

будет допустимым, если затраты для линии 1 и линии 2 не превосходят общего времени работы каждой из линий, т.е. выполняются неравенства:

Целевой функцией служит выручка от реализации допустимого плана

при ограничениях

(1.1)

Для канонической формы эти ограничения нужно преобразовать в равенства. Для этого введём две дополнительные переменные

остаток от производства на линии 1 (остаток времени обработки)

остаток от производства на линии 2 (остаток времени обработки).

Тогда получим каноническую форму задачи:

-найти переменные

, которые дают максимум целевой функции

при ограничениях

(1.2)

· Найдём все базисные решения.

Полученные ограничения образуют систему двух уравнений с четырьмя неизвестными. Среди бесконечного множества решений этой системы базисные решения получаются следующим образом. Две переменных приравняем к 0. Эти переменные назовём свободными. Значения остальных переменных получаем из решения системы. Эти переменные назовём базисными. Базисное решение называется допустимым, если оно неотрицательно.

1) Пусть

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

Следовательно, базисное решение имеет вид

.

Базисное решение означает, что изделия А и изделия В не производятся. Это базисное решение является допустимым. Выручка от реализации этого плана составит

.

2) Пусть

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

Следовательно, базисное решение имеет вид

.

Это базисное решение означает, что изделие А не производится, изделие В производится в количестве 60 ед., время изготовления продукции на линии 1 используется полностью, для производства на линии 2 не хватает 1440 минут работы. Это базисное решение не является допустимым.

3) Пусть

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

для базисных переменных

и . Следовательно, базисное решение имеет вид

.

Это базисное решение означает, что изделие А не производится, изделие В производится в количестве 36 единиц, время изготовления продукции линии 1 используется не полностью и его остаток составляет 768 минут, а на линии 2 используется полностью. Это базисное решение является допустимым. Выручка от реализации этого плана составит

ден.ед.

4) Пусть

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

для базисных переменных

. Следовательно, базисное решение имеет вид . Базисное решение означает, что изделия А производится в количестве 32 ед., изделие В не производится, время изготовления продукции линии 1 используется полностью, а время изготовления линии 2 не полностью используется, его остаток составляет 1008 минут. Это базисное решение является допустимым. Выручка от реализации этого плана составит

ден. ед.

5) Пусть

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

для базисных переменных

. Следовательно, базисное решение имеет вид . Это базисное решение означает, что изделия А производится 60 ед., изделие В не производится, не хватает времени обработки 1680 минут для первой линии, а время обработки второй линии используется полностью. Это базисное решение не является допустимым.

6) Пусть

свободные переменные. Тогда базисные переменные и найдём из системы уравнений

Отсюда следует, что базисное решение имеет вид

. Это решение означает, что изделия А производятся в количестве ед., изделия В производятся в количестве , время обработки на каждой из линий используется полностью. Это базисное решение является допустимым. Выручка от реализации составит ден.ед.

· Определим оптимальное базисное решение.

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

В таблице 1.1 приведены все допустимые базисные решения и соответствующие им значения выручки

.

двойственный задача равновесный спрос полезность товар

Таблица 1.1

№	Базисные переменные		Небазисные переменные
1
2
3
4

Максимальное значение выручки достигается на четвёртом базисном решении в этой таблице