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

Условие задачи:

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

Полуфабрикаты	Содержание полуфабриката в 1 л бензина	Минимальная норма
I сорт	II сорт
I
II
Стоимость

 

Математическая модель задачи:

Введем переменные x₁ – количество бензина первого сорта, x₂ – количество бензина второго сорта. Тогда 1×x₁ – стоимость производства бензина первого сорта, 1×x₂ – стоимость производства бензина второго сорта. В результате получим целевую функцию f = x₁ + x₂ → min.

Учитывая, что для выпуска бензина первого сорта используется 2 единицы полуфабриката типа I, получим 2× x₁ – количество полуфабриката типа I, необходимого для выпуска бензина первого сорта. Учитывая, что для выпуска бензина второго сорта используется 1 единица полуфабриката типа I, получим 1× x₂ – количество полуфабриката типа I, необходимого для выпуска бензина второго сорта. Учтем минимальную норму полуфабриката типа I в количестве 7, получим ограничение 2 x₁ + 1 x₂ ³ 7. Аналогично получается второе ограничение. На переменные накладывается условие неотрицательности.

Таким образом, получим следующую математическую модель:

f = x₁ + x₂ → min

2 x₁ + 1 x₂ ³ 7,

2 x₁ + 3 x₂ ³ 10,

x₁ ³ 0,

x₂ ³ 0.

 

Для этого подготовим исходные данные. Внесите следующие данные и функции, указанные в таблице 1.

Таблица 1.

Исходные данные

Заголовки строк	Заголовки столбцов
A	B	C	D	E	F
	Решение	x1	x2
	Целевая функция			min (max)	=СУММПРОИЗВ($B$2:$C$2;B3:C3)
		Коэффициенты			Свободные члены
	Ограничения			>=	=СУММПРОИЗВ($B$2:$C$2;B5:C5)
			>=	=СУММПРОИЗВ($B$2:$C$2;B6:C6)

 

В ячейке E3 используется функция для вычисления значения целевой функции f = c₁x₁ + c₂x₂, где c₁ и c₂ – значения коэффициентов целевой функции; x₁, x₂ - искомые значения неизвестных. В ячейках E5 и E6 используется левые части неравенств первого и второго ограничений , где a_ij – значения коэффициентов в ограничениях.

Затем в меню «Сервис» выбираем команду «Поиск решения». Если данной команды нет, то Сервис | Надстройки | Поиск решения.

 

Вводим следующие значения: в поле «Установить целевую ячейку» вводим адрес ячейки $E$3; в поле «Равной» выбираем «минимальному значению»; В поле «Изменяя ячейки» вводим диапазон ячеек $B$2:$C$2.

Щелкаем по кнопке «Добавить». Вводим ограничения: $E$5>=$F$5 и $E$6>=$F$6. Щелкаем по кнопке «Параметры» и ставим флаг в поле «Неотрицательные значения».

 

 

 

 

Выполним процедуру, щелкнув по кнопке «Выполнить». Если решение будет найдено, то появится сообщение: «Решение найдено. Все ограничения и условия оптимальности выполнены». Выбрав «Сохранить найденное решение», получим таблицу результатов (табл. 2).

 

 

Таблица 2.

Результаты

Заголовки строк	Заголовки столбцов
A	B	C	D	E	F
	Решение	x1	x2
		2,75	1,5
	Целевая функция			min (max)	4,25
		Коэффициенты			Свободные члены
	Ограничения			>=
			>=

 

Делаем вывод, что оптимальное решение X^*(2.75; 1.5), f(X^*)=4.25.

Интерпретация полученного решения:для получения минимальной стоимости 4,25 выпуска бензина необходимо организовать выпуск бензина первого сорта в количестве 2,75 литра, а второго сорта ‑ 1,5 литра.