Линейное программирование

F(х1)=90∙3+15∙10+70∙6+105∙22+60∙4+50∙11+130∙15=270+150+420+2310+240+550+1950=5890

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

ui + vj = cij

Система уравнений:

u1 + v1 = 3,

u1+ v2 = 10,

u1 + v5= 6,

u2 + v2 = 22,

u2+ v3 = 4,

u3 + v3=11,

u3+v4=15.

u1= 0,

v1= 3,

v2 = 10,              

v5= 6,

u2= 22 - 10 = 12,

v3= 4-10= -6,

u3= 11+6=17,

v4= 15-17=-2,

Далее нужно проверить опорное решение х1 на оптимальность:

∆13 = u1+ v3−c13 = 0 -6-14=-20,

∆14 = u1+ - v4 − c14 = 0-2-15=-17,

∆21 = u2 + v1 – c21=12+3-2=13,

∆24 = u2 + v4– c24= 12-2-12=-2,

∆25 = u2 + v5– c25= 12+6-9=9,

∆31 = u3 + v1 – c31 = 17+3-8=12,

∆32 = u3  + v2– c32= 17+10-5=22,

∆35 = u3 + v5  − c35 =17+6-7=13

Начальное опорное решение не является оптимальным, так как имеются положительные оценки.

Для клетки (3.2) следует построить цикл, так как эта клетка имеет наибольшую оценку. В этой клетки нужно поставить знак «+», а потом следует чередовать знаки с «+» на «-». Далее  эту клетку нужно присоединить к занятым клеткам.

Ө=min

Таблица 2

Начальное опорное решение все еще не является оптимальным.

Теперь для клетки (2.4) следует построить цикл.

Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломанной линией, которая в каждой клетке совершает поворот на ± 90◦.

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

F(х2)=90∙3+15∙10+70∙6+65∙22+110∙4+50∙5+130∙15=270+150+420+1430++440+250+1950=4910

u1 + v1 = 3,

u1+ v2 = 10,

u1 + v5= 6,

u2 + v2 = 22,

u2+ v3 = 4,

u3 + v2=5,

u3+v4=15.

u1= 0,

u2= 12,

u3= -5,

v1= 3,

v2 = 10,

v3= -8,

v4=20,             

v5= 6.

∆13 = u1+ v3−c13=-5-14=-19,

∆14 = u1+ - v4 − c14 = 6-15=-9,

∆21 = u2 + v1 – c21=12+3-2=13,

∆24 = u2 + v4– c24= 12+20-12=20,

∆25 = u2 +  v5–  c25= 12+6-9=9,

∆31 = u3 + v1 – c31 = -5+3-8=-10,

∆33  = u3  +  v5– c33= -5-8-11=-24,

∆35 = u3 + v5  − c35 =-5+6-7=-6

Начальное опорное решение не найдено.

Следует построить новый цикл для клетки (1.4).

Таблица 3

F(х3)=90∙3+15∙10+70∙6+110∙4+65∙12+115∙5+65∙15=270+150+420+440+780+575+975=3610

u1 + v1 = 3,

u1+ v2 = 10,

u1 + v5= 6,

u2+ v3 = 4,

u3 + v4=12,

u3+v2=5,

u3+v4=15.

u1= 0,

u2= -8,

u3= -5,

v1= 3,

v2 = 10,

v3= 12,

v4=20,             

v5= 6.

∆13 = u1+ v3−c13=12-14=-2,

∆14 = u1+ - v4 − c14 = 20-15=5

∆21 = u2 + v1 – c21=-8+3-2=-7

∆24 = u2 + v4– c24= -8+10-22=-20

∆25 = u2 +  v5–  c25= -8+6-9=-11

∆31 = u3 + v1 – c31 = -5+3-8=-10

∆33  = u3  +  v5– c33= -5+12-11=-4

∆35 = u3 + v5  − c35 =-5+6-7=-6

Начальное опорное решение найдено.

Таблица 4

F(х3)=90∙3+15∙15+70∙6+110∙4+65∙12+130∙5+50∙15=270+225+420+440+780+650+750=3535

u1 + v1 = 3,

u1+ v4 = 15,

