Линейное программирование, решение задач симплексным методом (стр. 2 из 8)
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 неизвестными
a11x1 + a12x2 + … + a1nxn = b1,
……………
am1x1 + am2x2 + … + amnxn = bm.
Запишем эту систему в виде таблицы
| x1 | xj | xn | |
| b1 = | a11 … a1j … a1n | ||
| ……………….. | |||
| bi = | ai1 … aij … ain | ||
| ……………….. | |||
| bm = | am1 … amj … amn | ||
Шагом обыкновенного жорданова исключения (ОЖИ), произведенным над данной таблицей с разрешающим элементом aij ≠ 0 с I разрешающей строкой и j разрешающим столбцом, назовем операцию решения уравнения
bi = ai1x1 + ai2x2 + … + aijxj + … + ainxn
относительно xj, подстановки этого решения в исходную систему и записи вновь полученной системы в виде новой таблицы.
Нетрудно проверить, что новая таблица будет иметь вид
| x1 | x2 … | bi… | xn | |
| b1 = | b11 b12 … a1j … b1n | |||
| b2 = | b21 b22 … a2j … b2n | |||
| … | ……………….. | |||
| xj | -ai1 –ai2 … 1 ... -ain | |||
| … | ……………….. | |||
| bm = | bm1 bm2 … amj … bmn | |||
: aij,
где brs = arsaij - arjais (i ≠ r, j ≠ s),
причем все элементы таблицы нужно разделить на aij.
Таким образом, один шаг жорданова исключения (ШЖИ) переводит исходную таблицу в новую по схеме, состоящей из следующих 5 правил:
1) разрешающий элемент заменяется единицей
2) остальные элементы разрешающего столбца j остаются без изменения.
3) остальные элементы разрешающей строки i меняют лишь свои знаки.
4) остальные элементы brs вычисляются по формуле brs = arsaij - arjais
5) все элементы новой таблицы делятся на разрешающий элемент aij.
Пример 1. Для таблицы
| X1 | X2 | X3 | |
| Y1 = | 1 | -2 | 3 |
| Y2 = | -1 | 1 | 2 |
| Y3 = | 2 | -1 | -1 |
один шаг жорданова исключения с разрешающими 2-й строкой и 3-м столбцом приводим к таблице
| X1 | X2 | Y2 | |
| Y1 = | 5 | -7 | 3 |
| X3 = | 1 | -1 | 1 |
| Y3 = | 3 | -1 | -1 |
: 2
Жордановы исключения позволяют от случайно взятой декартовой системы координатных плоскостей перейти к новой системе, в которой координатами точек являются их уклонения
от более интересной для той или другой задачи системы плоскостей. Модифицированные жордановы исключенияЕсли исходную систему уравнений ai1x1 + ai2x2 + … + ainxn = bi, где i = 1,m,
записать в виде –ai1(-x1) – ai2(-x2) - … - ain (-xn) = bi
и составить таблицу
| -X1 | -X2 | …-Xn | |
| b1 = | –a11 | –a12 | … –a1n |
| …. | ………….. | ||
| bm = | –am1 | –am2 | … –amn |
то в этих случаях вместо ОЖИ пользуются МЖИ.
Один шаг МЖИ с разрешающим элементом “-ars”, означает переход к новой таблице
| -X1 … | -Yr … | -Xn | |
| b1 = | b11 ... | a1s … | b1n |
| …. | ……………………. | ||
| xs = | -ar1 … | 1 … | -arn |
| …. | ……………………. | ||
| bm = | bm1 … | ams … | bmn |
: (-ars)