Реферат: Линейное программирование, решение задач симплексным методом

3.1.3. Задача третья:

На предприятии выпускают 3 вида изделий, при этом используют 3 вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице:

Виды сырья	Расход сырья на продукцию			Запасы сырья
	1	2	3
1	2	3	7	1250
2	1	1	0	250
3	5	3	0	900
Прибыль	41	35	96

Как следует спланировать выпуск продукции, чтобы прибыль была наибольшей?

3.1.4. Задача четвертая:

Для изготовления 4 видов продукции используются 3 вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице:

Виды сырья	Расход сырья на продукцию				Запасы сырья
	1	2	3	4
1	2	3	3	1	20
2	1	1	2	2	11
3	1	2	3	1	25
Прибыль	2	4	3	2

Как следует спланировать выпуск продукции, чтобы прибыль была наибольшей?

3. Заключение

4. Список литературы

Председатель цикловой комиссии /Баранов В.А.

Руководитель курсового проекта /Карпушкин А.Г.

Дата выдачи задания: Срок окончания:

« » 2007 г. « » 2007 г.

СИМПЛЕКСНЫЙ МЕТОД

Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако, еще в 1939 г. идеи метода были разработаны российским ученым

Л В.Канторовичем.

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

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

элемента:

• способ определения какого-либо первоначального допустимого

базисного решения задачи;

• правило перехода к лучшему (точнее, не худшему) решению;

• критерий проверки оптимальности найденного решения.

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

Обыкновенные жордановы исключения

Рассмотрим систему из m линейных уравнений с n неизвестными

a₁₁ x₁ + a₁₂ x₂ + … + a_1n x_n = b_1,

……………

a_m1 x₁ + a_m2 x₂ + … + a_mn x_n = b_{m .}

Запишем эту систему в виде таблицы

	x1	xj	xn
b1 =	a11 … a1j … a1n
………………..
bi =	ai1 … aij … ain
………………..
bm =	am1 … amj … amn