u1 + v5= 6,

u2+ v3 = 4,

u3 + v4=12,

u3+v2=5,

u3+v4=15.

u1= 0,

u2= -3,

u3= 0,

v1= 3,

v2 = 5,

v3= 7,

v4=15,             

v5= 6.

∆12 = u1+ v2−c12=5-10=-5,

∆13 = u1+ - v3 − c13 = 7-14=-7,

∆21 = u2 + v1 – c21=-3+3-2=-2,

∆22 = u2 + v2– c22= -3+5-22=-20,

∆25 = u2 +  v5–  c25= -3+6-9+-12,

∆31 = u3 + v1 – c31 = 3-8=-5,

∆33  = u3  +  v5– c33= 7-11=-4,

∆35 = u3 + v5  − c35 =6-7=-1.

Ответ: общая минимальная стоимость перевозок равна F min = 3535 ден.ед.

ЗАКЛЮЧЕНИЕ

В результате проделанной работы изучено несколько методов решения задачи линейного программирования, а именно графический, симплекс-метод (аналитический и табличный) для прямой и двойственной задачи линейного программирования, а также изучена транспортная задача.

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

Характерная особенность исследования операций — системный подход к поставленной проблеме и анализ. Системный подход является главным методологическим принципом исследования операций. Он заключается в следующем. Любая задача, которая решается, должна рассматриваться с точки зрения влияния на критерии функционирования системы в целом. Для исследования операций характерно то, что при решении каждой проблемы могут возникать новые задачи. Важной особенностью исследования операций есть стремление найти оптимальное решение поставленной задачи (принцип «оптимальности»). Однако на практике такое решение найти невозможно по таким причинам:

                    1) отсутствие методов, дающих возможность найти глобально оптимальное решение задачи

                    2) ограниченность существующих ресурсов (к примеру, ограниченность машинного времени ЭВМ), что делает невозможным реализацию точных методов оптимизации.

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1.                  Кремер Н.Ш. Исследование операций в экономике: Учеб.пособие для вузов\ Н.Ш. Кремер Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. – М.:ЮНИТИ, 2005. – 407 с.

2.                  Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике: Учебник: В 2-х ч. – М.: Финансы и статистика, 2005. – 384 с.

3.                  Шикин Е.В., Шикина Г.Е Исследование операций: учеб. М.: ТК Велби, Изд-во Проспект, 2006.-280 с.

4.                  Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем: Учеб. пособие.- 2-е изд., прераб. и доп.- М.: Финансы и статистика, 2006.-432 с.

5.                  Грызина Н.Ю., Мастяева И.Н., Семенихина О.Н. Математические методы исследования операций в экономике: Уч-метод.копл, 2008.- 204 с.

6.                  Палий И.А. Линейное программирование. Учебное пособие/ И.А. Палий. – М.: Эксмо, 2008. – 256 с.

7.                  Морозов В.В. Исследование операций в задачах и упражнениях: Учеб. пособие для вузов по специальности «Приклад.мат.»/ В.В.Морозов, А.Г. Сухарев, В.В. Федоров. – М.: ЛИБРОКОМ, 2009.-285 с.

8.                  Кремер Н.Ш. Исследование операций в экономике: Учеб. пособие для вузов по эконом. специальностям / Н.Ш. Кремер и др. -  М.: Юрайт, 2010. – 430 с.

9.                  Г.И. Просветов Математика в экономике. Задачи и решения: учебник / Г.И. Просветов . – М.: Экзамен, 2008. – 446 с.

10.                В.В. Лебедев Математика в экономике и управлении: Учеб. пособие по курсу «Высш. Математика» для экон. специальностей вузов / В.В. Лебедев. – М.: НВТ-Дизайн, 2004.- 479 с.

11.             В.А. Бабайцев, А.С. Солодовников, А.В. Браилов, И.Г. Шандра Математика в экономике Ч.1.: Учеб. для экон. специальностей вузов. – М.: Финансы и статистика, 2006. – 383 с.

12.             Н.В. Плотникова Исследование операций Часть1. Линейное программирование, Учеб. пособие. –Челябинск: Изд. ЮУрГУ, 2005. – 43 с.

40